Data Structure
Fondamentaux des structures de données et algorithmes
Ce que vous apprendrez
- Comprendre les types de structures de données de base et non de base
- Comprendre le lien entre structures de données et conception d'algorithmes
- Distinguer les structures linéaires et non linéaires
- Comprendre la représentation des expressions arithmétiques
- Utiliser une pile pour convertir entre les formes d'expressions
- Distinguer les structures statiques et dynamiques
- Programmer les algorithmes de pile en langage C
- Comprendre la file et programmer ses opérations de base
À propos du cours
Ce cours explique les structures de données et leur lien avec la conception d'algorithmes et la programmation. Les structures de données sont les manières d'organiser l'information dans un programme pour qu'elle soit facile à stocker et à retrouver. Le cours commence par une introduction, puis le lien entre structures de données et conception d'algorithmes, et les types de structures : de base et non de base, linéaires et non linéaires. Vous apprenez ensuite à représenter les expressions en notation infixe, préfixe et postfixe et à utiliser une pile pour passer de l'infixe au postfixe, puis les structures statiques et dynamiques en deux parties. Vous approfondissez la pile et les algorithmes de ses opérations de base, avec un exemple complet en langage C et une mise en oeuvre pratique du code, puis vous découvrez la file, le fonctionnement de ses pointeurs et les algorithmes de ses opérations de base. Le cours comprend un cahier de travail à télécharger. Il convient aux étudiants en informatique et aux programmeurs débutants. Il vaut mieux connaître les bases de la programmation avant de commencer pour suivre facilement les exemples. À la fin, vous saurez choisir la bonne structure pour un problème et programmer vous-même une pile et une file.
Résultats attendus
- Maîtriser les concepts fondamentaux des structures de données.
- Mettre en œuvre des algorithmes en utilisant différentes structures de données.
- Comprendre comment optimiser les performances des programmes en utilisant des structures de données appropriées.
- Utiliser le langage de programmation C pour appliquer les concepts et algorithmes acquis.
Avis des apprenants
Contenu du cours
1Structure de données
15 leçons
- IntroductionIntroduit le cours sur les structures de données : leur rôle dans l'organisation des données et l'efficacité des programmes, et les thèmes (tableaux, listes chaînées, piles, files, arbres, graphes) avec algorithmes en C.5:05
- Relation des structures de données avec la conception d'algorithmes et la programmationMontre le lien entre structures de données et algorithmes et leur importance dans la conception de programmes, et définit les termes de base (briques, variable, enregistrement, champ), avec des exemples en C++.22:41
- Types de structures de donnéesExplique le besoin de structures de données : organisation, rapidité, mémoire, temps réel et réutilisabilité, puis les types de données (nombres, caractères) et la distinction entre structures primitives et non primitives.23:44
- Structures de données non primitives (linéaires et non linéaires)Explique les structures non primitives linéaires et non linéaires : tableaux, leur déclaration en C++ et les limites d'insertion et de suppression, listes chaînées (noeuds, avantages) et file circulaire.24:36
- Concepts de représentation des expressions infix/prefix/postfixExplique la pile (stack), l'ajout et le retrait au sommet et ses usages comme la récursivité, puis les notations infix, prefix et postfix et pourquoi l'ordinateur préfère les deux dernières.23:53
- Comment utiliser la pile pour convertir de l'infix à postfixExplique l'algorithme de conversion d'une expression infix en postfix avec une pile selon la priorité des opérateurs, puis présente la file (queue) et son principe premier entré, premier sorti, avec des exemples.24:26
- Structures de données non linéairesExplique les structures non linéaires : les arbres et leur vocabulaire (noeud, racine, feuille, profondeur, hauteur, frères, ancêtres), leurs usages (codage, décisions dans les jeux), puis les graphes et la recherche de chemins.19:02
- Structures de données statiques et dynamiques (partie un)Explique les graphes avec sommets, arêtes et poids, la recherche du plus court chemin, leur différence avec les arbres, les graphes orientés ou non, et leurs usages (cartes, réseaux sociaux, e-commerce).10:48
- Structures de données statiques et dynamiques (partie deux)Compare les structures statiques et dynamiques (allocation mémoire, flexibilité, accès), présente des opérations comme le tri et la fusion, puis les types de données abstraits (ADT) et leurs avantages.21:15
- Plongée dans le concept de la pileApprofondit la pile : le pointeur top et la détection pile vide ou pleine, les opérations count, change et display, puis l'algorithme push en pseudo-code et sa traduction en fonction C.27:46
- Algorithmes des opérations de base pour la pileExplique l'algorithme pop d'une pile en pseudo-code avec test de pile vide, sa traduction en C avec valeur de retour, la différence entre top-- et --top, et annonce un programme complet sur la pile.16:44
- Exemple complet en C sur la pileParcourt un programme C complet sur les opérations de pile : bibliothèques, pile représentée par un tableau, déclaration des variables, fonctions prédéfinies ou définies par l'utilisateur, lecture avec scanf et affichage du menu.13:58
- Mise en œuvre pratique du code de pile complet pour différents casExplique la suite du programme C de pile : boucle while, instruction switch pour push, pop, show et exit, cas par défaut, fonction push et spécificateurs de format.13:34
- Comprendre la file d'attente et le fonctionnement de ses indicateursExécute le programme C de pile et teste ses options, puis passe à la file (queue) et ses usages (appels, mémoire tampon multimédia), les opérations enqueue et dequeue et les types (circulaire, à priorité).25:20
- Algorithmes des opérations de base pour la file d'attenteExplique la représentation d'une file par un tableau avec les pointeurs front et rear et les états vide et plein, ainsi que les algorithmes d'ajout et de suppression en pseudo-code et l'évolution des pointeurs.23:24
2Extensions
1 pièces jointes
- Télécharger le cahier d'exercices
Formateur
Dr. Eng. Mohamed Al-Khodour
