Difference between revisions of "Courses/ALGO"
From LRDE
Line 9: | Line 9: | ||
|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) |
Revision as of 20:07, 20 March 2017
Titre |
Algorithmique |
---|---|
Sigle |
ALGO |
Enseignant | |
Période |
Ing1 |
Public |
Tronc-commun |
Contrôle |
Partiel, QCM |
Durée |
28h |
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 |
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 |
|
Support | |
Journaux |