Courses/ALSD

From LRDE

Titre

Algorithmique et Structure de Données

Sigle

ALSD

Enseignant

Etienne Renault

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