Courses/ALGO-TDTP

From LRDE

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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.

N'a pas eu lieu en 2020-2021. Le but est de le remplacer par des TDs/TPs tout le long de l'année, mais à cause du manque de préparation de l'école et du confinement, cela a simplement sauté en 2020-2021.

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