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

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