Codes et jeux de données
Cette page permet de récupérer les programmes C et OCaml ainsi que les jeux de données utilisés en exemples dans le livre.
Codes C et OCaml du livre
Une archive pour les télécharger tous : code.zip. Ce code a été compilé avec gcc 7.5.0 (avec les options -O2 -std=c99 -pedantic -Wall sur la ligne de commande) et OCaml 4.14.0 (sans option particulière sur la ligne de commande). Ce code a été testé, mais les codes de test ne sont pas fournis. Le code C utilise ce prelude.h.
Il est possible de cliquer sur chaque fichier pour en visualiser le contenu (avec coloration syntaxique), ou d'enregistrer le fichier original en effecutant un clic droit puis « enregistrer la cible ».
Chapitre 6 - Raisonner sur les programmes (C et OCaml)
| Prélude | ||
|---|---|---|
| prelude.h | ||
| Petits algorithmes | ||
| recherche dichotomique | binary_search.c / .h | binary_search.ml |
| exponentiation rapide | arith.c / .h (power) | math.ml / .mli (power) |
| motifs et chaînes de caractères | string_search.c / .h | |
| vote majoritaire | majority.c | |
| tableaux binaires | binary_counter.c | |
| coefficients du binôme | binom.c | |
| Algorithmes de tri | ||
| tri par insertion | insertion_sort.c / .h | insertion_sort.ml |
| tri fusion | merge_sort.c / .h | merge_sort.ml |
| tri rapide | quick_sort.c / .h | |
| tri par tas | heap_sort.c / .h | heapsort.ml |
| tri par sélection | selection_sort.c / .h | |
| tri de chaînes de caractères | string_sort.c / .h | |
| tri à bulles | bubble_sort.c | |
| Induction structurelle | ||
| mobiles de Calder | calder.ml | |
| expressions arithmétiques | expr.ml | |
| manipulations de listes | lists.ml | |
Chapitre 7 - Structures de données (C et OCaml)
| Structures de données séquentielles | ||
|---|---|---|
| tableaux redimensionnables | vector.c / .h | vector.ml / .mli |
| listes chaînées | list.c / .h | |
| piles (fifo) | stack.c / .h | istack.ml / .mli |
| files (lifo) | queue.c / .h | iqueue.ml / .mli (mutable) |
| aqueue.ml / .mli (immuable) | ||
| tables de hachage | hashtbl.c / .h | hashtable.ml / .mli |
| Arbres binaires | ||
| arbres binaires | bintree.c / .h | bintree.ml / .mli |
| arbres binaires de recherche | bst.c / .h | bst.ml / .mli |
| arbres rouge-noir | rbt.ml / .mli | |
| files de priorité | pqueue.c / .h | braun.ml / .mli (immuable) |
| pqueue.ml / .mli (mutable) | ||
| skew_heap.ml / .mli (immuable) | ||
| Arbres | ||
| arbres | tree.c / .h | tree.ml / .mli |
| arbres préfixes | trie.c / .h | trie.ml / .mli |
| union-find | union_find.c / .h | union_find.ml / .mli |
Chapitre 8 - Graphes (C et OCaml)
| Structures de graphe | ||
|---|---|---|
| graphes orientés | digraph.c / .h | digraph.ml / .mli |
| graphes non orientés | graph.c / .h | graph.ml / .mli |
| graphes orientés pondérés | wdigraph.ml / .mli | |
| graphes non orientés pondérés | wgraph.ml / .mli | |
| Algorithmes et parcours | ||
| composantes connexes | components.c / .h | components.ml / .mli |
| algorithme de Floyd-Warshall | floyd_warshall.ml / .mli | |
| algorithme de Dijkstra | dijkstra.ml / .mli | |
| algorithme A* | astar.ml / .mli | |
| composantes fortement connexes | kosaraju_sharir.c / .h | kosaraju_sharir.ml / .mli |
| algorithme de Kruskal | kruskal.ml / .mli | |
| couplage maximum dans un graphe biparti | bipartite.ml / .mli | |
Chapitre 9 - Algorithmique (C et OCaml)
| Mathématiques | ||
|---|---|---|
| arithmétique entière | arith.c / .h | math.ml / .mli |
| matrices | matrix.ml / .mli | |
| Retour sur trace | ||
| Sudoku | sudoku.c | |
| N reines | queens.c | |
| Algorithmes gloutons | ||
| rendu de monnaie | greedy_change.c | greedy_change.ml |
| coloration de graphe | greedy_color.ml | |
| Diviser pour régner | ||
| plus proches points dans le plan | closest_pair.ml / .mli | |
| Programmation dynamique | ||
| pyramide d'entiers | dp_pyramid.ml | |
| rendu de monnaie | dp_change.c | dp_change.ml |
| Algorithmique des textes | ||
| Boyer-Moore | boyer_moore.c / .h | boyer_moore.ml / .mli |
| Rabin-Karp | rabin_karp.c / .h | rabin_karp.ml / .mli |
| Huffman | huffman.ml / .mli | |
| Lempel-Ziv-Welch | lzw.c / .h | lzw.ml / .mli |
| RLE (Run-Length Encoding) | rle.ml / .mli | |
| Algorithmes probabilistes | ||
| mélange de Knuth | quick_sort.c | arrays.ml |
| échantillonnage | arrays.ml (sampling) | |
| problème des N reines | queens.c (queens_prob) | |
| test de primalité | arith.c / .h | |
| génération de labyrinthe | maze.ml | |
| Apprentissage | ||
| bibliothèques pour utiliser la base MNIST | mnist.c / .h | mnist.ml / .mli |
| k moyennes | kmeans.c / .h | learning.ml / .mli |
| k plus proches voisins | learning.ml / .mli (k_nn) | |
| arbres k dimensionnels | kdtree.ml / .mli | |
| ID3 | id3.ml / .mli | |
| Jeux à deux joueurs | ||
| algorithmes min-max et alpha-beta | game.ml | |
| exemple : Othello | othello.ml | |
| exercice 172 : tic-tac-toe | tictactoe.ml | |
Chapitre 10 - Logique (OCaml)
| Manipulation de formules | |
|---|---|
| formules propositionnelles | fmla.ml / .mli |
| formes normales | cnf.ml / .mli |
| Satisfiabilité | |
| algorithme de Quine | quine.ml |
| algorithme DPLL | dpll.ml |
| modélisation du coloriage de graphes | color2sat.ml |
Chapitre 12 - Langages formels (OCaml)
| Automates | |
|---|---|
| bibliothèque d'automates | auto.ml/.mli |
| opérations sur les automates (reconnaissance, émondage, déterminisation, …) | auto_op.ml |
| Nombre de mots de longueur, k, mot de longueur k | ex_auto.ml |
| Expressions régulières | |
| bibliothèque d'expressions régulières | re.ml/.mli |
| Algorithme de Berry-Sethi, résidus de Brzozowski, élimination des états, construction de Thompson | re_algo.ml |
| Grammaires non-contextuelles | |
| Analyse syntaxique de formules logiques | prop_parser.ml |
| reconnaissance de mots du langage de Dyck | ex_gram.ml |
Chapitre 13 - Calculabilité (OCaml)
| Décidabilité | |
|---|---|
| indécidabilité de l'arrêt | barber.ml |
| équivalence sémantique | equivalence.ml |
| théorème de Rice | rice.ml |
| Réductions polynomiales | |
| transformation de Tseitin | tseitin.ml |
| réduction de 3SAT à 3COLOR | sat2color.ml / color.ml |
| Problèmes d'optimisation | |
| voyageur de commerce | tsp.ml |
| MAXSAT | maxsat.ml |
Chapitre 14 - Gestion de la concurrence et synchronisation (C et OCaml)
| Concurrence et synchronisation | ||
|---|---|---|
| algorithme de Peterson | peterson_thread.c | |
| algorithme de la boulangerie de Lamport | bakery_thread.c | bakery_thread.ml |
| producteurs et consommateurs | prod_cons_thread.c | prod_cons_thread.ml |
| dîner des philosophes | philo_thread.c | philo_thread.ml |
Code supplémentaire
| L'âne rouge (OCaml) | |
|---|---|
| L'âne rouge | ane_rouge.ml |
| Solution générique de mémoïsation (OCaml) | Mémoïsation | memo.ml / .mli |
Jeux de données
Les fichiers SQL ont été testés avec le SGBD libre PostgreSQL ainsi qu'avec l'évaluateur en ligne (basé sur SQLite).
| Description | fichier |
|---|---|
| mots anglais de cinq lettres (depuis The Stanford GraphBase) | words.txt |
| Le code SQL de création de la base de données des Films | films.sql |
| Le code SQL de création de la base de données du championnat France de football féminin | foot.sql |
| Le code SQL de création de la base de données des Étudiants | etudiants.sql |
| Le code SQL de création de tables pour la médiathèques, utilisé dans le livre NSI Terminale | livres.sql |