Study program

• Objectives

  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.
• Content

  • 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

Type of teaching and workload

Course specification

Evaluation methods

• Continuous assessment Written work, Practical exercises / Evaluated reports
• Exam: written (120 min.)

Course grade calculation method

SemesterScore=Average of written work +/- possible small adjustment determined by the evaluation of the TPs. FinalGrade = (SemesterGrade+GradeReview)/2

Reference work

Intructor(s) and/or coordinator(s)

Frédéric Bapst, Alain Jungo, Rudolf Scheurer