Introduction à l'algorithmique

linfo1103  2020-2021  Louvain-la-Neuve

Introduction à l'algorithmique
En raison de la crise du COVID-19, les informations ci-dessous sont susceptibles d’être modifiées, notamment celles qui concernent le mode d’enseignement (en présentiel, en distanciel ou sous un format comodal ou hybride).
5 crédits
30.0 h + 30.0 h
Q2
Enseignants
Dupont Pierre;
Langue
d'enseignement
Français
Thèmes abordés
  • Conception et mise en oeuvre d'algorithmes itératifs ou récursifs : parcours, comptage, tri, recherche dans des collection
  • Complexité calculatoire
  • Structures de données élémentaires : tableaux, piles, files, listes chaînées
  • Structures de données récursives : structures arborescentes, arbres binaires de recherche
  • Invariants
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 en sciences informatiques », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :
  • S1.I2, S1.I3
  • S2.2-4
  • S6.2
Les étudiants ayant suivi avec fruit ce cours seront capables de :
  • justifier un choix entre plusieurs solutions algorithmiques pour résoudre un problème donné,
  • analyser des d'algorithmes, itératifs ou récursifs, pour représenter et manipuler des collections et d'en proposer des variantes,
  • choisir, concevoir et utiliser des structures de données, y compris récursives,
  • donner une estimation motivée de la complexité temporelle d'algorithmes itératifs et de la complexité spatiale de structures de données,
  • raisonner sur des propriétés d'algorithmes ou de structures de données en terme d'invariants.
Les étudiants auront développé des compétences méthodologiques et opérationnelles. En particulier, ils ont développé leur capacité à :
  • porter un regard critique et faire une analyse argumentée sur une solution ou un ensemble de solutions qui pourraient être apportées à un problème posé en se fixant des critères de qualité,
  • réaliser des programmes de taille réduite utilisant des algorithmes et structures de données classiques.
 
Contenu
L'algorithmique concerne la résolution de problèmes par la mise en oeuvre de suites d'opérations élémentaires selon un processus défini aboutissant à une solution.
Cette discipline est à la fois abstraite et mise en pratique par le biais de programmes, typiquement en Python, exécutés sur un ordinateur. 
  • Complexité temporelle et spatiale
  • Algorithmes de recherche dans les tableaux
  • Types abstraits et structures de données : piles, files, tableaux dynamiques, liste chaînes
  • Algorithmes de tri
  • Récursion
  • Types abstraits récursifs
  • Complexité calculatoire des algorithmes récursifs, équations de récurrence
  • Arbres binaires et dictionnaires
  • Invariants
     
Méthodes d'enseignement

En raison de la crise du COVID-19, les informations de cette rubrique sont particulièrement susceptibles d’être modifiées.

  • Cours magistraux
  • Travaux pratiques sur le serveur Inginious
  • 2 mini-projets en fin de quadrimestre
Les cours magistraux sont donnés, par défaut, en présentiel. Selon le nombre effectif d'étudiant.e.s inscrit.e.s au cours et l'évolution de la situation sanitaire, un dispositif pour pouvoir suivre le cours à distance sera également mis en place (enseignement co-modal).
Les travaux pratiques et projets sont à soumettre en ligne et sont évalués sur la plateforme Inginious.
Des séances de support aux étudiants pour les travaux pratiques sont données, par défaut, en présentiel. Selon l'évolution de la situation sanitaire, ces séances pourraient être données, partiellement ou totalement, en distanciel sur Teams.
Modes d'évaluation
des acquis des étudiants

En raison de la crise du COVID-19, les informations de cette rubrique sont particulièrement susceptibles d’être modifiées.

Une note de PARTICIPATION reflète l'implication de l'étudiant lors de ses travaux sur Inginious et concernant les 2 mini-projets en fin de quadrimestre.
 
En première session, la note de participation vaut pour 20 % de la note finale + 80 % pour l'examen final (à livre fermé).
La note de participation ne peut pas être réévaluée.
En seconde session, elle compte pour 10 % et l'examen final pour 90 % de la note globale.
 
L'examen final est, par défaut, un écrit (sur un ordinateur ou, le cas échéant, sur papier).
 
Ces règles d'évaluation sont sujettes à d'éventuelles mises à jour en fonction de la situation sanitaire.  En particulier, le poids relatif de la note de participation (ou spécifiquement des projets) et de l'examen final pourrait être adapté.  De telles adaptations seraient alors notifiées aux étudiants via une annonce générale sur le site Moodle du cours.
 
Bibliographie
Il n'y a pas d'ouvrage de référence obligatoire mais, à titre complémentaire, des ouvrages sont recommandés sur le site Moodle.
Support de cours
  • Les supports obligatoires sont constitués de l'ensemble des documents (transparents des cours magistraux, énoncés des travaux pratiques, compléments, ...) disponibles depuis le site Moodle du cours.
  • Required teaching material include all documents (lecture slides, project assignments, complements, ...) available from the Moodle website for this course.
Faculté ou entité
en charge
INFO
Force majeure
Méthodes d'enseignement
Les cours magistraux se donnent en distanciel. Les travaux pratiques continuent à être en ligne sur le serveur Inginious.
Modes d'évaluation
des acquis des étudiants
L'examen final a lieu en distanciel sur la plateforme Inginious.


Programmes / formations proposant cette unité d'enseignement (UE)

Intitulé du programme
Sigle
Crédits
Prérequis
Acquis
d'apprentissage
Master [120] en linguistique

Approfondissement en sciences et technologies de l'information et de la communication (pour seule réinscription)

Mineure en sciences informatiques

Bachelier en sciences informatiques

Mineure en technologies numériques et société