| Titre
|
Algorithmique et Structure de Données
|
| Sigle
|
ALSD
|
| Enseignant
|
Etienne Renault, Edwin Carlinet
|
| Période
|
S1, App1
|
| Public
|
Apprentis
|
| Contrôle
|
|
| Durée
|
20h
|
| Optionnel
|
non
|
| Module
|
Informatique Fondamentale
|
| Prérequis
|
Logique booléenne, Sommes (Sigma), Produits (Pi), Logarithmes
|
| Objectifs
|
Ce cours présente des algorithmes et structures de données fondamentales, tout en introduisant les façons d'étudier ces algorithmes. Il s'adresse à la fois à des étudiants qui découvrent l'algorithmique qu'à des étudiants, plus informés, qui ont déjà des bases d'algorithmique mais vont apprendre à faire des calculs de complexité.
|
| Plan
|
- Rappel des notions mathématiques utilisées par la suite.* 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 (min/max, sélection stochastique, sélection en O(n))* Structure de données classiques (tableaux statiques et dynamiques, listes, piles, files, files de priorité, arbres, B-arbres)* Structures associatives (tables de hachage, arbre binaires de recherche, arbre rouge et noir, skip lists)
|
| Documentation
|
- Introduction to algorithms. Cormen, Leiserson, Rivest and Stein.
|
| Support
|
|
| Journaux
|
|
