Courses/ALGO-TDTP

From LRDE

Titre

Atelier algorithmique fondamentale

Sigle

ALGO-TDTP

Enseignant

Alexandre Duret-Lutz

Période

S1, Ing1

Public

Tronc-commun

Contrôle
Durée

10h TD + 10h TP (+ 10h du cours d'ALGO)"hTD+10hTP(+10hducoursd'ALGO)" is not declared as a valid unit of measurement for this property.

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.

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