Programme de colles¶

Semaines du 01/09, du 08/09 et du 15/09¶

Commandes de base d'un système Linux (cd, mkdir, ls, ...)
Traits généraux du langage C (passage par valeur, portée, typage, comportement indéfini)
Types de bases (int, float, double, char) et opérateurs associés
Opérateurs de comparaison
Tableaux statique, lecture et écriture d'un terme avec tab[i]
Instructions conditionnelles, boucle for et while
A partir du 08/09 : validation, jeu de tests, graphe de flot de contrôle
A partir du 15/09 : terminaison d'un algorithme, variant

Terminaison et correction d'algorithme simples. Les variants et invariants peuvent être suggérés aux élèves. Exemples traités en cours/TD : multiplication par addition successives, quotient et reste dans la division euclidienne, recherche de max/min dans un tableau, multiplication à la russe.
Modèle mémoire du langage C, pile, allocation dynamique dans le tas. Utilisation des opérateurs * afin d'obtenir le contenu d'une adresse et de & pour l'adresse d'une variable. Instructions malloc et free.
Ecriture en C de fonctions renvoyant un pointeur vers une zone mémoire allouée sur le tas qui sera traité comme un tableau, on pourra dire par abus de langage "fonction renvoyant un tableau"
Types structurés en C, définition et utilisation. Pointeur vers un type structurée, la notation raccourcie s->champ pour (*s).champ doit être connue.
Arguments en ligne de commande en C. Fonction atoi et atof.
A partir du 29/06 : représentation des entiers. Formats disponibles en OCaml et en C. Cas de dépassement de capacité.
A partir du 06/09 : représentation des flottants, exemples simples de conversion du type simple précision en décimal ou inversemment. Problème de fiabilité des calculs en arithmétique à virgule flottante.

Types structurés en C, utilisation de pointeurs vers de tels types.
Représentation des entiers et des flottants
A partir du 03/11 : Récursivité. Preuve de terminaison et correction d'algorithmes récursifs. Ecriture de fonctions simples en versions récursives (somme, minimum, puissance, dessins à l'aide d'instructions print). Récursivité croisée.
A partir du 10/11 : Aspects fonctionnels de OCaml. Ecriture et évaluation d'expressions en OCaml. Définition de fonctions, expressions conditionnelles. Type list, correspondance de motifs.

Manipulations de listes en OCaml. Générations récursives de listes, utilisations de List.init (avec éventuellement une fonction anonyme). Correspondances de motifs sur les listes, écritures de fonctions récursives sur les listes (minimum, recherche, ...). Utilisation de List.map, List.fold_left, List.fold_right, List.iter. On n'utilise pas List.nth.
Terminaison, correction et complexité. Complexités usuelles et exemple d'algorithmes ayant ces complexités. Définition et manipulation de la notation \(\mathcal{O}\).
A partir du 01/12 : Complexité amortie (la seule méthode vue en cours est celle du potentiel). Tableaux et listes chainées comme structure de données abstraites. Implémentation de ces structures en C et en OCaml.
A partir du 08/12 : Piles et files, et implémentations de ces structures de données à l'aide de tableaux ou de listes.

Révisions du semestre 1
Fonctions et tables de hachage, collisions, résolution par chainage ou par sondage linéaire. Exemples et applications.
A partir du 02/02 : Bases de données, clé primaire, clés étrangères, schéma relationnel. Langage sql, requête dans une ou plusieurs tables.
A partir du 09/02 : Arbres binaires, définition, vocabulaire. Relation entre nombres de noeuds et hauteur. Représentation en machine en OCaml et en C.

Parcours en profondeur préfixe, infixe et suffixe d'un arbre. Parcours en largeur.
Arbres binaires de recherche, insertion, recherche et suppression de valeurs. Complexité de ces opérations.
Caractérisation d'un arbre binaire de recherche par son parcours infixe.
Structure de tas binaire. Représentation par un tableau. Opération d'insertion et d'extraction du minimum. Utilisation pour l'implémentation d'une file de priorité. Tri par tas
Méthodes algorithmiques : force brute, retour sur trace, algorithme glouton.