[PDF] Cours dAlgorithmique - Florent Hivert

View - Download Cours dAlgorithmique - Florent Hivert

Previous PDF

Next PDF

1 de 16

Cours d"Algorithmique

Florent Hivert

Mél :Florent.Hivert@lri.fr

Adresse universelle :http://www.lri.fr/˜hivert

2 de 16

Informations pratiques

25heures de cours;

25heures de travaux dirigés;

Évaluation :

2 contrôles + examen final + mini projets.

3 de 16

Plan du cours

1Introduction;2Notion de complexité;3Tableaux et type de donnée abstraîts;4Listes chaînées;5Trouver et trier;6Arbres;

4 de 16

Généralités sur le traitement de l"information Les ordinateurs sont utilisés pourle traitement d"informations; le stockage d"informations.

5 de 16

Généralités sur le traitement de l"information (2) Le schéma global d"une application informatique est toujours le même :RéceptionTraitement desÉmission d"informationsinformationsd"informations déduites Exemple:réception desomme de cesnvaleursémission de la nvaleurs!et division!moyenne numériquesdu résultat parnarithmétique

6 de 16

La notion de programme

Tout traitement demandé à la machine, par l"utilisateur, est effectué par l"exécution séquencée d"opérations appelées instructions. Une suite d"instructions est appelée unprogramme.Retenir Un programme est unesuite d"instructionspermettant à une

système informatique d"exécuter une tâche donnéeécrit dans un langage de programmation compréhensible

(directement ou indirectement) par un ordinateur.

Données

=)Programme=)Résultats

7 de 16

Qu"est-ce que la programmation?

Retenir

Écriture d"unprogrammedans un langage de programmation donnée. Langage de programmation: ensemble de règle de vocabulaire et de grammaire compréhensible par un ordinateur.int fun(int x) { x = x + 1; return x; void main(void) { printf("%i", fun(2));

8 de 16

La notion d"algorithme

Pour résoudre un problème de manière informatique il y a un cheminement méthodique à respecter :

Énoncé Programme

Problème! !Algo.! !Résultats

algo. (instructions)

9 de 16

La notion d"algorithme (2)

Définition (Notion d"Algorithme)description formelle d"unprocédé de traitementqui permet, à partir d"un ensemble d"informations initiales, d"obtenir des informations déduites;succession finie et non ambigüe d"opérations;

se termine toujours(Note : semi-algorithme).Définition (Notion de Programme)suite d"instructions définies dans un langage donné;

décrit un algorithme.

10 de 16

11 de 16

12 de 16

Exemple d"algorithme

Algorithme (Calcul de la moyenne d"un tableau de notes) Entrées : un entier n, un tableau de n nombres à virgules

Sorties : la moyenne des nombres du tableau

i est un entier; s un nombre à virgule. initialiser s avec 0 pour i de 1 à n faire ajouter le i-ème élement du tableau à s retourner s=n

12 de 16

Exemple d"algorithme

Algorithme (Calcul de la moyenne d"un tableau de notes) Entrées : un entier n, un tableau de n nombres à virgules

Sorties : la moyenne des nombres du tableau

i est un entier; s un nombre à virgule. initialiser s avec 0 pour i de 1 à n faire ajouter le i-ème élement du tableau à s retourner s=nQuel est le nombre d"additions effectuées par cet algorithme?

13 de 16

Différentes problématiques

terminaison: terminera en un temps fini.complexité en temps: terminera en un temps borné (raisonnable).complexité en espace: terminera en utilisant une quantité de mémoire bornée (raisonnable).correction: si l"algorithme termine en donnant une

proposition de solution, alors cette solution est correcte.complétude: pour un espace de problèmes donné,

l"algorithme, s"il termine, donnera toujours des propositions de solutions.

14 de 16

Pourquoi faire

" I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships. " - Linus Torvalds (creator of Linux) " Algorithms + Data Structures = Programs. " - Niklaus Wirth

15 de 16

Objectifs du cours d"algorithmique

Concevoir des algorithmes simples;

Analyser les performances d"un algorithme :

notion de complexité;Algorithmes fondamentaux : description et complexité;

Structures de données performantes :

tableaux dynamiques, tableaux triés, listes chaînées, arbres, tables de hachage. Choisir la bonne structure de donnée selon l"application!!!

15 de 16

Objectifs du cours d"algorithmique

Concevoir des algorithmes simples;

Analyser les performances d"un algorithme :

notion de complexité;Algorithmes fondamentaux : description et complexité;

Structures de données performantes :

tableaux dynamiques, tableaux triés, listes chaînées, arbres, tables de hachage.Choisir la bonne structure de donnée selon l"application!!!

16 de 16

Bibliographie

Mots clés : algorithmique, analyse d"algorithmes.Cormen, Leiserson, Rivest et Stein,Algorithmique : Cours avec

957 exercices et 158 problèmes, (trad. de l"anglais) Dunod,

2010.Knuth,The Art of Computer Programming (TAOCP)

Vol 1.-5., Addison-Wesley, Boston.Graham, Knuth et Patashnik,Mathématiques concrètes, Fondations pour l"Informatique, International Thomson publishing France, 1998.Froidevaux, Gaudel et Soria,Types de données et algorithmes

McGraw-Hill 1990- Ediscience International 1993, 577 pagesGranjon,Algorithmes en Pascal et en langage C, Dunod, 2004.

quotesdbs_dbs45.pdfusesText_45

[PDF] Algorithme ; Fonction ; f(x) 2nde Mathématiques

[PDF] Algorithme ? faire Terminale Mathématiques

[PDF] Algorithme ? programmer Terminale Mathématiques

[PDF] algorithme ? réaliser 2nde Mathématiques

[PDF] Algorithme ? trouver 1ère Mathématiques

[PDF] Algorithme Abonnement DVD 2nde Mathématiques

[PDF] algorithme algobox exemple PDF Cours,Exercices ,Examens

[PDF] algorithme algobox seconde PDF Cours,Exercices ,Examens

[PDF] algorithme algobox suite PDF Cours,Exercices ,Examens

[PDF] Algorithme angle orienté 1ère Mathématiques

[PDF] algorithme avancé et complexité exercices corrigés PDF Cours,Exercices ,Examens

[PDF] algorithme avec algobox PDF Cours,Exercices ,Examens

[PDF] Algorithme avec des congruences Terminale Mathématiques

[PDF] Algorithme avec exemples 2nde Mathématiques

[PDF] Algorithme avec un triangle isocèle 2nde Mathématiques