Introduction à l'algorithmique

Enseignants

Derval Guillaume (supplée Dupont Pierre); Dupont Pierre;

Langue
d'enseignement

Français

Préalables

Ce cours suppose acquises les notions de base de la programmation visées par le cours LINFO1101

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

• Cours magistraux
• Travaux pratiques sur le serveur Inginious
• Un projet en fin de quadrimestre

Modes d'évaluation
des acquis des étudiants

Calcul de la note globale pour le cours

Règles concernant les collaborations entre étudiants et l'usage de ressources externes

Une collaboration active entre les étudiant.e.s est encouragée lors des séances de travaux pratiques et via un forum d'échanges sur Moodle.
Chaque étudiant.e doit soumettre une solution personnelle au projet final. Le recours à des ressources publiques (p.ex. stackoverflow.com), ce-inclus des IA génératives (p.ex. chatGPT) est autorisé pour autant que chaque (fragment de) code mentionne toutes les ressources utilisées.
La diffusion ou l'échange entre étudiants de (fragments de) code ne sont pas autorisés par quelque moyen que ce soit (GitHub, Facebook, Discord, ...) et ce même après la date limite de remise du projet.
Le non-respect de ces règles pour le projet entraînera une note globale de 0 pour la participation au cours.
L'examen final sur ordinateur doit se faire sans accès à aucune ressource externe.
Ces règles sont exposées et détaillées lors du premier cours (voir site Moodle du cours).
 

Ressources
en ligne

moodle.uclouvain.be/course/view.php?id=1916

Bibliographie

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