Computer science and communication systems : /en/education/bachelor/computer-science-and-communication-systems/

Study program

Department: Computer science and communication systems
Specialization: Networks and Systems
Module: Simulation IT

Course description

Back Mathématiques spécifiques 2

  • Objectives

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

    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)

Type of teaching and workload

Lecture course (including exercises)
64 periods
Travail personnel
26 periods

Course specification

Year of validity
2025-2026
Weight
2nd year
Semester
Spring
Program
French,Bilingual
Department
Computer science and communication systems
Language of instruction
French
ID
B2C-MAS2-S
Level
specialized
Course type
Core
Study program
Bachelor

Evaluation methods

  • Continuous assessment Written work

Course grade calculation method

The continuous assessment mark corresponds to the weighted average of all of the semester's exams. In case of a revision exam, the course's final mark corresponds to the arithmetic average of the continuous assessment and the revision exam marks.

Reference work

  • D. C. Kozen : ''Automata and computability'', Springer, 2007, ISBN 978-0-387-94907-9 (bibl. EIA-FR : 681.32 KOZE)
  • C. Baier, J. P. Katoen : ''Principles of model checking'', MIT Press, 2007, ISBN 978-0-262-02649-9 (bibl. EIA-FR : 681.332 BAIE)

Intructor(s) and/or coordinator(s)

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