Difference between revisions of "Courses/ALGO-TDTP"

From LRDE

(Created page with "{{Course |title=Atelier algorithmique fondamentale |acronym=ALGO-TDTP |teacher=Adl |period=S1, Ing1 |audience=Tronc-commun |optional course=non |module=Informatique fondamenta...")
 
 
(5 intermediate revisions by 3 users not shown)
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)
 
|optional course=non
 
|optional course=non
 
|module=Informatique fondamentale
 
|module=Informatique fondamentale
Line 12: Line 13:
 
Le but de cet atelier est d'appréhender et d’appliquer les concepts de l'algorithmique par la pratique.
 
Le but de cet atelier est d'appréhender et d’appliquer les concepts de l'algorithmique par la pratique.
 
|content=* Journée 1  
 
|content=* Journée 1  
- Définition formelle des notations O, Θ, et Ω
+
** Définition formelle des notations O, Θ, et Ω
- Propriétés de O, Θ, et Ω
+
** Propriétés de O, Θ, et Ω
- Utilisation pour le calcul de complexité
+
** Utilisation pour le calcul de complexité
- Tri fusion
+
** Tri fusion
 
* Journée 2
 
* Journée 2
- Théorème général pour le calcul de complexité
+
** Théorème général pour le calcul de complexité
- Application sur plusieurs exemples
+
** Application sur plusieurs exemples
- Tas définition et opérations (avec leurs complexités)
+
** Tas définition et opérations (avec leurs complexités)
 
* Journée 3
 
* Journée 3
- Fin des algos sur le tas, et Tri par tas
+
** Fin des algos sur le tas, et Tri par tas
- Quick Sort
+
** Quick Sort
- algo de base et partition avec première valeur comme pivot
+
** algo de base et partition avec première valeur comme pivot
- calcul de complexité
+
** calcul de complexité
 
* Journée 4
 
* Journée 4
- calcul de complexité de Quick Sort
+
** calcul de complexité de Quick Sort
- discussion sur l'implémentation d'un quick sort
+
** discussion sur l'implémentation d'un quick sort
- tri introspectif
+
** tri introspectif
 
* Journée 5
 
* Journée 5
  - Minoration du pire cas d'un tris comparatif
+
** Minoration du pire cas d'un tris comparatif
  - Tris linéaires
+
** Tris linéaires
 
|references="Introduction to algorithms" par Cormen, Leiserson, Rivest et Stein
 
|references="Introduction to algorithms" par Cormen, Leiserson, Rivest et Stein
 
}}
 
}}

Latest revision as of 08:51, 17 March 2017

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