Logique et structure discrètes [ LINGI1101 ]

> https://icampus.uclouvain.be/claroline/course/index.php?cid=ingi1101

Au sein du programme SINF1BA : LSINF1250

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

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

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.

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

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

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

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,