Ausbildungsprogramm

• Angestrebte Kompetenzen und Lernziele

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

  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)

Unterrichtsform

Kursbeschreibung

Lernkontrolle

• Schlussprüfung Lernkontrolle Berichte

Notenberechnung / Validierungsmodalitäten

Die Note des Kurses entspricht dem gewichteten Durchschnitt aller Lernkontrollen während des Semesters. Im Falle einer Schlussprüfung entspricht die Note des Kurses dem arithmetischen Mittel aus der Note der Lernkontrolle und der Schlussprüfung.

Bibliografie

Dozierende

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