<- Archives UCL - Programme d'études ->



Mathématiques pour l'informatique [ LSINF1250 ]


7.0 crédits ECTS  30.0 h + 15.0 h   2q 

Enseignant(s) Saerens Marco (supplée Avoine Gildas) ; Avoine Gildas ;
Langue
d'enseignement:
Français
Lieu de l'activité Louvain-la-Neuve
Ressources
en ligne

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

Préalables

LMAT1111E, LSINF1101

Thèmes abordés

1. Logique, ensembles et fonctions

  • Equivalence,
  • Prédicats et quantifieurs,
  • Ensembles et opérations sur les ensembles,
  • Séquences et sommations,
  • Croissance des fonctions

2. Algorithmes, entiers et matrices

  • Complexité algorithmique,
  • Entiers et divisions,
  • Rudiments de la théorie des nombres,
  • Rappels de calcul matriciel,
  • Application aux chaînes de Markov

3. Raisonnement logique et mathématique

  • Méthodes de preuve,
  • Induction mathématique,
  • Récursion et algorithmes récursifs,
  • Exactitude d'un programme

4. Combinatoire

  • Comptage,
  • Permutations,
  • Arrangements,
  • Relations de récurrence,
  • Solutions d'équations de récurrence

5. Graphes

  • Représentation de graphes et isomorphisme de graphe,
  • Connectivité,
  • Chemins Hamiltoniens,
  • Problèmes de chemin le plus court

6. Arbres

  • Introduction, 
  • Applications des arbres,
  • Parcours d'arbres,
  • Arbres et tri,
  • Arbres de recouvrement minimal
Acquis
d'apprentissage

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

  • Utiliser à bon escient la terminologie des fonctions, relations et ensemble et réaliser les opérations associées lorsque le contexte le nécessite
  • Expliciter la structure de base des principales techniques de preuve (preuve directe, contrexemple, preuve par l'absurde, induction, récursion)
  • Appliquer les différentes techniques de preuve de manière convaincante en sélectionnant la plus adaptée au problème posé
  • Analyser un problème pour déterminer les relations de récurrence sous-jacentes
  • Calculer des comptages, permutations, arrangements sur des ensembles dans le cadre d'une application.
  • Appliquer diverses méthodes de parcours de graphes et d'arbres (parmi lesquelles les parcours préfixe, postfixe et infixe d'arbres)
  • Modéliser divers problèmes du monde réel rencontrés en informatiques en utilisant les formes appropriées de graphes et d'arbres, par exemple la représentation de la topologie des réseaux, l'organisation hiérarchique de fichiers, ...
  • Expliquer le problème du plus court chemin dans un graphe et appliquer sur des graphes simples l'algorithme de Dijkstra et de Bellman-Ford
  • Expliquer comment construire l'arbre de recouvrement minimal d'un graphe
  • Déterminer si deux graphes sont isomorphes
Modes d'évaluation
des acquis des étudiants
  • Un projet/cas d'étude comptant pour 3 points sur 20.
  • Un examen écrit organisé en session comptant pour 17 points sur 20.
Méthodes d'enseignement
  • 30 heures de cours magistraux.
  • Un projet/cas d'étude portant sur l'implémentation d'un algorithme.
Contenu

Le contenu est articulé autour des thèmes de base comme suit:

- Structures mathématiques de base : ensembles, relations, fonctions, ensembles infinis

- Méthodes de démonstration : intuition, éléments de logique

- Dénombrement : nombres binomiaux, récurrences, fonctions génératrices - Structures algébriques : monoïdes, groupes, morphismes, treillis, algèbre de Boole

- Théorie des graphes : arbres, chemins, couplages, tours, etc.

- Analyse de la complexité : algorithme polynomial, etc.

Autres infos

Préalables:

  • De bonnes connaissances en mathématiques générales (en particulier en algèbre linéaire) et des concepts de base de la programmation sont requises pour ce cours
Cycle et année
d'étude
> Bachelier en sciences informatiques
Faculté ou entité
en charge
> INFO


<<< Page précédente