Polycopié

Le polycopié du cours, au format PDF

Les transparents du premier cours, au format PDF

Mes notes de cours (qui recouvrent partiellement le poly) au format PDF

Spécifications algébriques

Spécification axiomatique des booléens.

Spécification récursive des listes, extension d'une spécification.

TD n°1 sur les spécifications algébriques

Approche objet :
specifications, classes abstraites et implémentations concrètes

Points

  - Point.java
  - CartesianPoint.java
  - PolarPoint.java

Date

  - Date.java
  - StructDate.java
  - FieldDate.java

Types de données élémentaires

La présentation de ces types est l'occasion de montrer comment passer d'une spécification à une classe abstraite, puis d'étudier les représentations classiques à l'aide de tableaux et de structures chaînées, et d'évaluer leurs avantages et inconvénients en termes d'occupation de la mémoire et de performances des différentes opérations.

Bag (ensemble avec occurrences multiples possibles)

  - Bag.java
  - ArrayBag.java
  - LinkedBag.java

Queue (file d'attente FIFO)

  - Queue.java
  - LinkedQueue.java
  - BufferQueue.java tampon circulaire

Stack (pile LIFO)

  - Stack.java
  - LinkedStack.java
  - ArrayStack.java

Première étude de laboratoire : listes chaînées

Utilisation de piles pour l'évaluation d'expressions arithmétiques par l'algorithme de Dijkstra

  - DijkstraEval.java évaluation d'expressions arithmétiques à l'aide de 2 piles.

Heap (tas pour files de priorités) et tri par tas

  - Heap.java (avec méthode sort pour le tri par tas)
  - MinHeap.java
  - MaxHeap.java

TD n°2 : complexité et tri rapide

Une vidéo illustrant le déroulement du tri rapide : http://www.youtube.com/watch?v=ywWBy6J5gz8

BinaryTree (arbres binaires)

  - BinaryTree.java
  - TreeCursor.java (position dans un arbre binaire)
  - LinkedBinaryTree.java (implémentation avec nœuds)
  - TreeWalk.java (parcours d'arbres binaires)

Forest (forêts, arbres planaires)

  - Forest.java
  - ForestCursor.java (position dans une forêt)
  - LinkedForest.java (implémentation avec nœuds)
  - ForestWalk.java (parcours de forêts)

Associative arrays (dictionnaires)

  - AssociativeArray.java
  - ListAssocArray.java (implémentation simple par liste)
  - BTreeAssocArray.java (arbres binaires de recherche)
  - SearchTest.java (test des algos de recherche)

Code des collections présenté dans le polycopié (ne sont plus traitées en cours depuis 2012)

Cette archive contient le code source des collections (listes, arbres et graphes) présenté dans le polycopié.

Illustration du déroulement d'un algorithme à essais successifs

Le problème du placement de huit reines sur un échiquier sans qu'aucune ne soit en position d'être prise permet de percevoir la recursivité de l'algorithme, la profondeur de récursion correspondant ici à la ligne sur laquelle on cherche à placer une reine.

Visualiser le déroulement de l'algorithme