Objectif : découvrir la science du calcul, en utilisant la programmation en Python pour illustrer les concepts d’algorithmes, leurs limites et leurs applications à des problèmes divers
- Introduction aux algorithmes et aux instructions Python : variables, fonctions, conditions, boucles conditionnelles, itérations avec range
- Codage des entiers (bases 2, 10 et 16), des chaînes de caractères (opérateur de concaténation) et des images
- Introduction des tableaux unidimensionnels (append, pop, concaténation, création par compréhension, pas de slice, pas d’itérateur, pas de [0]*n), algorithmes de recherche séquentielle et dichotomique, tris par insertion et fusion, notions de complexité algorithmique
- Algorithmes récursifs simples (exponentiation naïve et rapide, test de tri, recherches séquentielle et dichotomique)
- Modélisation par graphes (matrices d’adjacence) et algorithmes de parcours en largeur, coloration de graphes (algorithme glouton)
- Modélisation par arbres d’arité non bornée (à l’aide de tableaux d’associations) et algorithmes récursifs de parcours en profondeur, applications aux expressions arithmétiques, aux arborescences de fichiers et au codage de texte de longueur variable, interprétation d’un petit langage de programmation impératif
- Introduction à la programmation fonctionnelle en Python et preuve d'indécidabilité du problème de l’arrêt