Difference between revisions of "Courses/ALGO-TDTP"

From LRDE

 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
{{Course
 
{{Course
  +
|visible=Yes
 
|title=Atelier algorithmique fondamentale
 
|title=Atelier algorithmique fondamentale
 
|acronym=ALGO-TDTP
 
|acronym=ALGO-TDTP
Line 5: Line 6:
 
|period=S1, Ing1
 
|period=S1, Ing1
 
|audience=Tronc-commun
 
|audience=Tronc-commun
|duration=10H TD + 10H TP e+ 10H du cours d'ALGO
+
|duration=20h
 
|optional course=non
 
|optional course=non
 
|module=Informatique fondamentale
 
|module=Informatique fondamentale
 
|prerequisites=ALGO
 
|prerequisites=ALGO
|objectives=L’atelier se déroule en 5 jours :
+
|objectives=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.
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.
 
 
|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 15:31, 4 February 2020

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.

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