12
Algorithmique & Programmation Semestre 2 ST Rappels du semestre 1 Rappels du semestre 1 Types agrégés Structuration en sous-algorithmes Tableaux de variables Algorithmes de recherche et de tri Précision, rapidité et complexité Matrices de variables Récursivité Travaux dirigés Travaux pratiques Informations Sujets de projet Evaluation intermédiaire Evaluation finale Evaluation complémentaire Archives Exécution séquentielle Les types Les constantes littérales Les variables et les constantes Le transtypage Les opérateurs Les instructions de structuration Analyse d'un problème Les algorithmes Débugger Version PDF Exécution séquentielle Programme informatique (algorithme): Stockage d'informations Traitements sur ces informations Exécution séquentielle: Instructions exécutées dans l'ordre de leur écriture dans le fichier source Instruction en cours d'exécution possiblement influencée par les instructions précédentes Instruction en cours d'exécution possiblement influente sur les instructions suivantes Instruction en cours d'exécution jamais influencée par les instructions suivantes Instruction en cours d'exécution jamais influente sur les instructions précédentes Les types Typage des informations stockées au sein d'un programme: Catégorie d'information Limites inhérentes au type Occupation mémoire (empreinte mémoire) Langage algorithmique Langage Java Nom et type d'information stockée Nom de type Intervalle de définition Occupation mémoire Page 1 sur 12 Algorithmique-Programmation Semestre 2 ST - Rappels du semestre 1 08/02/2017 http://127.0.0.1:9000/Algo-S2/00-Rappels/Default.htm

Algorithmique & Programmation Semestre 2 STraphaello.univ-fcomte.fr/Algo-S2/PDF/00-Rappels.pdf · Semestre 2 ST Rappels du semestre 1 Rappels du semestre 1 Types agrégés Structuration

Embed Size (px)

Citation preview

Algorithmique & Programmation

Semestre 2 STRappels du semestre 1

Rappels du semestre 1

Types agrégésStructuration

en sous-algorithmes

Tableaux

de variables

Algorithmes

de recherche et de tri

Précision, rapidité

et complexité

Matrices

de variablesRécursivité

Travaux

dirigés

Travaux

pratiquesInformations

Sujets de projetEvaluation

intermédiaireEvaluation finale

Evaluation complémentaire

Archives

Exécution séquentielle Les typesLes constantes

littérales

Les variables

et les constantesLe transtypage

Les opérateursLes instructions

de structurationAnalyse d'un problème Les algorithmes Débugger

Version PDF

Exécution séquentielle

• Programme informatique (algorithme): ◦ Stockage d'informations◦ Traitements sur ces informations

• Exécution séquentielle: Instructions exécutées dans l'ordre de leur écriture dans le fichier source

◦ Instruction en cours d'exécution possiblement influencée par les instructions précédentes

◦ Instruction en cours d'exécution possiblement influente sur les instructions suivantes◦ Instruction en cours d'exécution jamais influencée par les instructions suivantes◦ Instruction en cours d'exécution jamais influente sur les instructions précédentes

Les types

• Typage des informations stockées au sein d'un programme: ◦ Catégorie d'information◦ Limites inhérentes au type◦ Occupation mémoire (empreinte mémoire)

Langage algorithmique Langage Java

Nom et type

d'information stockéeNom de type

Intervalle

de définition

Occupation

mémoire

Page 1 sur 12Algorithmique-Programmation Semestre 2 ST - Rappels du semestre 1

08/02/2017http://127.0.0.1:9000/Algo-S2/00-Rappels/Default.htm

entier

byte [-128, 127]

équivalent à [-27, 27-1]

1 octet

short[-32768, 32767]

équivalent à [-215, 215-1]2 octets

int[-2147483648, 2147483647]

équivalent à [-231, 231-1]4 octets

long[-9223372036854775808, 9223372036854775807]

équivalent à [-263, 263-1]8 octets

réel

float

En valeur positive ou négative

Valeur minimale strictement positive: 1.4e-45

Valeur minimale strictement positiveavec mantisse à 8 chiffres de précision:

