Logique et structure discrètes

Note du 29 juin 2020
Sans connaitre encore le temps que dureront les mesures de distances sociales liées à la pandémie de Covid-19, et quels que soient les changements qui ont dû être opérés dans l’évaluation de la session de juin 2020 par rapport à ce que prévoit la présente fiche descriptive, de nouvelles modalités d’évaluation des unités d’enseignement peuvent encore être adoptées par l’enseignant ; des précisions sur ces modalités ont été -ou seront-communiquées par les enseignant·es aux étudiant·es dans les plus brefs délais.

5 crédits

30.0 h + 30.0 h

Enseignants

Van Roy Peter;

Langue
d'enseignement

Français

Préalables

Au sein du programme SINF1BA : LSINF1250
Au sein du programme FSA1BA : LFSAB1101, LFSAB1102, LFSAB1401, (LFSAB1301, LFSAB1201, LFSAB1202)

Thèmes abordés

Partie I: la logique de la logique propositionnelle et prédicat

Logique propositionnelle (syntaxe, sémantique, preuves)
Logique des prédicats (quantificateurs, les variables liées et libres, preuves) et l'application de l'analyse d'algorithmes
Théorie des ensembles et application à la spécification de systèmes formels (notation Z)
Relations et applications en informatique (bases de données relationnelles, relations binaires, ...)
Fonctions et lambda-calcul

Partie II: Structures discrètes

Graphes (concepts de base, chemins et connectivité)
Applications des graphes, par exemple, pour modéliser les réseaux sociaux (liens, homophilie, fermeture)
Graphes et propriétés des graphes utilisés pour modéliser les réseaux basés sur l'internet.
Introduction à la théorie des jeux

Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :

Eu égard au référentiel AA du programme « Bachelier ingénieur civil », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :

AA1.1, AA1.2
AA2.4

Eu égard au référentiel AA du programme « Bachelier en sciences informatiques », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :

S1.I1, S1.G1
S2.2

Les étudiants ayant suivi avec fruit ce cours seront capables de

convertir des affirmations du langage courant en expressions logiques en utilisant la syntaxe et la sémantique de la logique des propositions ou des prédicats
utiliser les règles d'inférence pour construire des preuves en logique de proposition ou des prédicats
décrire en quoi la logique symbolique permet de modéliser des situations réelles, telles que celles rencontrées dans le contexte de l'informatique (p.e. analyse d'algorithmes)
identifier et définir de manière précise les concepts de base des graphes et des arbres en fournissant des exemples contextualisés qui les mettent en lumière.
expliciter diverses méthodes de parcours de graphes
modéliser divers problèmes du monde réel rencontrés en informatique en utilisant les formes appropriées de graphes et d'arbres, par exemple les réseaux sociaux et le Web
expliciter les principaux concepts de la théorie des jeux (le type de jeu, le type de stratégie des agents) à l'aide d'exemples appropriés

Les étudiants auront développé des compétences méthodologiques et opérationnelles. En particulier, ils auront développé leur capacité à

définir et interpréter avec rigueur et précision les concepts
éviter les mauvaises interprétations et détecter des erreurs de raisonnement.

La contribution de cette UE au développement et à la maîtrise des compétences et acquis du (des) programme(s) est accessible à la fin de cette fiche, dans la partie « Programmes/formations proposant cette unité d’enseignement (UE) ».

Contenu

Préliminaires: ensembles, relations et fonctions, systèmes formels, déduction, induction, abduction, méthode scientifique.
Logique mathématique:
- Logique des propositions - syntaxe, sémantique, règles d'inférence, algorithme de preuve;
- Logique des prédicats du premier ordre - syntaxe, sémantique, règles d'inférence, algorithme de preuve;
- Langage de programmation Prolog et son algorithme de preuve;
- Notion de théorie, modèles, consistance, inclusion et extension de théories.
Théories équationnelles: théorie de l'égalité, théorie des ordres partiels, théorie des treillis, théorie des groupes.
Structures discrètes sur l'internet: graphes et propriétés des graphes, composants géants, liens forts et faibles, fermeture triadique, équilibre structurel, théorème d'équilibre, structure du Web, PageRank, lois de puissance, la longue traîne.

Illustrations élémentaires dans différents champs d'application: preuves de programmes, spécification de types abstraits, automatisation du raisonnement déductif, systèmes experts, robotique, bases de données, analyse syntaxique, etc.

Méthodes d'enseignement

2h de cours magistral/semaine, insistant sur les points délicats et difficiles
2h de séances d'exercices / semaine

Modes d'évaluation
des acquis des étudiants

brefs tests durant le quadrimestre (auto-évaluation)
examen écrit en session

Autres infos

Préalables :

Mathématiques discrètes élémentaires (fonctions, ensembles, ...)
Exposition à différentes techniques de démonstration mathématique

Ressources
en ligne

LINGI1101 Moodle: https://moodleucl.uclouvain.be/course/view.php?id=8199

Bibliographie

LINGI1101: Logique et Structures Discrètes par Peter Van Roy
Networks, Crowds and Markets: Reasoning About a Highly Connected World par David Easley and Jon Kleinberg

Faculté ou entité
en charge

INFO

Programmes / formations proposant cette unité d'enseignement (UE)

Intitulé du programme

Sigle

Crédits

Prérequis

Acquis
d'apprentissage

Master [60] en sciences informatiques

SINF2M1

Master [120] en sciences informatiques

SINF2M