| 13 septembre 2011 | Introduction à l'algorithmique avec le tri Transparents introduction à l'algorithmique Magnets à imprimer Transparents tri insertion et fusion 1) Tri insertion : algorithme, terminaison, validité, complexité en temps 2) Tri fusion : algorithme, terminaison, validité, complexité en temps |
| 20 septembre 2011 | 3) Optimalité de la complexité 4) Conclusion Démonstration qui compare le tri insertion et fusion sur un tableau aléatoire Démonstration qui compare le tri insertion et fusion sur un tableau presque trié Tri par tas Transparents tri par tas 1) Motivations 2) La structure de données "file de priorité" a) Structure de données abstraites 3) Tri par tasb) Implémentations naïves c) Tas d) Implémentation en place du tas e) Implémentation des opérations Exercice de cours Projet Algorille (si quelqu'un est intéressé, n'hésitez pas à me joindre) : exemple d'exécution du tri par tas |
| 27 septembre 2011 | Algorithme et géométrie : "applications" des tris Transparents algorithme et géométrie 1) Appartenance d'un point à un polygone a) Algorithme pour un polygone simple quelconque 2) Enveloppe convexe de n pointsb) Algorithme pour un polygone convexe a) Algorithme de Graham b) Optimalité via une réduction |
| 4 octobre 2011 | Ensembles et tableaux associatifs Transparents Ensembles et tableaux associatifs I) Structures de données abstraites Implémentations naïves Transparents arbres binaires de recherche II) Arbres binaires de recherche Plus de magnets pour les arbres binaires de recherche 1) Définition III) Arbre binaire de recherche équilibré (Adelson-Velsky-Landis)2) Opération de recherche 3) Ajout d'un élément 4) Suppression d'un élément 1) Définition et propriété 2) Ajout d'un élément et rééquilibrage avec rotations |
| 11 octobre 2011 | Transparents sur les nombres d'équilibrages IV) Table de hachageUn seul rééquilibrage 3) Suppression Plusieurs rééquilibrages Transparents table de hachage a) Source d'inspiration : tables à adressage direct b) Définitiion d'une table de hachage c) Résultats négatifs d) Exemples de fonctions de hachage e) Enoncé du problème de hachage parfait V) Conclusion générale Graphe et parcours de graphe I) Graphe 1) Définitions 2) Structure de données |
| 18 octobre 2011 | Transparents sur les applications des graphes 44 définitions de théorie des graphes Magnets pour habiller le savant Cosinus II) Parcours en profondeur Transparents pour le parcours en profondeur 1) Généralités a) Algorithme générique 2) Application : cycleb) Classification des arcs c) Lemme utile : le lemme des chemins non vus 3) Application : tri topologique a) Extensions linéaires 4) Autre application : composantes fortement connexesb) Problème du tri topologique a) Définitions b) Algorithme de Kosaraju |
| 25 octobre 2011 | Labyrinthe en parcours en profondeur III) Parcours en largeur Labyrinthe en parcours en largeur Transparents pour le parcours en largeur 1) Algorithme de parcours en largeur, distance des plus courts chemins 2) Adaptation pour un graphe pondéré positivement : algorithme de Dijkstra Exemple d'exécution de l'algorithme de Dijkstra Une `très bonne' implémentation des files de priorités : tas de Fibonacci |
| 1er novembre 2011 | VACANCES |
| 8 novembre 2011 | Programmation dynamique Transparents Problème d'optimisation (illustré avec la suite de Fibonacci) 1) Principe de mémorisation a) Chevauchement des problèmes 2) Principe de sous-structures optimalesb) Solution : Algorithme ascendant c) Autre solution : mémoïsation a) Problème du découpe de barres 3) Ingéniosité pour trouver les sous-structures optimales (illustré avec les problèmes de plus courts chemins)b) Exhiber les sous-structures optimales a) Un ennemi : les cycles de poids négatifs b) Graphe orientés acycliques pondérés et sous-structures provenant d'un tri topologique c) Graphe sans cycles négatifs : devoir "inventer" un problème qui se découpe d) Algorithme de Bellmann-Ford e) Algorithme de Floyd-Warshall |
| 15 novembre 2011 | Algorithmes gloutons Transparents 1) Principe général 2) Arbre couvrant de poids minimal a) Algorithme de Kruskal Exemple d'exécution de l'algorithme de Kruskal b) Structure union-find pour Kruskal - Implémentation en tableau - Implémentation en forêt d'arbres - Compression de chemins |
| 22 novembre 2011 | c) Algorithme de Prim 3) Glouton comme une approximation : exemple de la couverture d'ensembleFlots et programmation linéaire I) Flots a) Définitions b) Un algorithme "glouton" qui ne marche pas c) Graphe résiduel et algorithme de Ford-Fulkerson |
| 29 novembre 2011 | d) Théorème flot maximum / coupe minimum II) Programmation linéaire et réductions1) Le problème de la programmation linéaire III) Introduction à l'algorithme du simplexe2) Réductions a) Définitions b) Exemples : plus court chemins et flots (on se restreint à la forme canonique) 1) Principe général - exemple du chocolatier 2) Résolution de l'exemple a) Explication de l'algorithme sur la forme standard b) Déroulement de l'algorithme |
| 6 décembre 2011 | Des problèmes "difficiles" Transparents I) Classes de complexité P et NP 1) Intuitions II) Le pouvoir de la logique propositionnelle2) Définitions formelles avec les machines de Turing Exemple d'une machine de Turing - Fiche à compléter 3) Difficulté et réductions 1) La logique propositionnelle III) Des réductions pour montrer la NP-dureté2) La puissance du problème SAT a) Quelques applications : sudoku, coloriage etc. b) Théorème de Cook (admis) 1) 3SAT (admis) 2) Ensembles indépendants 3) Cliques |