Quelques ressources bibliographiques et liens autour du programme d'ITC, conseillés par différent·e·s collègues de l'UPS. Merci de me signaler d'autres références ainsi que les liens défectueux à «mickaelpechaud arobase protonmail point com».

🔗 : Page web
🕮 : Livre
🖵 : Poly/TP/sujet de concours

Semestre 1 (1^ère année)
Semestre 2 (1^ère année)
Semestre 3 (2^ème année)
- Un cours complet de seconde année (en version provisoire) par Jean-Pierre Becirspahic
- Bases de données
- Dictionnaires
- Programmation dynamique
- Algorithmique pour l'intelligence artificielle et l'étude des jeux

Cours complets

Un très bon cours complet de première année, de François Fayard.

Ouvrages d'algorithmique généraux

🕮 Introduction to Programming in Python (Sedgewick) Introduction encore incomplète mais très pédagogique à la programmation en Python.
🕮 Algorithmique (Cormen et al.) Un très grand classique, couvrant de nombreux points du programme. (Le lien donné est pour la version anglaise, mais le livre est également édité en français et facile à trouver).
🕮 Grokking algorithms. Une présentation simple d'algorithmes communs. (Version anglaise).
🕮 Algorithms Illuminated (Roughgarden) Une série de livres sur l'algorithmique, avec des supports videos et slides très intéressants.
🕮 Algorithms (Erickson) Une très bonne référence libre sur l'algorithmique. Beaucoup d'exemples et d'exercices intéressants. (En anglais)
Specialite NSI première et Specialite NSI terminale (Conchon, Filiâtre, et al.)

Premier semestre

Recherche séquentielle dans un tableau unidimensionnel. Dictionnaire.

🖵 Un TP sur les anagrammes : algorithmique de base dont beaucoup d'utilisation de dictionnaires (M.Péchaud).

Algorithmes dichotomiques

🔗 Page interactive sur la récursivité, dont les algorithmes dichotomiques (M.Péchaud).

Fonctions récursives

🔗 Page interactive sur la récursivité (M.Péchaud).

Matrices de pixels et images

🔗 Page interactive sur le redimensionnement «intelligent» d'images (M.Péchaud).
🖵 Un TP sur le redimensionnement «intelligent» d'images (M.Péchaud).

Tris

🔗 Page interactive sur la récursivité, traitant notamment les tris fusion et rapide (M.Péchaud).

Deuxième semestre

Terminaison, preuves, invariants

🕮 Conception d'algorithmes (Patrick Bosc, Marc Guyomard, Laurent Miclet)
Invariants, a Generative Approach to Programming (D.Zingaro): «les invariants servent à écrire des algorithmes».

Représentation des nombres

🔗 Page interactive sur la représentation des nombres entiers et flottants (M.Péchaud)

Bases des graphes, plus courts chemins

🖵 Des slides d'introduction aux graphes, introduisant divers problèmes apparentés, du vocabulaire, et des graphes «réels» (N.Pécheux)

Recherche d'un plus court chemin

Parcours de graphes, Dijkstra, A*

🕮 Artificial intelligence, a modern approach (Russell et Norvig) (version française)
🕮 Éléments d'algorithmique (Beauquier, Berstel et Chrétienne)
🕮 AI for games (Millington)
🕮 Algorithms illuminated (Tim Roughgarden)
- 🔗 Une page interactive sur les principaux algorithmes de recherche de plus courts chemins, et leurs variantes (M.Péchaud)
- 🔗 Application de la page sur les parcours à la résolution de taquin (M.Péchaud)
- 🔗 Application de la page sur les parcours à la résolution de sokoban (M.Péchaud)
- 🔗 Application de la page sur les parcours l'alignement de séquences d'ADN (M.Péchaud)
🖵 Un TP sur le jeu de taquin et la résolution de sokoban (M.Péchaud).

Troisième semestre

Bases de données

Dictionnaires et programmation dynamique

Dictionnaires, clés et valeurs. Tables de hachage

🕮 Algorithmique (Cormen et al.). Une section sur les tables de hachage.
🕮 Algorithms illuminated (Tim Roughgarden)
🔗 Une page d'introduction aux tables de hachages (M.Péchaud) avec quelques explications sur leur utilisation pour l'implémentation des dictionnaires et ensembles en Python.

Programmation dynamique

🖵 Un TP sur le chocolat empoisonné - introduisant l'intérêt de la mémoïsation, ainsi qu'informellement des notions sur les jeux d'accessibilité à deux joueurs (M.Péchaud).
🖵 Un TP sur le problème du rendu de monnaie et un problème d'occupation du sol (récursivité, programmation dynamique, algorithmes gloutons, tableaux à deux dimensions) (M.Péchaud).
🔗 Page interactive sur la récursivité, traitant de calcul par mémoïsation et de bas en haut pour Fibonacci et la distance d'édition (M.Péchaud).
Seam carving
- 🔗L'algorithme de Seam Carving est un algorithme de traitement d'images basé sur la programmation dynamique pour chercher des «chemins minimaux» dans une image, en vue de réduire sa taille. On peut également relier cela à des approches gloutonnes ou à la Dijkstra.
- 🖵 Un TP correspondant (M.Péchaud).
Alignement de séquences d'ADN, distance d'édition.
- 🔗des algorithmes d'alignement de séquences d'ADN (récursivité, programmation dynamique, plus courts chemins, A*). (M.Péchaud)
- 🖵 Un TP correspondant (M.Péchaud).

Algorithmique pour l'intelligence artificielle et l'étude des jeux

🕮 Machine Learning in Action (P. Harrington)

🕮 Apprentissage statistique (réseaux de neurones, cartes topologiques, machines à vecteurs supports) (G.Dreyfus et al.). Une bonne introduction à l'apprentissage statistique.

K plus proches voisins

🕮 Apprentissage statistique (réseaux de neurones, cartes topologiques, machines à vecteurs supports) (G.Dreyfus et al.). Les k plus proches voisins sont mentionnés dans l'introduction, comme supports à l'explication de principes d'apprentissage statistique.
🔗 Une page introductive aux k plus proches voisins, avec une application à la reconnaissance de caractères. (M.Péchaud). Adaptable en TP.
🖵 Le sujet d'info commune CCP PSI 2019 parle de k plus proches voisins et de matrices de confusion.

K moyennes

🖵 Un énoncé de TP sur les images utilisant notamment les k-moyennes pour faire du regroupement de couleurs (M.Péchaud)
🖵 Un énoncé de TP utilisant les k-moyennes pour détecter le soleil dans des images de l'eclipse de 2015 (E.Bougnol, JJ.Fleck, M.Heckmann, M.Kostyra)
🔗 Une introduction très peu technique aux k-moyennes (M.Péchaud)
🔗 Une page interactive sur une application des k moyennes au problème du regroupement des couleurs dans une image. (M.Péchaud). Adaptable en TP.

Jeux d'accessibilité à deux joueurs

🕮 AI for games (Millington)
🕮 Artificial intelligence, a modern approach (Russell et Norvig)
🔗 Techniques de théorie des jeux en informatique (Olivier Serre). Cours au MPRI.
🖵 Le sujet d'info 2007 des ENS : Graphes et jeux à deux joueurs