Logique et structure discrètes

lingi1101  2018-2019  Louvain-la-Neuve

Logique et structure discrètes
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 relationnellesrelations 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.
  • Logique mathématique:
    • Calcul des propositions - syntaxe, sémantique, règles d'inférence; calcul des prédicats du premier ordre - syntaxe, sémantique, règles d'inférence, réfutation;
    • 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
Bibliographie
Transparents en ligne sur icampus
Livres :
  • Introductory Logic and Sets for Computer Scientists par Nimal Nissanke
  • 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
Mineure en sciences informatiques