Programme de formation

• Objectifs

  Aspects mathématiques: à la fin du cours, l'étudiant-e connaît :

  • quelques méthodes de la théorie des nombres, ainsi que plusieurs applications (par exemple, en cryptographie).
  • quelques méthodes standard des mathématiques numériques

  Aspects formels des langages : à la fin du cours l'étudiant-e sait :

  • utiliser les automates finis, les expressions régulières, et les diagrammes syntaxiques pour décrire un langage
  • utiliser l'algorithme de descente récursive pour programmer un analyseur de langage
  • manipuler les assertions pour vérifier des propriétés dans un programme, se débrouiller avec la notation JML
  • manipuler des formules de logique temporelle (LTL)
  • manipuler les concepts liés aux limites de la calculabilité (machines de Turing, indécidabilité, réduction polynomiale, ensemble dénombrable ou non, famille de problèmes NP-complet).
• Contenu

  Aspects formels des langages :

  • Notion d'alphabet et de langage; opérateurs sur les langages (union, intersection, concaténation, fermeture de Kleene)
  • Langage réguliers. Automates d'états finis. Expression régulières
  • Equivalences (DFA-NFA, automates-expressions)
  • Langages hors-contexte; diagrammes syntaxiques; grammaire formelle; notation EBNF
  • Dérivation, symboles terminaux et non terminaux. Algorithme de descente récursive
  • Analyse lexicale/syntaxique/sémantique; interprétation de langages
  • Analyse d'expressions arithmétiques
  • Preuves de programme. Assertions et invariants; pré/post conditions; JML
  • Logique propositionnelle; logique temporelle
  • Machines de Turing. Problèmes indécidables
  • Ensembles dénombrables ou non (et diagonalisation de Cantor)
  • P vs NP; réduction polynomiale; problèmes NP-complet (SAT, HAM, 3-COL)

  Mathématiques discrètes

  • Récurrence linéaires et séries génératrices
  • Relations, relation d'équivalence
  • Initiation à la théorie des nombres (modules, tests de primalité, etc)
  • Bases de la théorie de l'information de Shannon
  • Bases de la cryptographie moderne ('public key', 'zero knowledge' etc)

Forme d'enseignement et volume de travail

Spécification du cours

Modalités d'évaluation

• Contrôle continu: travaux écrits

Mode de calcul de la note de cours

La note du contrôle continu est la moyenne pondérée des évaluations du semestre. En cas d'examen de révision, la note finale du cours est la moyenne arithmétique de la note du contrôle continu et de celle de l'examen de révision.

Ouvrage de référence

Enseignant(s) et/ou coordinateur(s)

Richard Baltensperger, Frédéric Bapst, Christoph Herren, Philippe Joye, Roseline Nussbaumer, Rudolf Riedi