★ À maîtriser
Le projet vise à étudier l’influence des structures de données sur la performance des algorithmes et à comprendre les types abstraits et leurs implémentations.
🔄 Le projet suit ces étapes :
Compléments
La base de données du projet est interrogée avec des requêtes SQL et peut être récupérée avec DBeaver.
Valgrind sert à mesurer l’utilisation de la mémoire, et des scripts Bash peuvent aider à exploiter les données.
L’encapsulation et la programmation modulaire permettent de passer d’une structure de données à une autre dans le projet.
Changer de structure → observer les variations de performance.
★ À maîtriser
Compléments
Pour une collection créée avec une capacité n, sa longueur est nulle et l’accès à un indice renvoie une erreur.
Après l’ajout d’un élément e à l’indice i, la longueur augmente de un, l’élément d’indice i vaut e, et les éléments précédents et suivants sont décalés en conséquence.
La recherche dans une collection vide renvoie -1, et l’ajout d’un élément déjà présent conserve son indice de recherche antérieur.
★ À maîtriser
Un tableau stocke ses éléments dans un espace mémoire contigu sans espace perdu ; avec des entiers codés sur 4 octets et une adresse codée sur 64 bits (8 octets), un tableau de n entiers occupe 4n + 8 octets.
Dans un tableau, l’accès prend O(1), tandis que la modification et la recherche prennent chacune O(n) en temps.
Une liste chaînée stocke ses éléments dans un espace non contigu et nécessite des adresses supplémentaires ; avec des entiers codés sur 4 octets et des adresses de 8 octets, elle occupe (4 + 8) × n octets.
Compléments
Dans une liste chaînée, l’accès et la recherche prennent O(n) en temps, tandis que la modification prend O(n) en temps et O(1) en mémoire supplémentaire.
Les hash-map ou les arbres peuvent rendre la recherche plus efficace que dans les structures présentées.
Tableau contigu pour l’accès rapide ; liste non contiguë pour limiter la mémoire temporaire.
Les ressources matérielles comprennent :
Les systèmes d’exploitation fonctionnent notamment sur :
★ À maîtriser
Windows est un système d’exploitation produit par Microsoft et principalement destiné aux PC.
À l’origine, Windows était une interface graphique reposant sur un cœur MS-DOS ; depuis Windows 95, il est un système d’exploitation complet.
Compléments
Unix a été créé en 1969 par Kenneth Thompson et Dennis Ritchie, principalement pour un usage professionnel.
Après une tentative infructueuse avec le langage B, le langage C est créé par Dennis Ritchie en modifiant et en étendant B, puis Unix est réécrit en C.
📌 Deux familles d’Unix apparaissent : AT&T, issue des Bell Labs, et BSD, issue de Berkeley.
MULTICS échoue, les équipes Bell s’en détachent, puis conçoivent UNIX.
★ À maîtriser
Compléments
📌 GNU peut fonctionner avec d’autres noyaux, comme GNU/Hurd, tandis que Linux peut être associé à d’autres outils, comme dans Android.
La plupart des distributions Linux actuelles descendent de :
GNOME, KDE, LXDE et Unity sont des environnements de bureau pouvant être utilisés sur plusieurs distributions Linux, voire sur plusieurs systèmes Unix.
GNU apporte les outils, Linux le noyau
★ À maîtriser
Sur les smartphones, les parts indiquées sont de 73 % pour Android, 20 % pour iOS et 0,7 % pour Windows.
Sur les serveurs, les parts indiquées sont de 32 % pour Windows, 35 % pour Linux et 31 % pour Unix (BSD).
Compléments
★ À maîtriser
📌 Un makefile est constitué de règles de la forme cible : dépendances, suivies des instructions de construction.
Compléments
Il existe plusieurs implémentations de make qui ne sont pas uniformisées ; le cours porte sur GNU make.
Dans un makefile, les instructions d’une règle doivent être précédées de tabulations.
Les make sont moins utiles pour Java, car javac compile automatiquement le fichier et les dépendances nécessaires.
Une dépendance plus récente → mise à jour de la cible
★ À maîtriser
Les variables personnelles de make se définissent par affectation et s’utilisent sous la forme $(NOMVAR).
Les variables prédéfinies de make sont $@ pour le nom de la cible, $< pour la première dépendance, ? pour les dépendances plus récentes que la cible et $* pour le nom du fichier sans suffixe.
📌 Sans règle explicite, make exécute la première règle non bidon dont le nom ne commence pas par un point, et ce comportement peut être modifié avec la variable .DEFAULT_GOAL.
Compléments
📌 Une règle générique comme %.o : %.c peut construire des fichiers selon leur suffixe ; les règles explicites définissant une recette pour une cible sont prioritaires pour cette cible, quelle que soit leur position par rapport à la règle générique.
📌 La directive .PHONY permet de déclarer des règles ne correspondant pas à des fichiers afin qu’un fichier de même nom n’interfère pas avec leur exécution.
Performances des structures
| Opération | Tableau | Liste chaînée |
|---|---|---|
| Accès | O(1) | O(n) |
| Modification | O(n) temps | O(n) temps, O(1) mémoire supplémentaire |
| Recherche | O(n) | O(n) |
Teste tes connaissances sur Unix Linux et Make avec 26 questions à choix multiples et corrections détaillées.
1. Quel objectif pédagogique central guide le projet consacré aux structures de données ?
2. Une équipe doit suivre la démarche du projet pour comparer deux structures de données. Quelle séquence d’étapes convient ?
Mémorisez les concepts clés de Unix Linux et Make avec 73 flashcards interactives.
Qu’étudie le projet concernant les structures de données et les algorithmes ?
L’influence des structures de données sur la performance des algorithmes.
Que vise le projet concernant les types abstraits ?
À comprendre les types abstraits et leurs implémentations.
Quelles étapes composent le déroulement du projet ?
Lire une base, stocker et exploiter les données, mesurer temps et mémoire, puis comparer différentes structures.
Importe ton cours et l'IA génère fiches, QCM et flashcards en 30 secondes.
Générateur de fiches