Difference between revisions of "Courses/ALGO"

Latest revision as of 15:53, 14 January 2021

Titre	Complexité des Algorithmiques
Sigle	ALGO
Enseignant	Alexandre Duret-Lutz
Période	Ing1
Public	Tronc-commun
Contrôle	Partiel, QCM
Durée	24h
Optionnel	oui
Module	Informatique Fondamentale
Prérequis	Programme Classes Préparatoires, piscine
Objectifs	Ce cours expose les notions de base de l'algorithmique, avec une emphase sur les calculs de complexité. La présentation des algorithmes de tris et des structures de données classiques (pour la plupart déjà introduits en classes préparatoires intégrées) sert de support à l'introduction de la notion de complexité et des différents outils mathématiques qui permettent de l'étudier.
Plan	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) Principaux paradigmes algorithmiques : a) diviser pour régner (ex.: tri fusion, Karatsuba) b) programmation dynamique (ex.: distance de Levenshtein, chaîne de multiplications de matrices, plus longue sous-séquence commune) c) algorithmes gloutons (ex.: distributeur de monnaie, codage de Huffman).
Documentation	"Introduction to algorithms" par Cormen, Leiserson, Rivest et Stein
Support	http://www.lrde.epita.fr/~adl/ens/algo/
Journaux	Courses/AlgoLog2007 Courses/AlgoLog2008Ing Courses/AlgoLog2008App Courses/AlgoLog2009Ing Courses/AlgoLog2010Ing

@@ Line 1: / Line 1: @@
+{{Course
-Titre (Titre du cours) : '''Algorithmique'''
+|visible=Yes
+|title=Complexité des Algorithmiques
-Sigle	 (Sigle du cours) : '''ALGO'''
+|acronym=ALGO
+|teacher=Adl
-Enseignant (Auteur du cours) : [[Teacher::Alexandre Duret-Lutz]]
+|period=Ing1
+|audience=Tronc-commun
-Période (Période du cours, pick one : S1, S2, S3, S4, S5, S6, Ing1, Ing2, Ing3, App1, App2, App3) : [[Course period::Ing1]]
+|exam type=Partiel, QCM
+|duration=24h
-Public (Public du cours, pick one : InfoSup, InfoSpé, Tronc-commun, Cycle ING, Majeure, Apprentis) : Tronc commun
+|optional course=oui
+|module=Informatique Fondamentale
-Contrôle (Type de contrôle, pick one : Partiel, QCM, Projet, Soutenance) : Partiel
+|prerequisites=Programme Classes Préparatoires, piscine
+|objectives=Ce cours expose les notions de base de l'algorithmique, avec une emphase sur les calculs de complexité.  La présentation des algorithmes de tris et des structures de données classiques (pour la plupart déjà introduits en classes préparatoires intégrées) sert de support à l'introduction de la notion de complexité et des différents outils mathématiques qui permettent de l'étudier.
-Durée (Durée du cours, pick one : 14H, 28H, 42H, 56H, 70H, 84H) :	 28H
+|content=* Introduction aux mesures de complexité (notations, théorème général, exemples du tri par insertion et du tri fusion)
-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
@@ Line 28: / Line 18: @@
 * 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)
+* Structures associatives (tables de hachage, arbre binaires de recherche, arbre rouge et noir)
+* Principaux paradigmes algorithmiques :  a) diviser pour régner (ex.: tri fusion, Karatsuba)  b) programmation dynamique (ex.: distance de Levenshtein, chaîne de multiplications de matrices, plus longue sous-séquence commune)  c) algorithmes gloutons (ex.: distributeur de monnaie, codage de Huffman).
-* Principaux paradigmes algorithmiques :
+|references="Introduction to algorithms" par Cormen, Leiserson, Rivest et Stein
-** diviser pour régner (ex.: tri fusion, Karatsuba)
+|slides=http://www.lrde.epita.fr/~adl/ens/algo/
-** programmation dynamique (ex.: distance de Levenshtein, chaîne de multiplications de matrices, plus long sous-séquence commune)
+|logbook=Courses/AlgoLog2007, Courses/AlgoLog2008Ing, Courses/AlgoLog2008App, Courses/AlgoLog2009Ing, Courses/AlgoLog2010Ing
-** algorithmes gloutons (ex.: distributeur de monnaie, codage de Huffman)
+|optional=non
+}}
-Documentation	 (Lien vers de la documentation) :
-* Book: "Introduction to algorithms" par Cormen, Leiserson, Rivest et Stein
-* [http://www.lrde.epita.fr/~adl/ens/algo/  Past exams]
-Support (Lien vers les transparents du cours) :
-Journal (Journal du cours) : AlgoLog2010, AlgoLog2011Ing, AlgoLog2011App, AlgoLog2012Ing, AlgoLog2013Ing

Difference between revisions of "Courses/ALGO"

From LRDE

Latest revision as of 15:53, 14 January 2021