Algorithmes et programmation

Objectif

Ce cours présente les bases de la programmation, puis différents algorithmes autour de domaines variés tels que les graphes, les méthodes d’optimisation numérique, les méthodes de tri, la programmation dynamique. Chaque méthode est illustrée par un programme informatique écrit en langage Python dont les concepts sont également introduits durant ce cours. Chaque séance de cours est divisée en deux parties. La première présente le langage Python, la seconde est consacrée à l’étude d’un algorithme.

Principaux acquis de la formation : 

- Les éléments de bases de tout langage impératifs (variables, boucles, test, fonction, classes).
- Notions d'algorithme : récurrence, coût d'un algorithme, programmation dynamique, dichotomie.
- Découverte d'un environnement de programmation pour un scientifique : Notebook, dataframe.

Plan

LANGAGE PYTHON

1. Manipulation des données
2. Boucles, tests, fonctions
3. Classes et programmation objet
4. Exceptions
5. Modules
6. Interface graphique

ALGORITHMES

1. Algorithmes de tri
2. Files d’attente, simulation informatique
3. Plus court chemin dans un graphe
4. Plus court chemin reliant tous les noeuds d’un graphe, cartes de Kohonen
5. Distance d’édition, distance entre deux séquences
6. Optimisation numérique, algorithmes BFGS, DFP
7. Classification à l'aide des k plus proches voisins (k-PPV), optimisation de la recherche du plus proche voisin
8. Modèles de Markov cachés et algorithme Expectation-Maximisation (EM)

Références

- Apprentissage de la programmation, Gérald Swinnen
- Précis de recherche opérationnelle, Robert Faure, Bernard Lemaire, Christophe Picouleau
- Problem Solving with Algorithms and Data Structures, Brad Miller, David Ranum