Difference between revisions of "Courses/ALGO-TDTP"

From LRDE

Line 5: Line 5:
 
|period=S1, Ing1
 
|period=S1, Ing1
 
|audience=Tronc-commun
 
|audience=Tronc-commun
|duration=10h TD + 10h TP + 10h du cours d'ALGO
+
|duration=10H TD + 10H TP e+ 10H du cours d'ALGO
 
|optional course=non
 
|optional course=non
 
|module=Informatique fondamentale
 
|module=Informatique fondamentale

Revision as of 12:38, 2 July 2014

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 e+ 10H du cours d'ALGO"HTD+10HTPe+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