Chronologie du cours
page d’accueil
septembre
1er septembre 2025
présentation rapide de ce qu’est l’informatique;
introduction à la ligne de commande
3 septembre 2025
introduction au SGF
commandes liées au SGF : pwd, cd, ls, mkdir, rmdir, cp,
mv, rm
i-nœuds, commande ls -i
répertoires comme entité structurante pour le passage du tableau
d’i-nœuds à l’arborescence du SGF
liens physiques et liens symboliques; commandes ln et ln -s
exemple de création d’un faux gros fichier; code: bigfile.c
espace d’adressage
droits sur les fichiers : consultation, signification et modification
6 septembre 2025
caractérisation d’un langage de programmation: paradigmes
(POO/impératif/fonctionnel)
graphe de flot de contrôle d’un programme
compilation vs. interprétation
types: définition, taille, conversions explicite et implicite, typage fort vs. typage faible
typage statique vs. typage dynamique
identifiants dans les langages de programmation
bases de C : compilation
8 septembre 2025
bases de C : flot d’un programme C et rôle de la fonction main
identifiants en C : règles
variables en C : déclaration, affectation
variables en C : portée
variables en C : portée; code :
reutilisation_identifiant.c
constantes en C (littérales et symboliques)
9 septembre 2025
fonctions en C: invocation/appel, syntaxe
fonctions en C: passage par valeurs, variables locales, valeur de
retour; code : passage_par_valeurs.c
types en C: int, unsigned int, int8_t, int32_t, int64_t,
uint8_t, uint32_t, uint64_t
bit de poids fort / bit de poids faible
complément à 2
opérations sur les entiers
norme IEEE 754 pour les nombres à virgule flottante en double
précision (début)
10 septembre 2025
norme IEEE 754 pour les nombres à virgule flottante en double
précision (fin)
opérations sur les doubles, problèmes de précision et erreurs d’arrondi
opérations entre doubles et entiers
booléens
structures de contrôle de C: conditionnelles, boucles
conditionnelles, boucles inconditionnelles
15 septembre 2025
introduction à l’algorithmique
conception d’un algorithme: entrée, sortie, problème de décision
correction: terminaison, correction partielle et totale; code :
plus_grande_puissance_de_2.c /
plus_grande_puissance_de_2.ml
efficacité: complexité temporelle, complexité spatiale
indécidabilité du problème de l’arrêt
terminaison : définition des variants de boucle
17 septembre 2025
22 septembre 2025
preuve de correction par invariant de boucle
preuve de correction par récurrence
définition des pointeurs
valeur, contenu et déréférencement d’un pointeur
24 septembre 2025
obtenir une valeur de type pointeur: NULL, adresse d’une variable,
allocation mémoire avec malloc
libération mémoire avec free
29 septembre 2025
octobre
1er octobre 2025
compter des opérations en itératif et en récursif
ordres de grandeurs : grand O, $\Theta$, $\Omega$
comparaisons et calculs des ordres de grandeurs habituels
(début)
6 octobre 2025
comparaisons et calculs des ordres de grandeurs habituels (fin)
comment définir les tailles des entrées; code : tri_bulle.c
complexités dans le pire et le meilleur des cas (définition)
Schéma général de calcul d’une complexité
étude de la complexité temporelle du tri bulle: meilleur des cas et
pire des cas; code : tri_bulle.c
8 octobre 2025
13 octobre 2025
étude de la complexité temporelle de la recherche dichotomique: meilleur des
cas et pire des cas; code : dichotomie.c
étude de la complexité temporelle du tri fusion; code : tri_fusion.c
types structurés en C : définition (struct), déclaration,
initialisateur; accès aux champs
types structurés et fonctions; code :
quadrilatere.c
15 octobre 2025
novembre
3 novembre 2025
introduction à OCaml : immuabilité, expressions
compilation et exécution OCaml : OCamlc, OCamlopt, REPL
types primitifs OCaml
définitions de variables
expressions conditionnelles
5 novembre 2025
expressions let et portée
annotation de types
fonctions anonymes
10 novembre 2025
12 novembre 2025
filtrage par motifs de listes
fonctionnement du filtrage
19 novembre 2025
filtrage profond, disjonction de motifs
20 novembre 2025 (rattrapage du 17)
exemples filtrage par motifs de listes; code :
pattern_matching.ml
types algébriques: types énumérés sans valeur; code : mois.ml
portée des constructeurs des types énumérés
motifs de filtrage pour les types énumérés
24 novembre 2025
enregistrements et leurs motifs
$n$-uplets et leurs motifs
types énumérés embarquant des données
motifs de filtrage des types énumérés embarquant des données;
code : figure.ml / liste_entiers_flottants.ml
26 novembre 2025
décembre
1er décembre 2025
3 décembre 2025
8 décembre 2025
types récursifs et polymorphes; code : liste.ml /
liste_parametree.ml
mot-clef and en OCaml pour définir des types mutuellement
récursifs
options
parenthésage (/) et begin/end
files en OCaml; code : queue.ml
10 décembre 2025
arbres binaires : définitions de base (père, frère, sous-arbre,
feuille, nœud interne, branche, arbre binaire strict, arbre binaire
complet)
lien taille / hauteur dans les divers types d’arbres binaires
implémentation des arbres binaires en C avec des pointeurs et en OCaml avec un type somme
15 décembre 2025
implémentation des arbres binaires complets sous forme de tableau
files de priorité
implémentation des files par tas max : percolation vers le bas (correction et
complexité), percolation vers le
haut, modification de valeur, insertion de valeur
17 décembre 2025
implémentation des files par tas max (suite) : extraction du
maximum, construction d’un tas (avec les complexités)