Nous définissons un graphe non orienté API et considérons les représentations de la matrice d'adjacence et des listes d'adjacence. Nous introduisons deux algorithmes classiques pour la recherche d'un graphe : la recherche en profondeur d'abord et la recherche en largeur d'abord. Nous examinons également le problème du calcul des composantes connectées et concluons par des problèmes et des applications connexes.

Dans ce cours, nous étudions les graphes dirigés. Nous commençons par la recherche en profondeur d'abord et la recherche en largeur d'abord dans les digraphes et nous décrivons des applications allant de la collecte des ordures à l'exploration du web. Ensuite, nous introduisons un algorithme basé sur la recherche en profondeur pour calculer l'ordre topologique d'un digraphe acyclique. Enfin, nous implémentons l'algorithme de Kosaraju-Sharir pour calculer les composantes fortes d'un digraphe.

Dans ce cours, nous étudions le problème de l'arbre couvrant minimal. Nous commençons par étudier un algorithme générique de type "greedy" pour le problème. Ensuite, nous considérons et implémentons deux algorithmes classiques pour le problème - l'algorithme de Kruskal et l'algorithme de Prim. Nous concluons par quelques applications et problèmes ouverts.

Dans ce cours, nous étudions les problèmes des plus courts chemins. Nous commençons par analyser quelques propriétés de base des chemins les plus courts et un algorithme générique pour le problème. Nous introduisons et analysons l'algorithme de Dijkstra pour les problèmes de plus courts chemins avec des poids non négatifs. Ensuite, nous considérons un algorithme encore plus rapide pour les DAG, qui fonctionne même si les poids sont négatifs. Nous concluons avec l'algorithme de Bellman-Ford-Moore pour les digraphes pondérés par les arêtes sans cycles négatifs. Nous considérons également des applications allant du remplissage en fonction du contenu à l'arbitrage.

Dans ce cours, nous introduisons les problèmes du flux maximal et de la coupe minimale. Nous commençons par l'algorithme de Ford-Fulkerson. Pour analyser sa correction, nous établissons le théorème maxflow-mincut. Ensuite, nous considérons une implémentation efficace de l'algorithme de Ford-Fulkerson, en utilisant la règle du plus court chemin augmentant. Enfin, nous considérons des applications, notamment l'appariement bipartite et l'élimination de baseball.

Dans ce cours, nous examinons des algorithmes de tri spécialisés pour les chaînes de caractères et les objets apparentés. Nous commençons par un sous-programme permettant de trier des nombres entiers dans un petit intervalle. Nous examinons ensuite deux algorithmes de tri radix classiques, les tris radix LS et MSD. Ensuite, nous considérons une variante particulièrement efficace, qui est un hybride du tri radix MSD et du tri sélectif connu sous le nom de tri sélectif radix à trois voies. Nous concluons avec le tri par suffixe et les applications connexes.

Dans cet exposé, nous examinons des algorithmes spécialisés pour les tables de symboles avec des clés de type chaîne de caractères. Notre objectif est de créer une structure de données aussi rapide que le hachage et encore plus flexible que les arbres de recherche binaires. Nous commençons par des essais à plusieurs voies, puis nous considérons des essais de recherche ternaire. Enfin, nous examinons les opérations basées sur les caractères, y compris la correspondance des préfixes et le préfixe le plus long, ainsi que les applications correspondantes.

Dans ce cours, nous examinons les algorithmes de recherche d'une sous-chaîne dans un morceau de texte. Nous commençons par un algorithme de force brute, dont le temps d'exécution est quadratique dans le pire des cas. Ensuite, nous considérons l'ingénieux algorithme de Knuth-Morris-Pratt dont le temps d'exécution est garanti linéaire dans le pire des cas. Nous présentons ensuite l'algorithme de Boyer-Moore, dont le temps d'exécution est sous-linéaire pour des entrées typiques. Enfin, nous examinons l'algorithme d'empreintes digitales de Rabin-Karp, qui utilise le hachage de manière intelligente pour résoudre la recherche de chaînes de caractères et les problèmes connexes.

Une expression régulière est une méthode permettant de spécifier un ensemble de chaînes de caractères. Le sujet de ce cours est le célèbre algorithme grep qui détermine si un texte donné contient une sous-chaîne de l'ensemble. Nous examinons une implémentation efficace qui utilise notre implémentation de l'accessibilité des digraphes de la semaine 1.

Nous étudions et mettons en œuvre plusieurs schémas classiques de compression de données, y compris le codage de longueur d'exécution, la compression de Huffman et la compression LZW. Nous développons des implémentations efficaces à partir des premiers principes en utilisant une bibliothèque Java pour la manipulation de données binaires que nous avons développée à cette fin, basée sur les implémentations de la file d'attente prioritaire et de la table de symboles des cours précédents.

Nos cours de cette semaine sont centrés sur l'idée de modèles de résolution de problèmes tels que le maxflow et le chemin le plus court, où un nouveau problème peut être formulé comme une instance de l'un de ces problèmes, et ensuite résolu avec un algorithme classique et efficace. Pour compléter le cours, nous décrivons le problème classique non résolu de l'informatique théorique qui est centré sur le concept d'efficacité des algorithmes et qui nous guide dans la recherche de solutions efficaces à des problèmes difficiles.

La quintessence du modèle de résolution de problèmes est connue sous le nom de programmation linéaire, et la méthode du simplexe pour la résoudre est l'un des algorithmes les plus utilisés. Dans ce cours, nous donnons un aperçu de ce sujet central de la recherche opérationnelle et décrivons sa relation avec les algorithmes que nous avons étudiés.

Existe-t-il un modèle universel de résolution de problèmes auquel se ramènent tous les problèmes que nous aimerions résoudre et pour lequel nous connaissons un algorithme efficace ? Vous serez peut-être surpris d'apprendre que nous ne connaissons pas la réponse à cette question. Dans ce cours, nous introduisons les classes de complexité P, NP et NP-complet, nous posons la fameuse question P = NP et nous examinons les implications dans le contexte des algorithmes que nous avons traités dans ce cours.