Courses/ALGO-TDTP

Titre	Atelier algorithmique fondamentale
Sigle	ALGO-TDTP
Enseignant	Alexandre Duret-Lutz
Période	S1, Ing1
Public	Tronc-commun
Contrôle
Durée	20h
Optionnel	non
Module	Informatique fondamentale
Prérequis	ALGO
Objectifs	L’atelier se déroule en 5 jours :Matin cours, après-midi TD suivi d'un TP sur machine.Le but de cet atelier est d'appréhender et d’appliquer les concepts de l'algorithmique par la pratique. N'a pas eu lieu en 2020-2021. Le but est de le remplacer par des TDs/TPs tout le long de l'année, mais à cause du manque de préparation de l'école et du confinement, cela a simplement sauté en 2020-2021.
Plan	Journée 1 Définition formelle des notations O, Θ, et Ω Propriétés de O, Θ, et Ω Utilisation pour le calcul de complexité Tri fusion Journée 2 Théorème général pour le calcul de complexité Application sur plusieurs exemples Tas définition et opérations (avec leurs complexités) Journée 3 Fin des algos sur le tas, et Tri par tas Quick Sort algo de base et partition avec première valeur comme pivot calcul de complexité Journée 4 calcul de complexité de Quick Sort discussion sur l'implémentation d'un quick sort tri introspectif Journée 5 Minoration du pire cas d'un tris comparatif Tris linéaires
Documentation	"Introduction to algorithms" par Cormen, Leiserson, Rivest et Stein
Support
Journaux