Examen corrigé d'algorithmique et programmation Master 1

Présentation de l'épreuve d'algorithmique et programmation

Ce document rassemble le sujet et le corrigé d'un examen d'algorithmique et programmation destiné aux étudiants de Master 1. Cette évaluation s'inscrit dans le cadre de l'unité d'enseignement J1BS7202 de la mention Master BioInformatique à l'Université Bordeaux 1, sous la direction de l'enseignant Alain Griffault. D'une durée de deux heures, cette épreuve écrite autorisait l'utilisation de documents et proposait un barème détaillé réparti sur trois exercices principaux : une partie introductive nommée mise en bouche, des algorithmes de rang et l'étude des listes doublement chaînées.

Contenu et exercices de l'évaluation

Le sujet aborde plusieurs aspects fondamentaux de l'algorithmique et de la programmation impérative, en alternant la rédaction d'algorithmes en pseudo-code et l'écriture de fonctions en langage Python. Les étudiants devaient ainsi maîtriser la manipulation de tableaux de nombres, la recherche d'éléments particuliers et la gestion de structures de données dynamiques.

Exercice 1 : Mise en bouche

La première partie évalue des fonctions de base sur les nombres opposés et inverses. Les questions successives demandent d'écrire une fonction vérifiant si deux nombres sont opposés ou inverses, puis d'étendre ce test à un tableau entier pour détecter la présence de nombres consécutifs possédant cette propriété, ou d'analyser toutes les paires d'indices possibles dans un tableau pour compter ou repérer ces relations.

Exercice 2 : Algorithmes de rang

Le cœur de l'épreuve est consacré au problème de la sélection, qui consiste à déterminer l'élément de rang i dans un tableau de nombres, en considérant que le rang 0 correspond au plus petit élément. Les différentes sous-parties explorent l'adaptation de méthodes classiques de tri, telles que le tri par sélection, le tri à bulles et le tri rapide basé sur une partition en trois zones inspirée du drapeau hollandais. Pour chaque méthode, le document présente l'algorithme itératif ou récursif correspondant ainsi qu'une analyse comparative rigoureuse des complexités temporelles et spatiales dans le meilleur des cas, le pire des cas et le cas moyen.

Exercice 3 : Listes doublement chaînées

La dernière partie s'intéresse aux structures de données dynamiques à travers l'implémentation de primitives pour les listes doublement chaînées. Les étudiants devaient concevoir des fonctions permettant de trouver la dernière cellule d'une liste, d'insérer une cellule après un pointeur donné, d'ajouter un élément en tête de liste et de concaténer deux listes entre elles en mettant à jour correctement les pointeurs de liaison.

Utilisation recommandée pour les révisions

Ce sujet corrigé constitue un support de travail particulièrement formateur pour s'entraîner à la conception d'algorithmes et à leur traduction en Python. Il est conseillé de chercher à résoudre chaque exercice par soi-même avant de consulter les solutions proposées, qui offrent souvent plusieurs pistes de rédaction. L'analyse des tableaux de complexité permet également de comprendre l'efficacité relative des algorithmes de recherche de rang et d'optimiser l'écriture de code manipulant des structures dynamiques ou des tableaux indicés.

Questions fréquentes

À quel niveau d'études s'adresse ce sujet d'examen ?

Ce document s'adresse aux étudiants en première année de Master (Master 1) en BioInformatique à l'Université Bordeaux 1.

Quels sont les grands thèmes abordés dans le document ?

L'évaluation couvre la manipulation de tableaux, les algorithmes de recherche de rang par adaptation de méthodes de tri, l'analyse de complexité algorithmique et la manipulation de listes doublement chaînées.

Quels langages ou notations sont utilisés pour les réponses ?

Les étudiants pouvaient répondre au choix en rédigant des algorithmes en pseudo-code structuré ou en écrivant directement des programmes en langage Python.

Testez vos connaissances

Télécharger Examen corrigé d'algorithmique et programmation Master 1 pdf