Difference between revisions of "Courses/ALGO"
From LRDE
(4 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
{{Course |
{{Course |
||
+ | |visible=Yes |
||
− | |title=Algorithmique |
||
+ | |title=Complexité des Algorithmiques |
||
|acronym=ALGO |
|acronym=ALGO |
||
|teacher=Adl |
|teacher=Adl |
||
Line 6: | Line 7: | ||
|audience=Tronc-commun |
|audience=Tronc-commun |
||
|exam type=Partiel, QCM |
|exam type=Partiel, QCM |
||
− | |duration= |
+ | |duration=24h |
|optional course=oui |
|optional course=oui |
||
|module=Informatique Fondamentale |
|module=Informatique Fondamentale |
||
− | |prerequisites=Programme Classes Préparatoires |
+ | |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. |
|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. |
||
|content=* Introduction aux mesures de complexité (notations, théorème général, exemples du tri par insertion et du tri fusion) |
|content=* Introduction aux mesures de complexité (notations, théorème général, exemples du tri par insertion et du tri fusion) |
||
Line 18: | Line 19: | ||
* Structure de données classiques (tableaux statiques et dynamiques, listes, piles, files, files de priorité) |
* 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) |
* 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) |
||
⚫ | |||
− | c) algorithmes gloutons (ex.: distributeur de monnaie, codage de Huffman). |
||
|references="Introduction to algorithms" par Cormen, Leiserson, Rivest et Stein |
|references="Introduction to algorithms" par Cormen, Leiserson, Rivest et Stein |
||
|slides=http://www.lrde.epita.fr/~adl/ens/algo/ |
|slides=http://www.lrde.epita.fr/~adl/ens/algo/ |
Latest revision as of 15:53, 14 January 2021
Titre |
Complexité des Algorithmiques |
---|---|
Sigle |
ALGO |
Enseignant | |
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 |
|
Documentation |
|
Support | |
Journaux |