View source for 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-20 ING1 Séance 3 (4h), Groupe A ==
== 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)