Algorithmes et structures de données Patrick Reuter maître de conférences preuter

Algorithmes et structures de données

Patrick Reutermaître de conférences

http://www.labri.fr/~preuter

Déroulement

• CM mardi de 11h15 à 12h15

• TD/TP en alternance- Groupe YB (Yonel Blanc) le mardi de 16h15 à 17h45

- Groupe PR (Patrick Reuter) le mercredi de 18h30 à 20h00

Motivation

• Niklaus Wirth, ETH Zuerich, 1976« Algorithms + Data Structures = Programs »

Motivation

8.168.684.336 pages

Comment ça marche ?

Motivation

Structure de donnée:

p.ex. fantôme- couleur - position- direction- aggressif ou pas ?

Algorithmes:

p.ex. mettre a jour lemeilleur score

Motivation

Structure de donnée:

- tableau a 2 dimension

Algorithmes:

- surtout I.A.

Motivation

Structure de donnée :

File

FIFO(First In First Out)

Aussi: File à priorité

Motivation


Pile

LIFO(Last In First Out)

Motivation


Arbre(pour l’éliminationdes parties cachées)

Motivation


Graphe(pour plannifier destrajets)

AlgorithmeDéfinition Wikipedia (12/9/2005)

L'algorithmique est la science des algorithmes, visant à étudier les opérations nécessaires à la réalisation d'un calcul.

René Descartes dans le Discours de la Méthode : • « diviser chacune des difficultés que j'examinerois, en autant de parcelles

qu'il se pourroit, et qu'il seroit requis pour les mieux résoudre. ».

• Un algorithme est une méthode de résolution de problème énoncée sous la forme d'une série d'opérations à effectuer.

• La mise en œuvre de l'algorithme consiste en l'écriture de ces opérations dans un langage de programmation et constitue alors la brique de base d'un programme informatique (implémentation, « codage »)

• L'algorithme devra être plus ou moins détaillé selon le niveau d'abstraction du langage utilisé ; autrement dit, une recette de cuisine doit être plus ou moins détaillée en fonction de l'expérience du cuisinier.

http://fr.wikipedia.org/wiki/Ren%C3%A9_Descartes

http://fr.wikipedia.org/w/index.php?title=Discours_de_la_M%C3%A9thode&action=edit

http://fr.wikipedia.org/wiki/M%C3%A9thode

http://fr.wikipedia.org/wiki/Programmation

Structure de donnéesDéfinition Wikipedia (12/9/2005)

• une structure logique destinée à contenir des données afin de leur donner une organisation permettant de simplifier leur traitement.

• Exemple : On peut présenter des numéros de téléphone *

- par département, - par nom - par profession (pages jaunes),- par numéro téléphonique (annuaires destinés au télémarketing),- par rue et/ou - une combinaison quelconque de ces classements.

À chaque usage correspondra une structure d'annuaire appropriée.

Ingrédients d’algorithmes

• Variables :

nombreyi patrick x1

• Mais non pas :3xentrée


• Affectation

• Condition/Comparaison

• Appel de fonction

• Structure de contrôle– Branchements conditionnels (multiples)– Boucles

• Bloc d’instruction


• Affectation

a := 7;score := 0;score := score + 100;gameover := FAUX;

- Note:- Affectation d’une seule variable avec un valeur.- La variable à affecter figure à gauche, la valeur à droite

Faux:a+b := 6;7 := c;


• Condition/Comparaison

a = 7absent = FAUXmalade = VRAI OU vacances = VRAIscore > highscore;…

- Note:

- Le résultat d’une condition/comparaison peut être uniquement soit VRAI, soit FAUX


• Appel de fonction, p.ex.

afficher(« Bonjour tout le monde »);

resultat := racine_carre(16);


• Structure de contrôle– Branchements conditionnels

SI <condition> ALORS<bloc d’instructions>

SINON<bloc d’instructions>



SI <condition> ALORS

<bloc d’instructions>

SINON


Exemple:

SI (score>meilleur_score) ALORS

meilleur_score := score;



SI <condition> ALORS<bloc d’instructions>

SINON<bloc d’instructions>

Exemple:SI (score>meilleur_score) ALORS


En PASCAL :IF (score>meilleur_score) THEN



• Structure de contrôle– Branchements conditionnels multiples

– CAS mois DE ‘1': nom := « Janvier » ; ‘2': nom := « Février » ; ‘3': nom := « Mars » ; ‘4': nom := « Avril » ; ‘5': nom := « Mai » ;

…. ‘12': nom := « Décembre » ;

AUTREMENT afficher('Erreur dans le mois') ; FIN CAS;


• Structure de contrôle– Boucle

Définition :

Suite d’instructions qui peut être exécuté plusieurs fois (itération)



TANT QUE <condition> FAIRE<bloc d’instructions>

FIN TANT QUE

ou

FAIRE<bloc d’instructions>

TANT QUE <condition>



TANT QUE <condition> FAIRE<bloc d’instructions>

FIN TANT QUE

Exemple :Afficher les nombres entiers dont le carré est inférieur à

100.

nombre := 1;TANT QUE (nombre*nombre<100) FAIRE

afficher(nombre);nombre := nombre + 1;

FIN TANT QUE

