IST Syllabus L3 Programme Majeure M5b Informatique

Semestre 5

97,5 heures

UE Probabilités et statistiques pour l’informatique 24h de CM & 25h de TD

UE Algorithmique et structures de données avancées 18h de CM & 30h de TD

**********************************

UE Probabilités et statistiques pour l’informatique

Prérequis
M4a-I UE Outils mathématiques pour l’informatique, Théorie des ensembles

Compétences visées
Disciplinaires :
Acquérir des notions liées aux probabilités et variables aléatoires ainsi que leurs champs d’application.

Transversales (Soft-skills) :
Modélisation des problèmes informatiques en utilisant des outils mathématiques

Contenu du cours
Rappels sur la théorie des ensembles, éléments de probabilités, probabilités conditionnelles, variables aléatoires (discrètes et continues), lois de probabilités (discrètes et continues), théorèmes limites, Inégalité de Tchebychev, convergence en probabilités, couples de variables aléatoires.

*************************************************

UE Algorithmique et structures de données avancées

Prérequis
Module d'algorithmiques et structures de données en L2-S3

Compétences visées
-  Acquérir les fondements théoriques et pratiques des structures de données et leurs algorithmes dans le but de comprendre comment les justifier, les utiliser et les incorporer dans la résolution des problèmes. L'accent sera mis sur les propriétés fondamentales de ces structures et l'étude de leur complexité, sans toutefois négliger les aspects reliés à leurs implantations et leurs applications.
-  Étudier et comparer la complexité en temps et en espace des algorithmes itératifs et récursifs, notamment ceux qui ont une stratégie de type divisé pour mieux régner. Connaître les classes de complexité.
-  Apprendre à utiliser à bon escient les structures linéaires, hiérarchiques, les tas, les dictionnaires. Comparer des implantations différentes de ces structures de données.
-  Les exercices et les projets guidés visent à se familiariser à la résolution de problèmes.

Contenu du cours
Analyse et complexité des algorithmes : méthodes itératives et récursives. Classes de complexités.
Complexités des algorithmes fondamentaux de recherches : séquentiels et dichotomiques
Complexités des algorithmes fondamentaux de tris : insertion, sélection, fusion, rapide, …
Approfondissement du langage C :  compilation séparées, compléments sur les fonctions, programmation générique.
Compléments des listes chaînées : listes doubles chaînées, listes circulaires, listes avec sentinelles.
Algorithmes qui accompagnent les structures linéaires : parcours, recherches, insertions, suppressions, tris, etc.
Compléments des structures hiérarchiques : arbres généraux, AVL, arbres 234.
Algorithmes qui accompagnent les structures arborescences : parcours, recherches, insertions, suppressions, tris, etc.
Transformations d'algorithmes récursifs, élimination de la récursivité terminale et non terminale.
Techniques de hachage : hachage fermé, hachage ouvert, résolution des collisions, ...
Langage de programmation utilisé : langage C