1.17549435e-38

Valeur maximale avec mantisse à 8 chiffresde précision:

3.4028235e+38

4 octets

double

En valeur positive ou négative

Valeur minimale strictement positive: 4.9e-324

Valeur minimale strictement positiveavec mantisseà 16 chiffres de précision:

2.2250738585072014e-308

Valeur maximale avec mantisseà 16 chiffres de précision:

1.7976931348623157e+308

8 octets

booléen boolean vrai ou faux 1 octet

caractère char

lettres: a à z, A à Z,chiffres: 0 à 9,

caractères de ponctuation: ,, ., ;, :, ^, ...caractères accentués: é, ù, è, à, ê, ï, ...

caractères spécifiques aux langues,...

2 octets

chaîne StringToute suite de n caractèresnotés entre guillemets (")

2*(n+1) octets

Les constantes littérales

• Valeurs numériques, caractères ou chaînes de caractères directement entrées dans le code source

Recommandation

• En langage algorithmique, noter les constantes littérales numériques en respectant leurs types

• Exemple: 1 et 1.0 pour la valeur 1 en entier et en réel

Recommandation

• En Java, noter les constantes littérales numériques en respectant leurs types • Exemple: 1, 1.0, 1.0F, 1L pour la valeur 1 en int, double, float et long

• En langage Java:◦ Constante littérale numérique 4 de type int: 4

◦ Constante littérale numérique 4 de type long: 4L

◦ Constante littérale numérique 4.0 de type double: 4.0

◦ Constante littérale numérique 4.0 de type float: 4.0F

◦ Constante littérale numérique 3.123e-18 de type double: 3.123E-18

Page 2 sur 12Algorithmique-Programmation Semestre 2 ST - Rappels du semestre 1

08/02/2017http://127.0.0.1:9000/Algo-S2/00-Rappels/Default.htm

◦ Constante littérale numérique 3.123e-18 de type float: 3.123E-18F

◦ Constante littérale caractère 2: '2'

◦ Constante littérale chaîne de caractères Abc: "Abc"

◦ Constantes littérales booléennes vrai et faux: true et false

◦ Constante littérale décimale 18 de type int mais notée sous forme hexadécimale (base 16): 0x00000012

◦ Constante littérale caractère Escape (code ascii décimal 27 codé 1B en hexadécimal): '\x1B'

Les variables et les constantes

• Stockage des informations des programmes dans des variables et des constantes

• Variable:◦ Caractérisée par un nom et un type◦ Contenu variable par "affectation" (signe <- en langage algorithmique, signe = en java)

• Constante:◦ Caractérisée par un nom, un type et une valeur◦ Contenu non modifiable

• Dans le code source, utilisation du nom pour désigner la variable ou la constante, mais en fait, désignation de son contenu

• Type utilisé pour définir ce qui peut être stocké• Déclaration -> Utilisation d'une quantité de mémoire fonction du type défini

Nom de constante

• Utilisation exclusive de lettres non accentuées, de chiffres et du caractère _Pas de chiffre en premier caractèreInterdiction d'utiliser les noms réservés du langage

• Convention

◦ Ecriture intégrale en majuscule• Exemples: N, M, PI, NOMBRE_AVOGADRO

Nom de variable

• Utilisation exclusive de lettres non accentuées, de chiffres et du caractère _Pas de chiffre en premier caractèreInterdiction d'utiliser les noms réservés du langage

• Convention

◦ Ecriture intégrale en minuscule◦ En cas de nom composé, mise en majuscule de l'initiale de chaque composante à

l'exception de la première• Exemples: r, longueurCote, nombreDeValeurs

Recommandation

Page 3 sur 12Algorithmique-Programmation Semestre 2 ST - Rappels du semestre 1

08/02/2017http://127.0.0.1:9000/Algo-S2/00-Rappels/Default.htm

• Choix de noms explicites pour les constantes et les variables (recommandation généralisée à tous les items pour lesquels le programmeur choisit le nom)

Syntaxe de déclaration d'une variable

Langage algorithmique Langage Java

nomVariable : type type nomVariable;

Syntaxe de déclaration d'une constante

Langage algorithmique Langage Java

constante type nomConstante < -

valeurSi définition en dehors du "main": public final static type

nomConstante = valeur;

Si définition dans le "main":final type nomConstante = valeur;

• En langage Java, affectation possible d'une valeur initiale à une variable lors de sa déclaration

• Syntaxe:

type nomVariable = valeur;

• valeur: Constante littérale, constante, variable ou expression affectée à la variable nomVariable

Le transtypage

• Transtyper (to cast en anglais): Convertir une information de son type véritable vers un autre type

• Pas de syntaxe particulière en langage algorithmique: affectation

• Syntaxe en langage Java:

(typeCible) (valeurOuVariableOuConstanteOuExpressionConvertie)

Exemples:

• (int) (2.623): Conversion du double 2.623 en l'entier 2 (troncature)

• (long) ('a'): Conversion du caractère a en un entier long -> 97 (code ASCII du caractère

a)• (float) (a): Conversion en un float du contenu de la variable ou de la constante a

• En langage Java, emploi explicite obligatoire du transtypage en cas d'éventuelle perte de précision (un double vers un float, un long vers un int, un double vers un int, ...)

Les opérateurs

Page 4 sur 12Algorithmique-Programmation Semestre 2 ST - Rappels du semestre 1

08/02/2017http://127.0.0.1:9000/Algo-S2/00-Rappels/Default.htm

• Opérateurs: Réalisation d'"opérations" sur les valeurs spécifiées (variables, constantes, ...)

Affectation

• Placement dans une variable (celle indiquée à gauche de l'opérateur) du contenu d'une variable, d'une constante, d'une constante littérale ou du résultat de l'évaluation d'une expression

• Cohérence de type entre la valeur affectée et la variable subissant l'affectation (transtypage éventuel)

Opérateur Langage algorithmique Langage Java

Affectation <- =

Opérateurs mathématiques

• Réalisation d'opérations mathématiques par construction d'"expressions arithmétiques" (respect des priorités usuelles des mathématiques, utilisation de parenthèses en cas de doute)Exemples

◦ a+b◦ a+b*c (équivalent à a+(b*c))

• Attention: Dépendance des opérations réalisées aux types des valeurs concernéesSi valeurs de différents types, conversion de la valeur du type le moins "précis" vers le type le plus "précis"Exemples

◦ Division réalisée sur deux entiers -> Division entière et résultat entier◦ Division réalisée sur un entier et un réel -> Division réelle et résultat réel◦ 3/2 -> 1◦ 19/10 -> 1◦ 3.0/2.0 -> 1.5◦ 3.0/2 -> 1.5◦ 3/2.0 -> 1.5

Opérateur Langage algorithmique Langage Java

Additions entière et réelle + +

Soustractions entière et réelle - -

Multiplication entière et réelle * *

Division entière et réelle / /

Reste de la division entière modulo %

Opérateurs de test

• Réalisation d'opérations de test entre "valeurs" (de types compatibles) par construction

d'"expressions conditionnelles" (fréquemment dénommées "conditions") simples (canoniques)

Opérateur Langage algorithmique Langage Java

Test d'égalité = ==

Test de différence � !=

Test d'infériorité < <

Test de supériorité > >

Page 5 sur 12Algorithmique-Programmation Semestre 2 ST - Rappels du semestre 1

08/02/2017http://127.0.0.1:9000/Algo-S2/00-Rappels/Default.htm

Test d'infériorité ou égalité � <=

Test de supériorité ou égalité � >=

• Exemples: ( a > b ), ( c = 3.0 ), ( x != y )

Opérateurs booléens

• Application à des valeurs booléennes• Composition d'expressions conditionnelles de manière à créer des expressions conditionnelles

complexes

Opérateur Langage algorithmique Langage Java

non non !

et et &&

ou ou ||

ou exclusif ou exclusif ^

et faux vrai

faux faux faux

vrai faux vrai

ou  faux vrai

faux faux vrai

vrai vrai vrai

ou

exclusif faux vrai

faux faux vrai

vrai vrai faux

-  non

faux vrai

vrai faux

• Exemple: non(a), non( a > b ), non(( a > b ) et ( c = 3.0 )), !(( a == b) && ( a != c))

Opérateurs spécifiques aux chaînes de caractères en Java

• Variable s de type String en Java◦ s.length() -> Le nombre de caractères de s◦ s.substring(i,j) -> La sous-chaîne de caractères de s commençant au caractère

d'indice i et finissant au caractère d'indice j-1 (j-i caractères de long, indices comptés à partir de 0)

◦ s.charAt(i) -> Le caractère de s situé à l'indice i (indices comptés à partir de 0)◦ s.toCharArray() -> Le tableau (vu plus tard) de caractères contenant, dans l'ordre,

tous les caractères de s

Les instructions de structuration

Structuration conditionnelle

"si"

• Exécution d'un bloc de code si le résultat de l'évaluation d'une expression conditionnelle a pour résultat la valeur booléenne vrai

• Possibilité optionnelle: Exécution alternative d'un second bloc de code si le résultat de l'évaluation de l'expression conditionnelle est faux ("sinon")

• Principale instruction de structuration conditionnelle• Utilisation extrêmement fréquente avec ou sans sinon

Syntaxe

Page 6 sur 12Algorithmique-Programmation Semestre 2 ST - Rappels du semestre 1

08/02/2017http://127.0.0.1:9000/Algo-S2/00-Rappels/Default.htm

Langage algorithmique Langage Java

si condition alors

bloc 1

sinon

bloc 2

fsi

if ( condition ) {

bloc 1 }

else {

bloc 2 }

"cas"

• Exécution de différents blocs de code en fonction de l'égalité d'une variable ou du résultat de l'évaluation d'une expression arithmétique avec différentes valeurs numériques constantes

• Possibilité optionnelle: Exécution d'un bloc de code alternatif si aucun autre bloc de code n'a été exécuté (i.e. si aucune égalité n'a été établie entre les constantes et la variable ou le résultat de l'évaluation de l'expression arithmétique)

• Utilisation peu fréquente mais instruction très pratique lorsque le cas s'y prête (gestion d'un menu, ...)

Syntaxe

Langage algorithmique Langage Java

Déclaration de la variable var

...

var <- ...

...

dans le cas de var

valeur1 :

bloc 1

valeur2 :

bloc 2

...

valeurN :

bloc N

autre cas :

bloc

fin cas de

Déclaration de la variable var

...

var = ...;

...

switch (var) {

case constante1 : {

bloc 1 }

break;

case constante2 : {

bloc 2 }

break;

...

case constanteN : {

bloc N }

break;

default : {

bloc }

break;

}

• En langage Java, valeur testée obligatoirement de type entier ou caractère et valeurs comparées obligatoirement constantes

• Recommandation: Faire pareil en langage algorithmique

Structuration itérative

"pour"

• Exécution répétitive (en boucle) du même bloc de code

Page 7 sur 12Algorithmique-Programmation Semestre 2 ST - Rappels du semestre 1

08/02/2017http://127.0.0.1:9000/Algo-S2/00-Rappels/Default.htm

• Utilisation d'une variable comme "compteur" de management du "pour":◦ Initialisée à une valeur donnée◦ Incrémentée d'une valeur donnée à chaque boucle◦ Limitée à une valeur donnée (y compris cette valeur)

• Utilisation à privilégier si nombre d'itérations connu dès avant le début d'exécution de l'instruction itérative

Syntaxe

Langage algorithmique Langage Java

Déclaration de la variable var

...

pour var de borne1

à borne2

pas p faire

bloc

fait

Déclaration de la variable var

...

for ( var = borne1 ;

var <= borne2 ;

var = var+p ) {

bloc }

• Bornes et pas généralement constants (inchangés dans le bloc de code)• En langage algorithmique pas implicitement de valeur 1 si non spécifié• Syntaxe du "for" Java sensiblement différente de celle du "pour" algorithmique

  - Initialisation explicite en premier item  - Expression conditionnelle en deuxième item  - Incrémentation explicite en troisième item

"tant que"

• Exécution en boucle du même bloc de code• Poursuite avec une nouvelle exécution du bloc de code tant que le résultat de l'évaluation de

l'expression conditionnelle sur laquelle porte le "tant que" a vrai pour résultat• Evaluation de l'expession conditionnelle avant exécution du bloc

-> Bloc de code éventuellement jamais exécuté (si la première évaluation donne faux)• Sauf si programmation volontaire d'une boucle "infinie", dépendance du résultat de

l'évaluation de l'expression conditionnelle de "quelque chose" modifié à l'intérieur de la boucle

• Utilisation à privilégier si nombre d'itérations inconnu (possiblement 0) dès avant le début d'exécution de l'instruction itérative

Syntaxe

Langage algorithmique Langage Java

tant que condition faire

bloc

fait

while ( condition ) {

bloc }

"faire tant que"

Page 8 sur 12Algorithmique-Programmation Semestre 2 ST - Rappels du semestre 1

08/02/2017http://127.0.0.1:9000/Algo-S2/00-Rappels/Default.htm

• Exécution en boucle du même bloc de code• Poursuite avec une nouvelle exécution du bloc de code tant que le résultat de l'évaluation de

l'expression conditionnelle sur laquelle porte le "faire tant que" est vrai• Evaluation de l'expession conditionnelle après exécution du bloc

-> Bloc de code obligatoirement exécuté une fois• Sauf si programmation volontaire d'une boucle "infinie", dépendance du résultat de

l'évaluation de l'expression conditionnelle de "quelque chose" modifié à l'intérieur de la boucle

• Utilisation à privilégier si nombre d'itérations inconnu (mais au moins égal à 1) dès avant le début d'exécution de l'instruction itérative

Syntaxe

Langage algorithmique Langage Java

faire

bloc

tant que condition

do {

bloc }

while ( condition );

Analyse pré-développement

• Analyse élémentaire d'un problème concret devant être implanté informatiquement:◦ Détermination des données initiales du problème◦ Détermination des résultats finaux du problème◦ Détermination de toutes les traitements à réaliser pour, les données étant connues,

calculer les résultats

• Inclusion fréquente dans l'implantation définitive du code nécessaire à l'acquisition des données (lecture au clavier, lecture dans un fichier, lecture sur un réseau, paramètres de fonction, ...) et à l'exploitation des résultats (affichage à l'écran, sauvegarde dans un fichier, valeur retournée par une fonction, ...)

Les algorithmes

• Définition de l'ensemble des informations manipulées◦ Constantes◦ Variables

• Définition de l'ensemble des actions réalisées:◦ Acquisition des données◦ Réalisation des traitements pour établir les résultats à partir des données◦ Exploitation des résultats

Syntaxe

Langage algorithmique Langage Java

Action principale()

Déclaration des variables locales

public class NomProgramme {

public static void main(String []

args) {

Page 9 sur 12Algorithmique-Programmation Semestre 2 ST - Rappels du semestre 1

08/02/2017http://127.0.0.1:9000/Algo-S2/00-Rappels/Default.htm

Corps de l'algorithme

Fin action

Déclaration des variables

locales

Corps de l'algorithme

}

}

• En langage Java:◦ NomProgramme définit aussi le nom du fichier de code source NomProgramme.java.◦ Respect des majuscules et minuscules◦ Extension du nom de fichier: .java◦ Lettres non accentuées et chiffres autorisés (pas de chiffre au début)◦ Convention

◾ Nom intégralement en minuscule à l'exception de l'initiale en majuscule◾ En cas de nom composé, mise en majuscule de toutes les initiales de ses

composantes◦ Exemples: CalculSurfaceCercle, TestInterieurRectangle

• Exemple: Calcul et affichage de la racine carrée de x itérée n fois ( pour n = 4)

Langage algorithmique Langage Java

Action principale() (0)

Locales (1)

n : entier (1-1)

x : réel (1-1)

res : réel (1-2)

i : entier (1-3)

Ecran.afficher("n : ") (2)

n <- Clavier.saisirEntier() (2)

Ecran.afficher("x : ") (2)

x <- Clavier.saisirReel() (2)

res <- x (3)

pour i de 1 à n pas 1 faire (3)

res <- sqrt(res) (3)

fait (3)

Ecran.afficher("Valeur : ",res) (4)

Fin action (5)

public class ExempleJava {

public static void main

(String [] args) {

int n;

double x;

double res;

int i;

Ecran.afficher("n : ");

n = Clavier.saisirInt();

Ecran.afficher("x : ");

x = Clavier.saisirDouble();

res = x;

for ( i = 1 ; i <= n ; i = i+1 ) {

res = Math.sqrt(res); }

Ecran.afficherln

("Valeur : ",res);

}

}

(0) Début de l'"action principale"(1) Début de la déclaration des variables(1-1) Déclaration des données(1-2) Déclaration des résultats(1-3) Déclaration des variables de traitement(2) Acquisition des données(3) Traitement(4) Exploitation des résultats(5) Fin de l'action

Code source sauvegardé dans un fichier portant le nom du programme (aux majuscules/minuscules près) et muni de l'extension .java: ExempleJava.java

Exemple d'exécution

Page 10 sur 12Algorithmique-Programmation Semestre 2 ST - Rappels du semestre 1

08/02/2017http://127.0.0.1:9000/Algo-S2/00-Rappels/Default.htm

Débugger un programme

• Réalisation possible, avant toute compilation, d'un certain nombre de vérifications pour s'assurer de la bonne syntaxe du code source:

◦ Déclaration correcte et exhaustive de toutes les variables◦ Première opération effectuée sur toute variable: Affectation (à la déclaration ou dans

le corps de l'algorithme)◦ En langage algorithmique:

◾ Nombre de "si" égal nombre de "fsi"◾ Nombre de "faire" égal nombre de "fait"◾ Bonne utilisation du signe <- pour les affectations◾ Bonne utilisation du signe = pour les tests d'égalité◾ ...

◦ En langage Java: ◾ Attention aux majuscules et aux minuscules◾ Nombre de { égal nombre de }◾ Bon parenthésage de toutes les expressions conditionnelles canoniques et de toutes

les expressions conditionnelles composées◾ Parenthésage global de toutes les conditions utilisées dans les "if", les "while" et les

"do while"◾ Nombre de ( égal nombre de )◾ Bonne utilisation du signe = pour les affectations◾ Bonne utilisation du signe == pour les tests d'égalité◾ ...

• Contrôles automatiquement pratiqués par le compilateur Java mais s'en assurer manuellement

• Si détection d'une ou plusieurs erreurs de syntaxe lors de la compilation, toujours s'intéresser à la première erreur car les suivantes peuvent découler d'elle

• Utilisation d'un éditeur réalisant en tâche de fond le contrôle du code source-> Signalisation des erreurs de syntaxe

• En cas de fonctionnement non correct, plusieurs comportements possibles:1. "Plantage" pur et simple2. Dysfonctionnement sans plantage (i.e. le programme s'exécute mais ne réalise pas les

traitements attendus)3. Situation 1 ou 2 mais de façon aléatoire

1. -> Situer l'instruction où se produit le plantage (ligne signalée dans le message d'erreur d'exécution) et analyser le fonctionnement du code en remontant depuis cette instruction.

2. -> Analyser le fonctionnement du code.

Analyser du code

• Tracer les instructions de structuration (à la main ou par affichage écran)• Tracer les valeurs des variables (à la main ou par affichage écran)• Utilisation possible d'un "débuggeur"

Page 11 sur 12Algorithmique-Programmation Semestre 2 ST - Rappels du semestre 1

08/02/2017http://127.0.0.1:9000/Algo-S2/00-Rappels/Default.htm

Auteur: Nicolas JANEY

UFR Sciences et TechniquesUniversité de Besançon

16 Route de Gray, 25030 Besanç[email protected]

Page 12 sur 12Algorithmique-Programmation Semestre 2 ST - Rappels du semestre 1

08/02/2017http://127.0.0.1:9000/Algo-S2/00-Rappels/Default.htm