Difference between revisions of "Courses/ALGO"

From LRDE

Line 5: Line 5:
 
Enseignant (Auteur du cours) : [[Teacher::Alexandre Duret-Lutz]]
 
Enseignant (Auteur du cours) : [[Teacher::Alexandre Duret-Lutz]]
   
Période (Période du cours, pick one : S1, S2, S3, S4, S5, S6, Ing1, Ing2, Ing3, App1, App2, App3) : [[Course period::ING1]]
+
Période (Période du cours, pick one : S1, S2, S3, S4, S5, S6, Ing1, Ing2, Ing3, App1, App2, App3) : [[Course period::Ing1]]
   
 
Public (Public du cours, pick one : InfoSup, InfoSpé, Tronc-commun, Cycle ING, Majeure, Apprentis) : Tronc commun
 
Public (Public du cours, pick one : InfoSup, InfoSpé, Tronc-commun, Cycle ING, Majeure, Apprentis) : Tronc commun

Revision as of 15:26, 31 July 2013

Titre (Titre du cours) : Algorithmique

Sigle (Sigle du cours) : ALGO

Enseignant (Auteur du cours) : Alexandre Duret-Lutz

Période (Période du cours, pick one : S1, S2, S3, S4, S5, S6, Ing1, Ing2, Ing3, App1, App2, App3) : Ing1

Public (Public du cours, pick one : InfoSup, InfoSpé, Tronc-commun, Cycle ING, Majeure, Apprentis) : Tronc commun

Contrôle (Type de contrôle, pick one : Partiel, QCM, Projet, Soutenance) : Partiel

Durée (Durée du cours, pick one : 14H, 28H, 42H, 56H, 70H, 84H) : 28H

Cours Optionnel (Le cours est-il optionnel ? non, oui) : non

Module (Le module du cours) :

Prérequis (Les cours prérequis) :

Objectifs (Les objectifs du cours) : Ce cours expose les notions de base de l'algorithmique, avec une emphase sur les calculs de complexité. Les présentation des algorithmes de tris et des structures de données classiques (pour la plupart déjà introduits en prépa) sert de support à l'introduction de la notion de complexité et des différents outils mathématiques qui permettent de l'étudier.

Plan (Contenu, plan du cours) :

  • Introduction aux mesures de complexité (notations, théorème général, exemples du tri par insertion et du tri fusion)
  • Autres tri comparatifs (selection, tri par tas, tri rapide, tri introspectif)
  • Borne de complexité des tris comparatifs
  • Tris linéaires
  • Rangs et médians (sélection stochastique, sélection en O(n))
  • Structure de données classiques (tableaux statiques et dynamiques, listes, piles, files, files de priorité)
  • Structures associatives (tables de hachage, arbre binaires de recherche, arbre rouge et noir, skip lists)
  • Principaux paradigmes algorithmiques :
    • diviser pour régner (ex.: tri fusion, Karatsuba)
    • programmation dynamique (ex.: distance de Levenshtein, chaîne de multiplications de matrices, plus long sous-séquence commune)
    • algorithmes gloutons (ex.: distributeur de monnaie, codage de Huffman)

Documentation (Lien vers de la documentation) :

  • Book: "Introduction to algorithms" par Cormen, Leiserson, Rivest et Stein
  • Past exams

Support (Lien vers les transparents du cours) :

Journal (Journal du cours) : AlgoLog2010, AlgoLog2011Ing, AlgoLog2011App, AlgoLog2012Ing, AlgoLog2013Ing