Rechercher Se connecter FR EN

Algorithmique et ComplexitéPrincipes de la programmation (STI)

FISA STI Semestre 5 Tronc Commun

Algorithmique et Complexité

Unité d'enseignement Principes de la programmation · AS05_PRO1  |  Code EC AS05_PRO1-2
6ECTS (UE)
1Coefficient
21:20Heures

Séquencement

C TD C TD C TD C TD C TD C TD C TD C TD

Objectifs pédagogiques

  • Savoir étudier la correction et la complexité d'un algorithme

Pré-requis

ModuleUnité d'enseignementSemestre
Mathématiques 4,3PO STI 2S4
Algorithmique et programmation 3Sciences de base 3S3
Mathématiques 1.1Sciences de base 1S1
Mathématiques 1.2Sciences de base 1S1
Algorithmique et programmation 1Eléments constitutifs Facultatifs 1S1
  • Connaissances de bases en programmation impérative
  • Manipulation des fonctions mathématiques de référence : polynômes, logarithme, exponentielle

Programme

  1. Rappels sur les pré-requis
  2. Tri par insertion : correction et complexité
  3. Récurrences : complexité des algorithmes récursifs
  4. Divide and Conquer
  5. Les arbres binaires de recherche

Modalités d'évaluation

  • Projet en groupe : étude d'un algorithme
  • Contrôle

Références bibliographiques

Introduction à l'Algorithmique. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.

Compétences

1
Réf.VerbeDescriptionNiveau
C1_1analyserun algorithme3