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

ECUE IA: Algorithmique

ECUE's code : SLEI603

This course belong to UE IA: Informatique fondamentale (6 ECTS) which contains 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.

Course's manager(s)

Michel Syska

In class

  • 12h of lectures
  • 15h of directed studies

PREREQUISITES

Before the start of the course, I must ...
  • 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

OBJECTIVES

By the end of this course, I should be able to...
  • 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

CONTENT

    • 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.

Access to complete Syllabus (Authentification required)
Important
This syllabus has no contractual value. Its content is subject to change throughout this year: be aware to the last updates