Programme de formation

• Objectifs

  Des bases solides en programmation incluent nécessairement une initiation soutenue et rigoureuse aux algorithmes et aux structures de données, et c'est l'objet de ce cours.

  Objectifs généraux :

  • Comprendre l'analyse de complexité, sur laquelle se base la notion d'efficacité (CPU, RAM) d'un programme
  • Comprendre, utiliser et implémenter les types abstraits de base, et maîtriser quelques algorithmes essentiels
  • Maîtriser certaines techniques de programmation comme la récursivité et les noeuds de chaînage
  • Réfléchir de façon abstraite, avec logique, en distinguant spécification et implémentation, et en s'aidant de formalismes adéquats (esquisses, pseudo-code, ...)
  • Concevoir et développer une solution à un problème simple au moyen d'un programme, en s'aidant d'un environnement de développement

  A la fin du cours, l'étudiant sait :

  • Appréhender les aspects algorithmiques d'un problème informatique, concevoir un algorithme pour le résoudre, en s'appuyant sur une structuration adéquate des données
  • Spécifier, réaliser et utiliser des types abstraits usuels (liste, ensemble, dictionnaire...), et en développer des variantes
  • Implémenter et exploiter des algorithmes fondamentaux (tris, recherche binaire...), et en développer des variantes
  • Analyser la complexité théorique d'un programme et la vérifier expérimentalement.
• Contenu

  • Algorithme et analyse de complexité (worst-case, O(...), CPU vs RAM)
  • Types abstraits (pile, file, liste chaînée, ensemble et dictionnaire, table de hachage, bitset, file de priorité, introduction aux arbres et graphes, liste récursive)
  • Récursivité (principes, exemples, Divide-and-Conquer...)
  • Chaînage de noeuds (liste doublement chaînée, arbres binaires...)
  • Techniques de programmation (programmation dynamique, algorithme probabiliste, traitement d'erreurs, généricité, exemple de backtracking)
  • Quelques algorithmes classiques (recherche binaire, 7 algorithmes de tri, hachage, nombres aléatoires, ...)
  • Résolution de problèmes, spécification (PRE/POST-conditions), tests de programme, lutte systématique contre les bugs, problèmes numériques en programmation, mesure du temps d'exécution

Forme d'enseignement et volume de travail

Spécification du cours

Modalités d'évaluation

• Contrôle continu: travaux écrits, TP/évaluation de rapports
• Examen: écrit (120 min.)

Mode de calcul de la note de cours

NoteSemestre=Moyenne des travaux écrits +/- éventuel petit ajustement déterminé par l'évaluation des TPs. NoteFinale = (NoteSemestre+NoteExamen)/2

Ouvrage de référence

Enseignant(s) et/ou coordinateur(s)

Frédéric Bapst, Andreas Fischer, Rudolf Scheurer