Voir la source de INFO510 : Algorithmique : structures de données complexes

Cours du semestre 5 de la licence STIC TRI et ESET.

Responsable INFO510 (2016-2017): Xavier Provençal


== Examen 1ere session ==
 - [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/examen.pdf Sujet de l'examen]
 - [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/correction.pdf Correction de l'examen]



== Notes de cours ==
 - [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/notes-de-cours.pdf Notes de cours]


== Aide pour l'examen ==
 - La feuille suivante vous sera remise lors de l'examen : [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/entetes.pdf entetes.pdf]

<!--
== Examen 1ere session 2015-2016 ==

#* [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/examen.pdf Énoncé]
#* [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/solution.pdf Solution]
-->

== Feuilles de TD ==

- [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/td1.pdf Première feuille de TD]

- [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/td2.pdf Deuxième feuille de TD]

- [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/td3.pdf Troisième feuille de TD]

- [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/td4.pdf Quatrième feuille de TD] [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/td4-sol.pdf Solution à 1a) et 1b).]

- [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/td5.pdf Cinquième feuille de TD]

<!--
#* [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/td0.pdf Feuille d'exercices "En attendant le premier TD"]
#* [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/td1.pdf Première feuille de TD, structures de contrôle, tableaux et chaînes de caractères]
#* [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/td2.pdf Deuxième feuille de TD, Algorithmes de tri]
#* [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/td-tris.c td-tris.c (sources à télécharger)]
#* [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/timeUtil.h timeUtil.h (sources à télécharger)]
#* [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/td-listes.pdf Troisième feuille de TD : listes]
-->

== Énoncés des TP ==

TP1 : Labyrinthes
 - [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/info510-tp1.pdf Énoncé au format pdf]
 - [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/info510-tp1.zip Code source]


TP2 : k-Moyennes
 - [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/info510-tp2.pdf Énoncé au format pdf]
 - [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/info510-tp2.zip Code source]



<!--
TP2 : Liste, Files, Piles !
Commencez par télécharger le fichier ci-dessous, extraire son contenu et compiler le programme. Ce TP est composé de 5 exercices. Chacun de ces exercices est décrit dans les commentaires de la fonction '''main'''.
 - [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/info510-tp2.zip info510-tp2.zip]


TP3 : Calcul d'enveloppe convexe.
 - [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/info510-tp3.pdf Énoncé du TP (info510-tp3.pdf)]
 - [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/tp3.c Fichier source tp3.c]
 - [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/Point.h Fichier source Point.h]
 - [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/DoubleFile.h Fichier source DoubleFile.h]
 - Si vous n'avez pas confiance en votre implémentation de listes réalisée au TP2, utilisez celle-ci : [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/Liste.h Fichier source Liste.h]
-->

== Déroulement INFO510 (2016/2017) ==

Cours 1 : Introduction et description du langage de pseudo-code.
 - Qu'est-ce que l'algorithmique ? 
 - Démarche "Problèmes -> Programme"
 - Types de base
 - Structures de contrôle
 - Types complexes (tableaux et entités)

Cours 2 : Fonctions et chaines de caractères
 - Fonctions
 - [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/langage.pdf Résumé du langage Pseudo-Code.]
 - Type abstrait
 - Chaine de caractères

Cours 3 : Récursivité
 - Récursivité : principe, exemples et trace.
 - Cas d'étude : calculette ( notation polonaise, lecture d'entiers )

Cours 4 : Files et Piles (1/2)
 - Type abstrait File, définition, fonctionnement et exemple.
 - Type abstrait Pile, définition, fonctionnement et exemple. 
 - Implémentation du type Pile.

Cours 5 : Files et Piles (2/2)
 - Solution au problème "bien parenthésé" en utilisant une pile.
 - Implémentation du type File via un tableau circulaire.

Cours 6 : Type abstrait Ensemble.
 - Implémentation du type Ensemble par un tableau non-trié.
 - Implémentation du type Ensemble par un tableau trie et recherche dichotomique.

== Quelques ressources pour l'étudiant ==

