Logique et structure discrètes

lingi1101  2019-2020  Louvain-la-Neuve

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
Q1
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 :

1 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

Master [120] en sciences informatiques