République Démocratique Du Congo
ENSEIGNEMENT SUPERIEUR, UNIVERSITAIRE, RECHERCHE SCIENTIFIQUE
ET INNOVATION
INSTITUT SUPERIEUR D'INFORMATIQUE,
PROGRAMMATION ET ANALYSE
____ I.S.I.P.A. ____
B.P. : 1895
KINSHASA 1
ALGORITHMES ET STRUCTURES DES
DONNEES AVANCEES
MPONGO LOMINGO Emet
Exp. KANKU
Année académique : 2025 - 2026
1. Parlez sur les concepts algorithmiques suivant en s’appuyant
sur des exemples concrets et des références relatives
a) Algorithme de Calculabilité
La calculabilité cherche à savoir quels problèmes peuvent réellement être
résolus par un ordinateur, et lesquels sont impossible à traiter, même
théoriquement.
Certains problèmes ne peuvent pas être résolus par un programme, peu
importe la puissance de l’ordinateur
Exemple : Créer un programme qui arrive à prédire correctement l’avenir des
utilisateurs, c’est impossible.
b) Algorithme de Complexité
Science qui mesure si un algorithme est rapide ou lent, et la quantité de la
mémoire qu’il consomme.
Ça évalue le temps et la mémoire requis quand la taille des données augmente
Exemple : Trouver un nom dans une liste de présence non trié, c’est long et ça
prend du temps, mais trouver un mot dans un dictionnaire est beaucoup plus
facile car le dictionnaire est trié par ordre alphabétique.
c) Algorithme de Récursivité
C’est la manière de résoudre un problème en le divisant en plus petits
problèmes similaires.
Explication : Résout un problème en le réduisant à des versions plus petites du
même problème
Exemple : Calculer 4 ! = 4 × 3 ! = 4 × 3 × 2 ! = 4 × 3 × 2 × 1
C’est aussi un peu comme on fait dans la modélisation, on divise le problème
en morceau pour mieux le résoudre.
d) Programmation Dynamique
La programmation dynamique permet d’éviter de refaire plusieurs fois les
mêmes calculs.
On mémorise les résultats intermédiaires pour éviter de refaire ce même
calcule, donc c’est un gain de temps
Exemple : le calcul du plus court chemin dans un réseau, on calcule et on
mémorise le chemin court et ça va nous servir dans les calculs qui viennent.
e) Programmation Linéaire
La programmation linéaire sert à optimiser quelque chose tout en respectant
des contraintes.
Trouve la meilleure solution quand on a des limitations précises
Exemple : Maximiser les profits d’une boulangerie avec des quantités limitées
de farine, sucre et beurre
f) Algorithme d’Approximation
Solution approchée pour problèmes complexes, il donne des réponses qui sont
très proches de la bonne au moment où on a les incapacités à être précis ou
soit la réponse parfaite est très coûteuse.
Exemple : Trouver un itinéraire raisonnable pour livrer des colis sans chercher
le trajet absolument le plus court
g) Algorithme Paramétré
Les algorithmes paramétrés simplifient un problème difficile en se focalisant
sur un petit paramètre k.
La difficulté dépend surtout d’un paramètre particulier du problème
Exemple :
· Trouver k points proches dans une carte
· Si k est petit, c’est facile même avec une grande carte
h) Algorithme Probabiliste
Les algorithmes probabilistes utilisent le hasard dans leur manière de
fonctionner.
Ça donne une réponse correcte avec une forte probabilité
Exemple : Tester si un nombre est premier en faisant plusieurs tests rapides
avec des nombres aléatoires
2. Concepts informatiques de gestion des données
a) Enregistrement de données
Un enregistrement est une structure de données qui rassemble plusieurs
éléments d’information (champs) de types potentiellement différents.
Par exemple, un enregistrement « Étudiant » pourrait contenir les champs : ID
(entier), Nom (texte), Date de naissance (date).
b) Sauvegarde de données
Création de copies de sécurité des données pour les protéger contre la perte
(erreur humaine, panne, cyberattaque).
Il y’a plusieurs sortes de sauvegarde notamment :
Sauvegarde complète : Copie de toutes les données.
Sauvegarde incrémentielle : Ne sauvegarde que les données modifiées
depuis la dernière sauvegarde
Sauvegarde différentielle : Sauvegarde toutes les données modifiées
depuis la dernière sauvegarde complète.
c) Transfert de données
Processus de déplacement de données entre systèmes, par exemple pour une
migration vers le cloud ou un archivage.
Il peut être manuel ou automatique.
d) Insertion de données
C’est l’action d’insérer (enregister) les données dans une table ou un fichier des
donnes et ça se fait souvent via des requêtes SQL
‘’insert into etudiant (id, nom) values (08, ‘’mpongo’’) ;
e) Modification de données
C’est apporter une modification sur les données se trouvant sur une table ou
fichier des données
Avec les requêtes de modification on arrive à le faire (UPDATE…) ça fait
également partie des opérations de langage de manipulation des données
f) Suppression de données
Opération critique qui consiste à retirer des données. Une suppression
sécurisée nécessite des outils spécifiques, car la simple suppression d’un fichier
ou le formatage d’un disque ne suffit pas toujours à effacer définitivement les
données. En SQL, la commande est DELETE.
g) Fusion de données
Ensemble de méthodes visant à agréger des données provenant de sources
hétérogènes pour obtenir une information plus sûre, plus précise et plus
pertinente. Un exemple classique est la combinaison de données de capteurs
différents (optique, infrarouge, radar) pour produire une image satellite plus
complète.
h) Éclatement de données
Phénomène où les blocs d’un fichier sont stockés de manière non contiguë sur
un disque dur, ce qui ralentit les temps d’accès. L’opération inverse, la
défragmentation, réorganise les données pour améliorer les performances. Ce
concept existe aussi en mémoire (fragmentation de la mémoire vive) et dans
les réseaux (fragmentation des paquets).
i) Tri de données
Opération qui consiste à organiser des données selon un ordre spécifique
(alphabétique, numérique, chronologique). C’est une technique fondamentale
de manipulation des données qui facilite leur évaluation, leur visualisation et
leur analyse ultérieure. Des algorithmes comme le tri rapide ou le tri fusion
sont utilisés pour cela.
j) Rupture de données
Ce concept est moins directement traité dans les sources. Il fait généralement
référence à une opération de génération de rapports où les données sont triées
par une clé (ex : « Département »), et le traitement est interrompu à chaque
changement de valeur de cette clé pour produire un sous-total ou un résumé.
C’est un concept lié au traitement par lots des données.