Courses/AlgoLog2008Ing

2008-10-10 ING1 Séance 1 (2h), Groupe B puis Groupe A

• Présentation

• Introduction des mesures de complexité
• RAM (je n'ai pas parlé de machines de Turing au groupe B)
• Problème de l'arrêt.

• Tri par insertion
• cas favorable, défavorable, moyen

• comparaisons des fonctions

• Notations \Theta, \Omega, O

• calculs de compléxité avec les notations \Theta et O

Je n'ai pas parlé des calculs simplifiés en ne comptant que les comparaisons. J'y reviendrai lors du prochain cours.

2008-10-17 ING1 Séance 2 (2h), Groupe B puis Groupe A

• Calcul simplifiés en ne comptant que les comparaisons.

• Retour sur les notations \Theta, \Omega, O
• Petits exercices de manipulation

• Complexité d'un problème (au groupe B uniquement)

• Définition d'un arbre enraciné (à partir d'un graphe)
• Définition d'un arbre binaire, d'un arbre binaire équilibré
• Propriétés sur les arbres

Puis rapidement...

• Tri fusion
• Complexité du tri fusion, avec résolution graphique, sur un arbre.

2008-10-21 ING1 Séance 3 (4h), Groupe B

• Retour sur le tri fusion et la résolution de sa complexité
• Théorème général
• Applications du théorème Général

• Complexité d'un problème (au groupe A uniquement)

• Tri par sélection

• Arbres parfaits
• Tas (insertion et suppression présentés graphiquement)
• Heapify, Build-Heap
• Heap-Sort

• Tri rapide
• Cas favorable
• Cas défavorable
• Déséquilibre 1:10 / 9:10
• Complexité moyenne

• Choix du pivot aléatoire
• Pivot médian (oralement pour le groupe A)
• Tri rapide de la libc

• Tri introspectif

2008-10-24 ING1 Séance 4 (2h), Groupe B puis Groupe A

• QCM

• résumé des complexités des tris comparatifs présentés
• borne inférieure pour les tris comparatifs

• tri par dénombrement

• tri par paquets
• calcul de la complexité moyenne du tri par paquets

2008-10-31 ING1 Séance 5 (2h), Groupe B puis Groupe A

• mélange de tableau, calcul du cas moyen sur l'algo naïf

• recherche dichotomique
• borne inférieure sur la recherche par comparaison

• recherche du minimum
• borne inférieur sur la recherche du minimum

• sélection stochastique
• cas favorable, défavorable, moyen

2008-11-07 ING1 Séance 6 (2h), Groupe B puis Groupe A

• Tri par sélection en O(1)

• QCM

• Type abstrait

• Complexité des opérations sur les tableaux (triés ou non)
• Coûts des tableaux dynamiques, complexités amorties

• Complexité des opérations sur les listes (simplement chaînées, doublement chainées, triées ou non)

• Pile, File, File à double entrée
• Tableaux circulaire pour représenter les files à double entrées
• Files de priorité

2008-11-10 ING1 Séance 7 (2h), Groupe B puis Groupe A

• Tables de hachage
• Rareté des fonctions injectives
• GPerf
• Résolution des collisions avec chaînage
• Résolution des collilsions par adressage ouvert (sondages linéaire, quadratique, double hachage)
• Réallocation des tables de hachage
• Complexité des accès

• Arbre binaire de recherche
• Parcours préfixe, infixe, suffixe

2008-11-28 ING1 Séance 8 (2h), Groupe A puis Groupe B

• Insertion et suppression dans un arbre binaire de recherche
• Complexité des opérations dans un ABR

• Définition des arbres rouge et noir
• Hauteur des arbres rouge et noir
• Insertion dans un arbre rouge et noir

• Définition des skip lists
• Algorithme d'insertion dans une skip list
• Complexité moyenne de l'insertion (au groupe B seulement)

2008-12-08 ING1 Séance 9 (2h), Groupe A puis Groupe B

• Résumé des complexité sur les structures de recherche

• Algorithmes diviser pour régner
• Multiplication de polynômes "de l'école" en \Theta(n^2)
• Multiplication de polynômes de Karatsuba en \Theta(n^{\log 3})

• Distance de Levenstein
• définition récursive
• algorithme récursif, de complexité exponentielle
• arbre des appels récursifs
• tableau des distances des suffixes pour une complexité quadratique (au groupe B seulement)

2008-12-15 ING1 Séance 10 (2h), Groupe B puis Groupe A

• Programmation dynamique
• Distance de Levenstein par programmation dynamique

• Chaîne de multiplication de matrices

• Intro de la plus longue sous-séquence commune.

2009-01-05 ING1 Séance 11 (2h), Groupe A puis Groupe B

• Plus longue sous-séquence commune.

• Algorithmes gloutons.
• Rendu de monnaie.
• Problème de la loutre (avec ou sans couteau)

• Codage de Huffman.

2009-01-12 ING1 Séance 12 (4h), Groupe A puis Groupe B

• Algorithme d'exponentiation rapide.
• Monoïdes, groupes
• Cas des matrices, polynômes
• Chaînes additives, additives/soustractives
• Éléments simplifiables d'un monoïde

(2h)

• Suite de Fibonacci
• Calcul récursif
• Programmation dynamique
• Exponentiation rapide
• Diagonalisation
• Formule de Binet

(3h)

• Plus courts chemins
• Algorithme en n^4
• Algorithme en n^3 log n (exponentiation de matrices sur un autre semi-anneau)
• Algorithme en n^3 (Floyd-Warshall)