Université Côte d'azur
/ Formation / Syllabus SLEI603
Français English

ECUE IA: Algorithmique

Code de l'ECUE : SLEI603

Ce cours appartient à UE IA: Informatique fondamentale (6 ECTS) qui contient 2 ECUE
PORTAIL SCIENCES ET TECHNOLOGIES
Informatique
Campus SophiaTech Les Lucioles
Licence 3
Semestre pair
Français

PRESENTATION

Ce cours introduit la notion de complexité des algorithmes de manière pratique.

Après avoir introduit les définitions et les notations nécessaires, on étudie les solutions des problèmes classiques de l'informatique du point de vue de leur coût en temps et en mémoire.

On donne aussi des outils pour résoudre (pas forcèment de manière optimale) des problèmes d'optimisation combinatoire complexes et on discute de la qualité des solutions.

Le cours se conclut avec une étude de cas pratique.

Responsable(s) du cours

Michel Syska

Présentiel

  • 12h de cours magistral
  • 15h de travaux dirigés

PREREQUIS

Avant le début du cours, je dois ...
  • avoir suivi un cours d'introduction aux algorithmes et à la programmation, en particulier la recherche d'un élément dans une collection de données, les bases des algorithmes de tri, ...
  • savoir écrire des programmes simples en Python

OBJECTIFS

A la fin de ce cours, je devrais être capable de...
  • donner des arguments de preuve qu'un algorithme est correct
  • dire pourquoi un algorithme est meilleur qu'un autre si les deux résolvent le même problème
  • trier judicieusement les données pour les traiter plus simplement
  • appliquer les paradigmes algorithmiques classiques (force brute, glouton, diviser pour régner, programmation dynamique, ...)
  • concevoir des heuristiques pour résoudre des problèmes d'optimisation combinatoire

CONTENU

    • Définition d'un algorithme
    • Abstraction des ordinateurs : machine de Türing, modèle RAM, architecture de Von Neumann
    • Correction et terminaison d'un algorithme
    • Exemples de base : recherches et tris
    • Ordre de grandeur des fonctions usuelles et notations O, Ω, Θ
    • Complexité en temps et en espace des algorithmes classiques
    • Définition
    • Exemple de l'ordonnancement d'intervalles
    • Heuristiques gloutonnes optimales : arbres couvrants, plus courts chemins

     

    • Introduction : cas de l'ordonnancement d'intervalles pondérés
    • Autres problèmes : tous les plus courts chemins, sac à dos, ...

  • Dans cette dernière partie on verra comment il est possible de combiner les techniques énoncées précedemment pour donner des solutions (sans garantie d'optimalité) à d'autres problèmes algorithmiques classiques comme le voyageur de commerce ou à des problèmes plus complexes issus de l'industrie, de l'économie ou de la société.

    En particulier on fera le lien avec les techniques de résolution de problème utilisées en IA qui font l'objet de plusieurs ECUE du parcours L3 IA.

Accéder au Syllabus complet (Authentification requise)
Important
Ce syllabus n’a aucune valeur contractuelle. Son contenu est susceptible d’évoluer en cours d’année : soyez attentifs aux dernières modifications.