Difference between revisions of "Courses/ALGO"
From LRDE
(38 intermediate revisions by 4 users not shown) | |||
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 |
||
⚫ | |||
− | |||
− | Cours Optionnel (Le cours est-il optionnel ? non, oui) : non |
||
− | |||
− | Module (Le module du cours) : |
||
− | |||
− | Prérequis (Les cours prérequis) : |
||
− | |||
⚫ | |||
− | |||
− | Plan (Contenu, plan du cours) : |
||
⚫ | |||
* Autres tri comparatifs (selection, tri par tas, tri rapide, tri introspectif) |
* Autres tri comparatifs (selection, tri par tas, tri rapide, tri introspectif) |
||
* Borne de complexité des tris comparatifs |
* Borne de complexité des tris comparatifs |
||
Line 28: | Line 18: | ||
* Rangs et médians (sélection stochastique, sélection en O(n)) |
* 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é) |
* 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 : |
||
⚫ | |||
− | ** diviser pour régner (ex.: tri fusion, Karatsuba) |
||
⚫ | |||
⚫ | |||
+ | |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) : |
||
⚫ | |||
⚫ | |||
− | |||
− | Support (Lien vers les transparents du cours) : |
||
− | |||
− | Journal (Journal du cours) : AlgoLog2010, AlgoLog2011Ing, AlgoLog2011App, AlgoLog2012Ing, AlgoLog2013Ing |
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 |