Introduction a l'algorithmique et aux types abstraits de données.

Ce cours (avec un faible volume horaire) donne quelques une des notions du calcul de fiabilité et de la théorie de l'information (entropie, transmission digitale et application au codage) .
Plan :
  1. Généralités sur la théorie de l'information
  2. Initiation à la théorie de la fiabilité
  3. Théorie du codage
Prérequis :
module IS 101 : Probabilités et Statistiques

L'objectif est l'acquisition des outils théoriques permettant de construire un raisonnement, avec application à la preuve de programmes.
  • Induction, preuve par induction
  • Logique propositionnelle
  • Logique du 1er ordre
  • Preuve formelle
  • Spécifications de programmes
  • Preuve de correction: logique de Hoare
  • Preuve de terminaison

Présentation de XML: analyse lexicale (SAX/DOM), types de documents (DTD/XML Schemas/Relax NG), requêtes (XPath) et styles (XSLT). Application à la programmation web, par exemple DHTML, RSS, AJAX, SOAP, Webservices.

Présentation des techniques et outils standards pour la compilation, pour une mise en oeuvre dans le projet IF204. Le plan du cours est:

  1. Objectif d'un compilateur, pourquoi étudier la compilation
  2. Expressions régulières et langages réguliers, quelques rappels
  3. Langages algébriques et grammaires
  4. Analyseurs syntaxiques, méthodes descendantes LL et ascendantes LR, PEG; mise en oeuvre dans un outil (Yacc)
  5. Analyse sémantique: grammaires attribuées, calculs d'attributs tels que les types
  6. Génération de code: pour une machine à pile, pour une machine à registres. Principaux schémas de traduction, allocation de la mémoire
  7. Problèmes d'optimisation: allocation de registre, optimisation de code, ...
  8. Les dernières phases de compilation: assembleur, édition de lien, chargeur.

Les automates finis permettent de modéliser des programmes informatiques à mémoire finie. Ils permettent de résoudre des problèmes à un niveau d'abstraction élevé, sans s'encombrer des spécificités d'un langage donné, et en se concentrant sur les invariants à maintenir pour parvenir à une solution. L'étude de ce modèle s'inscrit dans le cadre général de la théorie des langages abordée ensuite dans les modules IF203 (compilation) et IF228 (calculabilité et complexité). L'enseignement aborde des notions théoriques (automates finis, langages réguliers, expressions régulières, équivalence de ces trois formalismes, non-déterminisme, automate minimal, lemme de l'étoile) ainsi que leur utilisation pour la résolution de problèmes concrets.