Attention, ces ressources ne servent que de compléments pour les modules INFO510 et ne remplacent en aucun cas les cours, TDs et TPs.

0. Présentation du premier cours [http://www.lama.univ-savoie.fr/~provencal/enseignement/INFO510/INFO510--intro.pdf Diaporama].

1. Notes de cours d'autres enseignants.
#* Notes de cours de Jacques-Olivier Lachaud (responsable du module de 2007 à 2011) : [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Cours/notes-de-cours.pdf Fichier pdf].
#* cours Algo de Eric Sopena, Univ. Bordeaux 1, partie I [http://www.lama.univ-savoie.fr/~lachaud/Cours/INFO510/Cours/cours-ES-1.ps Fichier PostScript]


<!--
* 2013-2014 : Xavier Provençal (C/TD/TP), Louis Cuel (TD/TP)
* 2012-2013 : Xavier Provençal (C/TD/TP), Louis Cuel (TD/TP)
* 2011-2012 : Jacques-Olivier Lachaud (C/TD/TP), Louis Cuel (TD/TP)
* 2010-2011 : Jacques-Olivier Lachaud (C/TD/TP), Mouhammad Said (TD/TP)
* 2009-2010 : Jacques-Olivier Lachaud (C/TD/TP), Laurent Boyer (TD/TP)
* 2008-2009 : Jacques-Olivier Lachaud (C/TD/TP), Laurent Boyer (TD/TP)
* 2007-2008 : Jacques-Olivier Lachaud (C/TD/TP)
-->
== Historique ==

=== Déroulement INFO510 (2015/2016) ===
* Cours 1 : Introduction et description du langage de pseudo-code.                   
* Cours 2 : Description du langage de pseudo-code (suite et fin)         
* Cours 3 : Exercices         
* Cours 4 : Algorithmes de tri simples         
* Cours 5 : Tri (suite)         
* TD1 : Feuilles "Quelques exercices en attendant les TD" et première feuille de TD.         
* Cours 6 : Tri (suite et fin), TAD         
* Cours 7 : TAD (suite et fin)

=== Déroulement INFO510 (2014/2015) ===
* Cours 1 : Qu'est-ce que l'algorithmique ? Problèmes -> Programme. Types et structures de contrôle.
* Cours 2 : Types complexes (tableaux, entités), Action/Fonctions (I).
* Cours 3 : Actions/Fonctions (II), récursivité, algorithmes sur les tableaux (I).
* Cours 4 : Tris simples.
* Cours 5 : Tri rapide.
* TD1 : Puissance 4 en salle machine (TP0)
* Cours 6 : Tri rapide (suite et fin). TAD : les listes.
* Cours 7 : Première implémentation de listes : premières cases d'un tableau.
* TD2 : Manipulation de listes.
* TD3 : Implémentation de listes : listes chaînées.


=== Déroulement INFO510 (2013/2014) ===
* Cours 1 : Qu'est-ce que l'algorithmique ? Problèmes -> Programme. Types et structures de contrôle.
* Cours 2 : Types complexes (tableaux, entités), Action/Fonctions (I).
* Cours 3 : Actions/Fonctions (II), récursivité, algorithmes sur les tableaux (I).

* TD 1 : Exercies sur les tableaux (I).
* Cours 5 : Tri rapide.
* TD 2 : Puissance 4, exercies sur les tableaux (II).
* TD 3 : (salle machine) Implémentation du Puissance 4.
* Cours 6 : Types de données abstraits, listes (I) : utilisation.
* Cours 7 : Listes (II) : implémentation par tableaux, implémentation par listes chaînées.
* TD 4 : Exercices sur les tris simples.
* TD 5 : Exercices sur le tri rapide et l'utilisation de listes.
* TP1 : tris
* TD 6 : Types abstraits de données.

<!--
=== Déroulement INFO510 (2012/2013) ===
* (Cours 1) 18 septembre : Qu'est-ce que l'algorithmique ? Problèmes -> Programme. Types et structures de contrôle.
* (Cours 2) 21 septembre : Types complexes (tableaux, entités), Action/Fonctions (I).
* (Cours 3) 25 septembre : Actions/Fonctions (II), récursivité, algorithmes sur les tableaux (I).
* (TD 1) 28 septembre : Exercies sur les tableaux (I).
* (Cours 4) 1 octobre : Fouille dichotomique, tri simples (I).
* (TD 2) 5 octobre : Puissance 4, exercies sur les tableaux (II).
* (Cours 5) 9 octobre : Tri simples (II), tri fusion, tri rapide (I).
* (Cours 6) 17 octobre : Tri rapide (II), types de données abstraits, liste (I).
* (TD 3) 22 octobre : (salle machine) Implémentation du Puissance 4.


=== Déroulement INFO510 (2011/2012) ===


* (Cours 1) jeudi 15 septembre : Qu'est-ce que l'algorithmique ? Correction + Compromis vitesse / mémoire. Rappels d'algorithmique élémentaire (I).
* (Cours 2) lundi 19 septembre : Rappels d'algorithmique élémentaire (II). Types complexes (Tableaux, Entités). Actions/Fonctions (I).
* (Cours 3) mardi 19 septembre : Actions / Fonctions (II). Récursivité. Algorithmique sur les tableaux. (I).
* (TD 1) mardi 19 septembre et mercredi 20 septembre : TD 1 - Exercices sur actions/fonctions et tableaux.
* (TD 2) vendredi 23 septembre : TD 1 - Exercices sur actions/fonctions et tableaux (II)
* (Cours 4) mercredi 28 septembre : Tri (I). Tris de base.
* (Cours 5) vendredi 30 septembre : Tri (II). Tri rapide.
* (Cours 6) mardi 4 octobre. Structures séquentielles: listes.
* (TD 3) mercredi 5 octobre. TD machine. TP0 - Années bissextiles, Puissance 4.
* (Cours 7) jeudi 6 octobre. Structures séquentielles: listes (fin). Piles. Files.
* (TD 4) jeudi 6 octobre. fiche TD 3 : Tri. Dichotomie. Tri sélection. Pire cas quicksort et randomisation.
* (TP 1) jeudi 13 octobre. TP 1 : Tri.
* (TD 5) vendredi 7 octobre.


=== Déroulement INFO510 (2010/2011) ===

* (Cours 1) lundi 4 octobre : Qu'est-ce que l'algorithmique ? Correction + Compromis vitesse / mémoire. Rappels d'algorithmique élémentaire (I).
* (Cours 2) mercredi 6 octobre : Rappels d'algorithmique élémentaire (II). Types complexes (Tableaux, Entités). Actions/Fonctions (I).
* (TD 1) lundi 11 octobre : Exercices sur actions/fonctions et tableaux.
* (Cours 3) mercredi 13 octobre : Actions / Fonctions (II). Récursivité. Algorithmique sur les tableaux. (I).
* (Cours 4) mercredi 13 octobre : Tri (I). Tris de base.
* (Cours 5) mardi 19 octobre : Tri (II). Tri rapide. Sélection.
* (Cours 6) vendredi 22 octobre : Structures séquentielles (I). Principe. Pile. File.
* (TD 2) vendredi 22 octobre :  TD machine (TP0)
* (TD 3) mardi 2 novembre : Exercices sur actions/fonctions et tableaux.
* (Cours 7) mercredi 3 novembre : Structures séquentielles (II). Files à double entrées. Listes.
* (TD 4) mercredi 3 novembre : Exercices autour des tris.
* (TD 5) vendredi 5 novembre : Exercices sur listes. Implémentation des listes par tableaux avec chaînage.
* (TD 6) lundi 8 novembre : Applications des structures séquentielles. Hachage.
* (TD 7) mercredi 10 novembre : Applications des structures séquentielles. Radix-tri, tri fusion.
* (TP 1) vendredi 12 novembre : TP sur les tris.
* (TP 2) vendredi 12 novembre : TP sur les files à double-entrée. Application au calcul de l'enveloppe convexe. (I)
* (TP 3) mercredi 17 novembre : TP sur les files à double-entrée. Application au calcul de l'enveloppe convexe. (II)
-->