• Faire tourner un algorithme

nombre := 1;nombrecarre := nombre * nombre;

TANT QUE (nombrecarre<100) FAIREafficher(nombre);nombre := nombre + 1;nombrecarre := nombre * nombre;

FIN TANT QUE

nombre nombrecarre

Chaque variable une colonne

nombre := 1;nombrecarre = nombre * nombre;

TANT QUE (nombrecarre<100) FAIREafficher(nombre);nombre := nombre + 1;nombrecarre := nombre * nombre;

FIN TANT QUE

nombre

1

nombrecarre

Chaque instruction une ligne

nombre = 1;nombrecarre = nombre * nombre;

TANT QUE (nombrecarre<100) FAIREafficher(nombre);nombre = nombre + 1;nombrecarre = nombre * nombre;

FIN TANT QUE

nombre

1

nombrecarre

1



FIN TANT QUE

nombre

1

nombrecarre

1



FIN TANT QUE

nombre

1

nombrecarre

1

1



FIN TANT QUE

nombre

1

2

nombrecarre

1

1



FIN TANT QUE

nombre

1

2

nombrecarre

1

4

1



FIN TANT QUE

nombre

1

2

nombrecarre

1

4

1



FIN TANT QUE

nombre nombrecarre



FIN TANT QUE

nombre nombrecarre



FIN TANT QUE

nombre nombrecarre



FAIRE


TANT QUE <condition>



FAIRE

jouer();

afficher(« Voulez vous rejouer (O/N) ? »);

prendreDuClavier(charactere);

TANT QUE (caractere= "O" OU caractere = "o");


• Structure de contrôle– Boucle POUR

POUR variable de valeur à valeur FAIRE


FIN POUR


• Structure de contrôle– Boucle POUR

POUR variable de valeur à valeur FAIRE<bloc d’instructions>

FIN POUR

Exemple

POUR i:=1 à 10 FAIREafficher(i);afficher(i*i);

FIN POUR

« FAIRE TOURNER » un algorithme

• Exemple: Tester si un nombre est premier

Stratégie: Supposer que le nombre est premier jusqu’à on a trouvé un diviseur.

FONCTION estPremier(nombre)estPremier := VRAI;Diviseur := 2;TANT QUE diviseur<nombre ET estPremier := VRAI FAIRE

SI (nombre MOD diviseur = 0) ALORSestPremier := FAUX;

FIN TANT QUEFIN FONCTION

FONCTION testSiPremier(nombre) : boolean;

estPremier := VRAI;

Diviseur := 2;TANT QUE diviseur<nombre ET estPremier = VRAI FAIRE

SI (nombre MOD diviseur = 0) ALORS

estPremier := FAUX;

diviseur := diviseur + 1;FIN TANT QUE

RETOURNER estPremier;FIN FONCTION

DiviseurestPremier

EXEMPLE: resultat = testSiPremier(9);

resultatNombre


estPremier := VRAI;

Diviseur := 2;TANT QUE diviseur<nombre ET estPremier := VRAI FAIRE


estPremier := FAUX;



DiviseurestPremier

EXEMPLE: resultat := testSiPremier(9);

resultatNombre

9


estPremier := VRAI;



estPremier := FAUX;



DiviseurestPremier

VRAI

Nombre

9


resultat


estPremier := VRAI;


SI (nombre % diviseur = 0) ALORS

estPremier := FAUX;



Diviseur

2

estPremier

VRAI

Nombre

9


resultat


estPremier := VRAI;



estPremier := FAUX;



Diviseur

2

estPremier

VRAI

Nombre

9


resultat


estPremier := VRAI;



estPremier := FAUX;



Diviseur

2

estPremier

VRAI

Nombre

9


resultat


estPremier := VRAI;



estPremier := FAUX;



Diviseur

23

estPremier

VRAI

Nombre

9


resultat


estPremier := VRAI;



estPremier := FAUX;



Diviseur

23

estPremier

VRAI

Nombre

9


resultat


estPremier := VRAI;



estPremier := FAUX;



Diviseur

23

estPremier

VRAI

Nombre

9


resultat


estPremier := VRAI;



estPremier := FAUX;



Diviseur

23

estPremier

VRAI

FAUX

Nombre

9


resultat


estPremier := VRAI;



estPremier := FAUX;



Diviseur

234

estPremier

VRAI

Nombre

9


resultat


estPremier := VRAI;



estPremier := FAUX;



Diviseur

234

estPremier

VRAI

Nombre

9


resultat


estPremier := VRAI;



estPremier := FAUX;



Diviseur

234

estPremier

VRAI

FAUX

Nombre

9


resultat

FONCTION testSiPremier(nombre)

estPremier := VRAI;



estPremier := FAUX;



Diviseur

234

estPremier

VRAI

Nombre

9


resultat

FONCTION testSiPremier(nombre)

estPremier = VRAI;

Diviseur = 2;TANT QUE diviseur<nombre ET estPremier = VRAI FAIRE


estPremier = FAUX;

diviseur = diviseur + 1;FIN TANT QUE


Diviseur

234

FAUX

estPremier

VRAI

Nombre

9


resultat

Documents

Algorithmes et structures de données Patrick Reuter maître de conférences preuter