UE 4M017 - Algorithmique et Complexité - automne 2016 - retour

cours les jeudis de 08h30 à 10h30 de la semaine du 05/09/2016 à la semaine du 21/11/2016

travaux dirigés les vendredis de 13h45 à 16h45 de la semaine du 12/09/2016 à la semaine du 05/12/2016

partiel le jeudi 20 octobre de 08h30 à 10h30

examen 1ière session le jeudi 15 décembre 2016 de 14h00 à 17h00
examen 2ième session le jeudi 18 mai 2017 de 14h00 à 17h00

Triangulations de Delaunay et diagrammes de Voronoi, jeudis 17 et 24 novembre
Triangulations d'une famille de points du plan - triangulation de Delaunay - triangulation localement de Delaunay - Algorithme de Guibas, Knuth et Sharir - Espaces de configurations - diagrammes de Voronoi

Arbres couvrants optimaux (fin) et chemins optimaux , jeudis 10 et 17 novembre
Un arbre couvrant est de valuation minimale si et seulement si le vecteur croissant des valuations des arêtes de l'arbre est minimal composante par composante - correction de l'algorithme de Kruskal - algorithme de Dijkstra - correction de l'algorithme de Dijkstra - implémentation de l'algorithme de Dijkstra via les tas de Fibonacci (une extension des tas binomiaux)

Structure de données union-find et arbres couvrants optimaux (début) , jeudi 27 octobre et jeudi 3 novembre
Définition du problème de la gestion d'une partition - addition pondérée et identification avec ou sans compression des chemins - la fonction d'Ackermann et son inverse - analyse de complexité - arbre couvrant - arbre couvrant de valuation minimale - algorithme de Kruskal - complexité de l'algorithme de Kruskal

Arbres binaires de recherche et sélection , jeudis 6 et 13 octobre
Définition des arbres binaires de recherche - structure de données - recherche d'une clé - insertion d'une clé - arbres binaires de recherche aléatoires - profondeur d'un arbre binaire de recherche aléatoire - arbre binaire de recherche et quicksort - rotations - dynamisation des arbres binaires de recherches aléatoires : recherche, insertion et suppression d'une clé - sélection d'un élément en temps linéaire

Graphes, arbres et arbres binaires , jeudis 22 et 29 septembre
Définition d'un graphe : sommets ou nœuds, arêtes, fonction d'attachement, incidences sommet-arête - multiplicité d'une arête, arête simple, arête multiple, boucle, graphe simple, ordre d'un graphe, degré d'un sommet, feuilles - dessin de graphes - graphes isomorphes - graphes linéaires, graphes cycliques, graphes complets, graphes bipartis complets - sous-graphes, chemins et cycles d'un graphe - graphe connexe, composantes connexes d'un graphe - définition d'un arbre : un arbre est un graphe connexe sans cycles - un graphe connexe est un arbre si et seulement si pour toute paire de sommets du graphe il existe un unique chemin joignant les sommets de la paire - définition d'un graphe orienté - définition d'un arbre ordonné : un arbre ordonné est un arbre orienté dont toutes les arêtes sont orientées vers un même nœud et dont l'ensemble des arêtes est partiellement ordonné par la donnée pour chaque nœud de l'arbre d'un ordre linéaire sur ses arêtes entrantes - sous-arbres et sous-arbres immédiats d'un arbre ordonné - algébre partielle des arbres ordonnés - définition d'un arbre binaire : un arbre binaire est un arbre ordonné dont les noeuds sont de degré entrant 0 ou 2 - nœuds internes/externes, taille d'un arbre binaire, sous-arbre gauche et sous-arbre droit d'un arbre binaire, chemin de recherche d'un nœud, chemin de recherche d'un sous-arbre - profondeur d'un nœud d'un arbre binaire, hauteur d'un arbre binaire - borne supérieure sur le nombre de nœuds internes d'un arbre binaire de hauteur donné - arbres de décision associés à un algorithme de tri par comparaisons - borne inférieure sur le nombre de comparaisons d'un algorithme de tri par comparaisons - terminologie relative à la théorie des langages : mot, longueur d'un mot, longueur d'un mot en une lettre, facteur, facteur gauche, facteur droit - codage des classes d'isomorphisme d'arbres binaires par les mots de Łukasiewicz -

Tri par comparaisons , jeudis 08 et 15 septembre
Présentation succinte du cours - tri par insertion linéaire - tri par insertion dichotomique - tri fusion - tri fusion-insertion - analyse de complexité : nombre de comparaisons dans le pire des cas, nombre de comparaisons en moyenne - structure de données : piles, files, listes - borne inférieure (énoncé sans preuve) - graphes, arbres, arbres binaires (début) -