Compléments de programmation et d'algorithmique

Structures de données

• Principes généraux
• Piles, files et tableaux
• Listes chaînées
• Queues de priorité, tas (heaps)
• Arbres binaires de recherche
• Tables de hachage

Analyse de base des algorithmes

• Les notations Grand O, Omega et Theta
• Notion d'algorithme et de complexité
• Classes de complexité standards

Algorithmes de tri

• Tri par insertion
• Tri par fusion (mergesort)
• Tri par tas (heapsort)- Tri rapide (quicksort)
• Tri linéaire: tri par comptage (counting sort) et tri Radix

Stratégies algorithmiques

• Divide-and-conquer
• Backtracking
• Programmation dynamique
• Algorithmes gloutons

Structures de données :

• Pouvoir concevoir et utiliser une structure de données élémentaire adaptée au problème (tableaux, listes chaînées, tables de hachage, arbres binaires de recherche, etc.)
• Pouvoir analyse le coût des opérations pour chaque structure de donnée

Algorithmique :

• Pouvoir concevoir des algorithmes pour des problèmes simples en utilisant les techniques de base de l'algorithmique (divide-and-conquer, backtracking, programmation dynamique, etc.)
• Pouvoir analyser la complexité de ces algorithmes

Cours pré-requis

Cours ayant celui-ci comme co-requis

• Cours magistraux avec slides.
• Travaux pratiques en salle d'apprentissage actif: programmation sur ordinateur, mais aussi certains exercices théoriques sur papier.
• 2 projet de programmation sur des sujets imposés (structures de données et algorithmique)

Références, bibliographie et lectures recommandées

• Introduction to Algorithms (Third Edition), T.H. Cormen et al. (2009)

Support(s) de cours

• Podcast
• Université virtuelle

Contacts

Jérémie Roland (Jeremie.Roland@ulb.be)

Campus

Solbosch

Méthode(s) d'évaluation

• Examen écrit
• Projet
• Evaluation continue

Examen écrit

• Examen hors-session

• Question ouverte à réponse courte
• Question ouverte à développement long
• Question fermée à Choix Multiple (QCM)
• Question fermée à Réponses Multiples (QRM)

Projet

Evaluation continue

• Evaluation continue: 2 projets de programmation (2 points chacun donc 4 points au total)
  • 2 projets individuels: un projet sur les structures de données (à rendre au milieu du quadrimestre) et un projet sur l'algorithmique (à rendre en fin de quadrimestre)
  • Les projets seront évalués via deux interrogations écrites organisées pendant chacune des deux semaines de récupération du quadrimestre (chaque interrogation étant notée sur 2 points).
  • Le code du projet rendu sera testé pour vérifier qu'il est fonctionnel (en cas de code non-fonctionnel, la note de l'évaluation correspondante sera ramenée à 0/2), mais ne sera pas noté en tant que tel.
  • Attention: les projets sont organisés en première session uniquement
• Evaluation finale: examen écrit (16 points)
  • Questions ouvertes et fermées comportant des éléments de théorie et des exercices
  • Organisée en première et seconde session suivant les mêmes modalités

Construction de la note (en ce compris, la pondération des notes partielles)

L'interrogation liée à chaque projet est notée sur 2 et l'examen écrit final sur 16.

• Si le code rendu pour un des projets n'est pas fonctionnel, la note de l'évaluation correspondante sera ramenée à 0 point.
• La note finale du cours est la somme de la note des interrogations et de l'examen écrit final.

L'examen écrit est organisé en seconde session selon les mêmes modalités qu'en première session. Si le cours n'est pas crédité en première session, la note de l'examen oral n'est pas reportée en seconde session.

Les projets sont organisés en première session uniquement: si le cours n'est pas crédité en première session, la note des projets de première session sera automatiquement reportée en seconde session, les projets ne pouvant être représentés que l'année académique suivante.
Si le cours n'est pas crédité en seconde session, les notes partielles ne sont pas reportées à l'année académique suivante.

Langue(s) d'évaluation

• français