UE Fundamental Computer Science

Informations aux utilisateurs

Veuillez noter que vous consultez une page du catalogue de formation 2020-2021. Le recrutement est actuellement terminé pour les licences, licences professionnelles, masters, DUT et formations réglementées de santé. Pour consulter le catalogue des formations 2021-2022, cliquez sur le lien suivant.

Diplômes intégrant cet élément pédagogique :

Descriptif

This module introduces the fundamental aspects of computer science and particularly focuses on the notions of computability and complexity. Regarding computability theory, it presents the basic formal model to reason on the notion of computation, i.e., the Turing machine and its variants. Based on this computational model, the notions of decidable and semi-decidable languages will be defined, while the existence of languages which are undecidable will be shown. Regarding complexity theory, it presents the main classes of time complexity such as P, NP, as well as the notion of NP-completeness. Several problems in the domains of propositional logic, graphs and scheduling are studied with respect to their time complexity by proposing either polynomial-time algorithms to solve them efficiently or polynomial-time reductions to prove their hardness.

Course opened in 2018/2019

Informations complémentaires

Méthode d'enseignement : En présence
Langue(s) : Anglais