UE I5-A - Algorithmique et mathématiques 1

Ce cours présente une initiation à la résolution de problèmes simples au moyen de l'algorithmique, en particulier les problèmes de tris. Les seuls objets manipulés sont de types simples (entiers, réels,etc) ou tableaux et matrice de ceux-ci. Quelques familles d'algorithmes sont introduites: diviser pour régner, dynamiques et gloutons. La comparaison d'algorithmes est abordée par l'introduction de la notion de complexité.

Introduction
Notions de problèmes et d'algorithmes
Algorithme Diviser pour Régner
Programmation Dynamique
Algorithmes gloutons
Problème du Tri

Voir la page complète

Ce cours rappelle quelques structures mathématiques usuelles (ensemble, séquence et arbre), introduit la notion de type abstrait et fournit quelque méthode pour les implémenter.

Voir la page complète

Dans la première partie, il s'agit d'étudier les notions de base du calcul des probabilités, qui seront utilisées dans d'autres enseignements à l' ENSEIRB : Recherche opérationnelle, Traitement du signal, Théorie de l'information, Analyse des données, Algorithmique probabiliste et surtout les Statistiques étudiées dans la deuxième partie de ce module.

Introduction: probabilité sur un espace fini
Variables aléatoires discrètes
Variables aléatoires à densité
Convergences et théorèmes limites

Voir la page complète

L'objectif est l'acquisition des outils théoriques permettant de construire un raisonnement formel, ainsi que de prouver la terminaison et la correction des algorithmes.

La première partie présente la logique propositionnelle puis la logique du premier ordre comme langages formelles de spécification. L'élève-ingénieur apprend à formaliser un problème et à utiliser un solveur pour obtenir une solution.
La seconde partie concerne la théorie de l'induction, la définition de types inductifs et la preuve par induction, notamment de fonctions récursives
La troisième partie traite de la preuve de programmes itératifs: spécification (pre/post condition), terminaison, invariant de boucle, calcul de Hoare

Voir la page complète

Voir la page complète

Objectifs :
Acquisition des concepts et des outils de bases pour le traitement de données :
- Données quantitatives (numériques) : Analyse en Composantes Principales (ACP)
- Données qualitatives (catégories) : Analyse Factorielle des Correspondances (AFC)
- Introduction à l'apprentissage automatique: apprentissage non supervisé (clustering) et supervisé (classification, régression)

Compétences:
- Connaître les principe de base du traitement de données et de l'apprentissage automatique (Quiz)
- Savoir implémenter une méthode d'analyse de donnée simple (TP)
- Savoir analyser les résultats d'une méthode d'analyse appliquée à une base de données (Projet)

Voir la page complète

Définitions et propriétés élémentaires de quantité d'information apportée par la réalisation d'un événementet l'entropie (au sens de Shannon) d'une v.a. (variable aléatoire) simple entropie conditionnelle d'une v.a., information mutuelle de deux v.a.
Théorie de codage, déchiffrabilité et ambiguïté, spontanéité de codes, Algorithme de Sardinas et Patterson, condition nécessaire et suffisante de Kraft-MCMillan pour l'existence d'un code déchiffrable avec les mots de longueurs données
Optimalité de codage (de v.a.), liens entre l'entropie d'une v.a. et la longueur moyenne des mots de code associé (théorèmes de Shannon), Algorithme de Huffman
Transmission d'information par les canaux bruités sans mémoire, quelques canaux importants, capacité d'un canal, calcul de capacité dans les cas simples, problème de décodage, schéma de décodage de borneuniforme d'erreur, théorème fondamental de Shannon sur la possibilité d'une transmission correcte avecprobabilité arbitrairement grande et de taux inférieur à la capacité (sans démonstration)

Voir la page complète