Examen Structures de données
1. Décrivez les principales structures de données linéaires (liste,
pile, file) utilisées en informatique. Présentez leurs opérations fondamentales
(insertion, suppression, accès, etc.) et donnez un exemple d'implémentation en
pseudocode pour chacune d'entre elles.
2. Expliquez le principe des arbres binaires de recherche. Quelles
sont les principales opérations (recherche, insertion, suppression) que l'on
peut effectuer sur ce type de structure ? Donnez la complexité de ces
opérations.
3. Considérons un arbre binaire de recherche contenant les valeurs
suivantes : 10, 5, 15, 3, 7, 12, 20.
a. Construisez cet arbre
binaire de recherche.
b. Effectuez une recherche
de la valeur 12 dans cet arbre et expliquez le déroulement de l'opération.
c. Supprimez la valeur 15
de cet arbre et reconstruisez-le. Justifiez les étapes de cette suppression.
4. Décrivez les principes des tables de hachage et leurs avantages
par rapport aux structures de données linéaires classiques. Donnez un exemple
simple d'implémentation en pseudocode d'une table de hachage.
5. Comparez les algorithmes de tri par sélection et de tri rapide (quicksort). Quelles sont les complexités respectives de ces deux algorithmes dans le meilleur et le pire des cas ?
Vous devrez justifier vos réponses de manière détaillée et montrer
vos étapes de résolution. Cet exercice vise à évaluer vos compétences en
structure de données et en algorithmique.
Examen de Programmation II
Durée : 2 heures
1. Programmation orientée objet :
a. Définissez les concepts
de classes, d'objets, d'héritage et de polymorphisme en programmation orientée
objet.
b. Donnez un exemple
d'implémentation en pseudo-code d'une hiérarchie de classes représentant
différents types d'animaux.
2. Structures de données avancées :
a. Expliquez les principes
des arbres binaires de recherche (ABR) et donnez les complexités des
principales opérations sur ces structures.
b. Décrivez l'algorithme
de parcours en largeur (BFS) sur un ABR et donnez sa complexité.
3. Algorithmes et complexité :
a. Comparez les
algorithmes de tri fusion (merge sort) et tri rapide (quicksort) en termes de
complexité dans le meilleur et le pire des cas.
b. Décrivez l'algorithme
de Dijkstra pour le calcul du plus court chemin dans un graphe pondéré et
donnez sa complexité.
4. Programmation fonctionnelle :
a. Expliquez les concepts
de fonctions d'ordre supérieur, de lambda-expressions et d'immutabilité en
programmation fonctionnelle.
b. Donnez un exemple
d'implémentation en pseudo-code d'une fonction d'ordre supérieur pour filtrer
et transformer une liste d'éléments.
5. Programmation concurrente :
a. Décrivez le problème de
la condition de course (race condition) et expliquez comment le résoudre à
l'aide de mécanismes de synchronisation.
b. Implémentez en
pseudo-code un programme concurrent avec un producteur et un consommateur
utilisant un tampon partagé.
Vous devrez justifier vos réponses de manière détaillée et montrer
vos étapes de résolution. Cet examen vise à évaluer vos compétences en
programmation avancée, en structures de données, en algorithmes et en
programmation concurrente.
Bien sûr, voici des explications plus détaillées sur les concepts de programmation fonctionnelle mentionnés dans l'examen :
4. Programmation fonctionnelle :
a. Fonctions d'ordre supérieur :
- Les fonctions d'ordre
supérieur sont des fonctions qui peuvent prendre d'autres fonctions en argument
ou renvoyer des fonctions.
- Cela permet de créer des
abstractions plus puissantes et de réutiliser du code plus facilement.
- Exemples de fonctions
d'ordre supérieur : map, filter, reduce, etc.
b. Lambda-expressions :
- Les lambda-expressions,
ou fonctions anonymes, sont des fonctions sans nom qui peuvent être définies et
utilisées à la volée.
- Elles permettent
d'écrire du code plus concis et expressif, en évitant de définir des fonctions
nommées inutiles.
- Elles sont souvent
utilisées en combinaison avec les fonctions d'ordre supérieur.
- Exemple en Python :
```python
square = lambda x: x**2
numbers = [1, 2, 3, 4,
5]
squared_numbers = list(map(square, numbers))
c. Immutabilité :
- L'immutabilité signifie
que les structures de données ne peuvent pas être modifiées une fois créées.
- Cela permet de garantir
l'intégrité des données et facilite la programmation concurrente.
- Les langages
fonctionnels comme Haskell ou Clojure utilisent des structures de données
immutables par défaut.
- Même si les langages
impératifs comme Python ou Java n'ont pas d'immutabilité par défaut, on peut
créer des structures de données immutables (ex : tuples, listes en
compréhension).
J'espère que ces explications vous aident à mieux comprendre ces
concepts clés de la programmation fonctionnelle.