Le cours suivra le plan suivant :
Définitions, notations, pseudocode
Exemple, Pseudo-code, pseudo-code->scheme, recherche dans une liste, complexité, notations asymptotiques.
Données et information
Quelques notions de base.
Graphes et arbres
Encores des notions de base...
Automates et machines de Turing
À l’attaque des vrais fondements.
Automates II : non-déterminisme
Après les automates à états finis déterministes, les automates non-déterministes, qui sont d’ailleurs équivalents.
Expressions régulières
La suite logique des automates, auxquels elles sont équivalentes.
Accélération d’un algorithme
Recherche du maximum d’un ensemble de valeurs, memoization de Fibonacci, recherche de segments maximaux O(n3), O(n2), O(n). On attaque l’algorithmique proprement dite.
Accélération de l’algorithme de Fibonacci
Un exemple.
Tris
Algorithmes de tri par insertion, recherche de maximum dans une liste, tri fusion, tri rapide, tri linéaire.
Structures de données élémentaires
Les pile, les files, le tas et tris par tas, les arbres, arbres binaires de recherche, tables de hashage.
Recherche de mots dans un texte
Force brute, Knuth-Morris-Pratt (KMP), Karp Rabin.
Le précédent en style récursif
Instrumentation d’un programme pour l’observer : KMP
Une variation autour du précédent.
Recherche de mots dans un texte (suite)
Structures de données Les arbres de mot-clés (keyword trees), les arbres de suffixes (suffix trees).
Recherche d’un motif dans un texte
Prosite, les expressions régulières, grep, les automates à état fini, expression régulières -> automates à état finis indéterministes, déterminisation d’un automate à état fini, minimisation d’automates à état finis.
Algorithmes sur les graphes
Le métabolisme, représentation de graphe, recherche de plus court chemin, recherche d’arbre couvrant minimal.
Algorithme de Needleman et Wunsch
Alignement de séquences.
Programmation dynamique
Recherche de séquences hydrophobes, comparaison de séquence par l’algorithme de Needleman et Wunsch, par l’algorithme de Smith et Waterman, optimisation de Gotoh, multiplication de matrices : minimisation des calculs.
Recherche dans des banques de données
Blast, Fasta, les matrices PAM.
Chaines de Markov
Prédiction de modèles de gènes, prédiction de structure, représentation de motifs fonctionnels.
Des problèmes difficiles : NP-complétude
Problème de la clique, Sat, voyageur de commerce.
Solution presque optimales
Simulated anealing, algorithmes génétiques...