UCL - Etudes

English version

Formations
Premier cycle
Deuxième cycle
Troisième cycle
Certificats (programmes non académiques)
Passerelles
Formation continue
Facultés et entités
Cadre académique
Réforme de Bologne
Accès aux études
Organisation des études
Lexique
Calendrier académique
Règlement des études et examens
Charte pédagogique
Renseignements généraux
Recherche
Simple
Détaillée
Par cours

Logique et structure discrètes [INGI1101]
[30h+30h exercices] 4 crédits

English version

Version imprimable

Cette activité se déroule pendant le 1er semestre

Enseignant(s):

Chantal Poncin (supplée Axel Van Lamsweerde), Axel Van Lamsweerde

Langue d'enseignement :

français

Niveau :

Premier cycle

>> Objectifs (en termes de compétences)
>> Objet de l'activité (principaux thèmes à aborder)
>> Résumé : Contenu et Méthodes
>> Autres informations (Pré-requis, Evaluation, Support, ...)
>> Autres crédits de l'activité dans les programmes

Objectifs (en termes de compétences)

- Comprendre et maîtriser les fondemants mathématiques d'un grand nombre de concepts et techniques des systèmes informatiques.

- Etre capable d'établir les liens entre ces fondements et différents domaines d'application (algorithmique, structures de données, intelligence artificielle, génie logiciel, bases de données, robotique, etc.).

- Etre capable de suivre une démarche rigoureuse pour formaliser des structures informatiques courantes et appliquer des raisonnements sur ces structures.

Objet de l'activité (principaux thèmes à aborder)

- Introduction à la logique mathématique: logique des propositions, logique des prédicats; théories du premier ordre.

- Mécanismes de raisonnement: résolution, réécriture, induction sur un ensemble bien fondé.

- Structures discrètes vue comme théories du premier ordre: égalité, ordres partiels, treillis; naturels, chaînes, arbres, listes, ensembles, multi-ensembles, tuples, etc.

Résumé : Contenu et Méthodes

- Préliminaires: ensembles, relations et fonctions, systèmes formels.

- Logique mathématique: (1) calcul des propositions - syntaxe, sémantique, règles d'inférence; (2) calcul des prédicats du premier ordre - syntaxe, sémantique, règles d'inférence, réfutation; (3) 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.

- Théories inductives: relation biens fondées; induction générale sur un ensemble bien fondé; étude de quelques théories inductives de base - entiers, chaînes, arbres, listes, ensembles, multi-ensembles, tuples. Notion de générateur de structure, construction systématique d'axiomatisations, et démonstrations inductives de propriétés selon différents principes d'induction (récurrence, induction complète, etc.).

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.

Mise en oeuvre à l'aide de langages de programmation " déclaratifs " tels que PROLOG ou ML.

Autres informations (Pré-requis, Evaluation, Support, ...)

- Les séances de travaux pratiques hebdomadaires requièrent une participation active et la prépartion de questions/réponses et résolution, par petits groupes, de problèmes remis à la séance précédente. Plusieurs tests sont organisés au cours du quadrimestre de manière à contrôler le travail régulier de l'étudiant.

- Prérequis:
Maîtrise des mathématiques élémentaires (supposée acquise à l'issue des deux premières années de baccalauréat).

- Références :
(1) Syllabus en vente au SICI.

(2) Z. Manna and R. Waldinger, The Deductive Foundations of Computer Programming, Addison-Wesley, 1993.

(3) D. Gries, F. Schneider, A Logical Approach to Discrete Mathematics, Springer-Verlag, 1994.

- Modalités d'évaluation
Tests au cours du quadrimestre, et examen écrit en session.

Autres crédits de l'activité dans les programmes

FSA13BA

Troisième année de bachelier en sciences de l'ingénieur, orientation ingénieur civil

(4 crédits)

INFO22

Deuxième année du programme conduisant au grade d'ingénieur civil informaticien

(4 crédits)

INFO23

Troisième année du programme conduisant au grade d'ingénieur civil informaticien

(4 crédits)

SINF12BA

Deuxième année d'études de bachelier en sciences informatiques

(4 crédits)

SINF13BA

Troisième année d'études de bachelier en sciences informatiques

(4 crédits)

SINF1PM

Année d'études préparatoires au master en sciences informatiques (60 et 120)

(4 crédits)

Obligatoire



Ce site a été conçu en collaboration avec ADCP, ADEF, CIO et SGSI
Responsable : Jean-Louis Marchand - Contact : secretaire@fsa.ucl.ac.be
Dernière mise à jour :13/03/2007