Vincent Nivoliers

Algorithmique, programmation et complexité

Organisation de l'UE

Cette page regroupe les documents de cours, TD et TP pour le module Lifapc, semestre de printemps. Pour le semestre d'automne, référez vous à la page de Raphaëlle Chaîne.

Intervenants

TP noté

Le sujet de TP noté est disponible sur la forge.

Projet

Le projet de cette année est sur le jeu Fresh fish.

Cours

Introduction

Cours d'introduction, de présentation de la matière, des modalités de contrôle, et de présentation du projet.

Programmation modulaire par fichier en C / C++

Cours sur le mécanisme de compilation en C / C++, et l'assemblage de morceaux de code provenants de plusieurs fichiers pour la création d'un exécutable final.

Classes de complexité

Cours introduisant la notion de classe de complexité et la notation O pour l'étude asymptotique des algorithmes.

Parcours de graphes

Cours introduisant les algorithmes principaux de parcours de graphes : parcours en profondeur, en largeur, et recherche de plus courts chemins par l'algorithme de Dijkstra et la variante A*.

Master Theorem

Cours introduisant le Master Theorem, outil essentiel pour l'analyse de la complexité des algorithmes récursifs.

Hashage

Cours introduisant les tables de hashage.

Algorithmes de tri rapides

Algorithmes de tri rapides : arbres binaires de recherche, skip-lists, tas, quicksort, tri fusion, tri par radical

TD

Rappels sur la récurrence et la récursivité

TD de rappels sur la récursivité et les preuves par récurrence. Un premier exercice sur une paire de suite imbriquées, un second classique sur la célèbre suite de Fibonacci, et un dernier classique également sur les tours de Hanoï.

Complexité des algorithmes itératifs

Calcul du nombre d'opérations réalisées dans les boucles for, application à l'analyse de complexité de deux algorithmes naïfs de tri dans le meilleur cas, le pire cas, et en moyenne.

Notations de complexité et étude de meilleur et pire cas

Notation de complexité grand 0, grand theta et grand oméga, manipulation de ces notations.

Introduction aux graphes et complexité des Skip Lists

Recherche et insertion dans une skip list, intuition de la complexité moyenne, et introduction aux parcours de graphes via un problème d'échecs.

Algorithme de Dijkstra

Application de l'algorithme de Dijkstra, étude des cas limite et de sa complexité.

Tas binaire

Gestion d'un tas binaire, et extension à la définitino du tri par tas.

AVL

Équilibrage des arbres binaires de recherche via la technique des AVL

Diviser pour régner, Master Theorem

Étude d'algorithmes de type diviser pour régner avec le Master Theorem.

Hashage

Stratégies de rehashage dans les tables de hashage et probabilité de collision.

Pivot, quicksort et quickselect

Principe du pivot, algorithmes quicksort et quickselect.

TP

Listes chaînées

Rappels sur le C et le C++, les pointeurs, les références, l'allocation dynamique, les passages de paramètres, et la définition de structures. Mise en application à la programmation de listes chaînées (rappel).

Skip Lists

Mise en place de skip lists : listes chaînées permettant d'implémenter le type set.

Union-Find

Mise en place d'une structure d'Union-Find, et application à la création de labyrinthes

AVL

Mise en place de l'équilibrage automatique des arbres binaires de recherche par la stratégie des AVL.

Annales

Vous trouverez ci-dessous une partie des anciennes interros et examens des années précédentes. Je ne fournirai pas de corrigé directement. Pour vous entraîner, faites l'interro et contactez moi (Vincent Nivoliers) pour discuter de ce que vous avez fait.

Interros de TD

TP notés

Examens