Page d’accueil du cours d’algorithmique ALGO5
Merci de me signaler les oublis et les liens morts
Objectif du cours
Savoir proposer une solution algorithmique à un problème, savoir l’implanter et savoir l’analyser.- Savoir reconnaître et mettre en oeuvre des schémas génériques d’algorithmes (séquence, arbre, graphe…),
- Savoir analyser le coût des méthodes de spécification et de programmation
- Savoir construire une solution selon une démarche allant du plus simple (algorithme naïf) au plus efficace (diviser pour régner, etc.)
- Savoir comment évaluer la complexité d’une solution algorithmique:
- analyser la complexité au pire, en moyenne avec des hypothèses probabilistes,
- analyser la complexité en utilisant des mesures sur des simulations ou des jeux de test
Activités
- Cours : L’objectif du cours est d’exposer les principes fondamentaux de l’algorithmique. Le cours sera décomposé en 2 parties, une partie synthétique sur les concepts et une partie sur un algorithme classique mettant en oeuvre un schéma ou une méthode particuliers afin de se constituer une culture algorithmique de références.
Jean-Marc Vincent
- TD1 : Sous forme d’exercices sur feuille les TD1 permettent de renforcer la compréhension des concepts vus en cours.
Groupe 1 : Jean-Marc Vincent
Groupe 2 : Fabienne Carrier (coordination)
- TD2 : Les TD2 portent sur la mise en oeuvre des concepts et préparent aux activités pratiques.
Groupe 1 : Gwenaël Delaval (coordination)
Groupe 2 : Vincent Danjean
- APNEE : Les activités pratiques non encadrées permettent la validation des concepts et l’évaluation de la compréhension.
Coordination : Gwenaël Delaval
- Lecture et personnages: Des articles de culture générale et des biographies de personnalités permettent de resituer l’algorithmique dans son contexte social et historique
Quelques sujets d’examens de ces dernières années
Contenus (prévisionnel)
ATTENTION : les apnées sont indicatives, le programme définitif sera sur le placard
- Semaine 0, 10/09/2013 S37
- Cours : Présentation de l’UE, introduction à la notion de coût
- Concepts : Coût d’un algorithme, au pire, au mieux
- Algorithme classique : Drapeau hollandais
- Lecture : Computational Thinking COMMUNICATIONS OF THE ACM March 2006/Vol. 49, No. 3
- Personnage : Edsger Dijkstra (Turing Award 1972)
- Cours : Présentation de l’UE, introduction à la notion de coût
- Semaine 1, 17/09/2013 S38
- Cours :“Introduction à la notion de coût”:
- Concepts : Échelles de comparaison, ordres de grandeur, master theorem
- Algorithme classique : Exponentiation rapide
- TD1 : Calcul de coût (itérations imbriquées, recherche,…)TD1-1
- TD2 : Mesure expérimentale de la complexité TD2-1
- Personnage : Donald E. Knuth (Turing Award 1974)
- Cours :“Introduction à la notion de coût”:
- Semaine 2, 24/09/2013 S39
- Cours : Analyse en moyenne
- Concepts : Algorithme optimal, Analyse en moyenne, tri rapide
- Algorithme classique : Analyse du nombre d’affectations dans le calcul du maximum
- Note de cours sur la complexité
- TD1 : Calcul de coût moyen TD1-2
- TD2 : À propos de tableaux: TD2-2
- APNEE Maximum Sujet
- Lecture : The Algorithm: Idiom of Modern Science Bernard Chazelle, Princeton
- Cours : Analyse en moyenne
- Semaine 3, 1/10/2013 S40
- Semaine 4, 8/10/2013 S41
- Semaine 5, 15/10/2013 S42 (++)
- Cours : Complexité de la recherche en table
- Concepts : Table de hachage (ouvert et fermé)
- Algorithme classique : Algorithme de Bucket-sort
- TD1 : Problème du collecteur de coupons TD1-5
- TD2 : Implémentation de tables de hachage TD2-5
- QUICK : Sujet corrigé
- APNEE Hachage Sujet
- Personnage : Larry Wall
- Cours : Complexité de la recherche en table
- Semaine 6, 22/10/2013 S43
- S44 Interruption pédagogique VACANCES
- Semaine 7, 5/11/2013 S45
- S46 CONCOURS DE PROGRAMMATION
- Semaine 8, 19/11/2013 S47
- Semaine 9 26/11/2013
- Cours : Arbres de codage
- Concepts : Inégalité de Kraft, Codage optimal, entropie
- Algorithme classique : Algorithme de Huffman Transparents Notes de cours
- TD1 : Comptages dans les arbres
- TD2 : Type abstrait Arbre TD2-9
- APNEE :
- Personnage : Claude Shannon
- Cours : Arbres de codage
- Semaine 10 3/12/2013
- Cours : Précalcul
- Concepts : Automate de reconnaissance
- Algorithme classique : Algorithme de Knuth-Morris-Pratt
- TD1 : Arbres partiellement ordonnés
- TD2 : Implémentation Arbre n-aire à partir d’un type Arbre Binaire
- APNEE :
- Personnage :
- Cours : Précalcul
- Semaine 11 10/12/2013
- Cours : Synthèse sur les arbres
- Concepts : Automate de reconnaissance
- Algorithme classique : Algorithme de Knuth-Morris-Pratt
- TD1 : Algorithme de Heap-sort
- TD2 : Dictionnaire arborescent (recherche/insertion/supression)
- APNEE :
- Personnage :
- Cours : Synthèse sur les arbres
