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 :

FIFO(First In First Out)

Aussi: File à priorité

Motivation

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.

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

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

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 à

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

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

nombrecarre

FIN TANT QUE

nombre

nombrecarre

FIN TANT QUE

nombre

nombrecarre

FIN TANT QUE

nombre

nombrecarre

FIN TANT QUE

nombre

nombrecarre

FIN TANT QUE

nombre

nombrecarre

FIN TANT QUE

nombre nombrecarre

FIN TANT QUE

nombre nombrecarre

FIN TANT QUE

nombre nombrecarre

TANT QUE <condition>

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

estPremier := VRAI;

estPremier := FAUX;

DiviseurestPremier

Nombre

resultat

estPremier := VRAI;

SI (nombre % diviseur = 0) ALORS

estPremier := FAUX;

Diviseur

estPremier

Nombre

resultat

estPremier := VRAI;

estPremier := FAUX;

Diviseur

estPremier

Nombre

resultat

estPremier := VRAI;

estPremier := FAUX;

Diviseur

estPremier

Nombre

resultat

estPremier := VRAI;

estPremier := FAUX;

Diviseur

estPremier

Nombre

resultat

estPremier := VRAI;

estPremier := FAUX;

Diviseur

estPremier

Nombre

resultat

estPremier := VRAI;

estPremier := FAUX;

Diviseur

estPremier

Nombre

resultat

estPremier := VRAI;

estPremier := FAUX;

Diviseur

estPremier

Nombre

resultat

estPremier := VRAI;

estPremier := FAUX;

Diviseur

estPremier

Nombre

resultat

estPremier := VRAI;

estPremier := FAUX;

Diviseur

estPremier

Nombre

resultat

estPremier := VRAI;

estPremier := FAUX;

Diviseur

estPremier

Nombre

resultat

FONCTION testSiPremier(nombre)

estPremier := VRAI;

estPremier := FAUX;

Diviseur

estPremier

Nombre

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

estPremier

Nombre

resultat

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

Documents

These Reuter

Rapport de Mémoire Application des Algorithmes Génétiques ...nakechb.free.fr/rapports_projets/rapport_algo_genetique_v_c_m1_06.pdf · Les algorithmes génétiques sont des algorithmes

Algorithmes d'approximation

Algorithmes et structures de données Cours 10 Patrick Reuter preuter

Algorithmes et structures de données avancées Partie Conception de Sites Web dynamiques Cours 10 Patrick Reuter

Algorithmes et structures de données avancées 5ème cours Patrick Reuter preuter

Algorithmes et structures de données Cours 3 Patrick Reuter preuter

Algorithmes et structures de données avancées Cours 1+2+3 Patrick Reuter maître de conférences preuter

XPos Algorithmes g n tiquesdr/XPOSE2007/iboelle_jtourret_algos_genetiqu... · ExposéSystème -IR3 2 Algorithmes génétiques Présentation • Problèmes «non classiques» • Algorithmes

Algorithmes et structures de données avancées 6ème cours Patrick Reuter preuter

Conception de Site Webs Interactifs Cours 8 Patrick Reuter preuter@labri.fr

Rendu 3D temps réel Patrick Reuter preuter@labri.fr Pour DESS Ingénierie de l'Image DESS Informatique Multimedia Patrick Reuter Version 1.2 2/10/2002

algorithmes genetiques

Patrick Reuter, LaBRI/INRIA26/03/2008 1 Les Interfaces Graphiques 27 Février 2009 Patrick Reuter Maître de conférences LaBRI/INRIA, Université Bordeaux

Conception de Site Webs Interactifs Cours 9 Patrick Reuter preuter@labri.fr

Algorithmes et structures de données Cours 8 Patrick Reuter preuter

Algorithmes et structures de données 4ème cours Patrick Reuter maître de conférences preuter

TD1 Algorithmes

Algorithmes d'optimisation

Cas cliniques Dr GEOFFRAY-Dr ISNARDON-Dr RENAUD Dr REUTER-Dr ROUDIL