Algorithm 3
Mathematique L2 · DEUXIEME ANNÉE L2
10 chapitres · 0 séance
Description à venir.
Au programme
-
PLAN DU COURS / COURSE SYLLABUS
Par DR.HADJER LACHEHEB
English The Algorithms and Data Structures III course is a fundamental pillar in computer science education.Facing complex problems handling large datasets, this course focuses on mastering data structuring and theoretical complexity analysis. Algorithms and data structures are inextricably linked to design efficient, robust, and optimized solutions, independently of any specific hardware and software environment. Français Le cours d'Algorithmique et Structures de Données III constitue un pilier fondamental de la formation en informatique. Face à de gros problèmes complexes manipulant d'importants ensembles de données, ce cours vise à maîtriser la structuration des données et l'analyse de leur complexité théorique. L'algorithme et la structure de données sont indissolublement liés pour concevoir des solutions efficaces, robustes et optimisées, indépendamment de l'environnement matériel et logiciel.
-
Chapitre I : Rappels et Allocation Dynamique / Reminders & Dynamic Allocation
Par DR.HADJER LACHEHEB
English - Review of static and dynamic structures (arrays,procedures, and functions). - Data representation in main memory. - Dynamic memory allocation (pointers, allocation, and deallocation). - Linked lists (singly and doubly linked lists). Français - Rappels des structures statiques et dynamiques (tableaux, procédures et fonctions). - Représentation des données en mémoire centrale. - Allocation dynamique de mémoire (pointeurs, allocation et libération). - Les listes chaînées (simplement et doublement chaînées).
-
Chapitre II : Introduction à la Complexité des Algorithmes / Introduction to Algorithm Complexity
Par DR.HADJER LACHEHEB
English - Theoretical analysis of algorithms (execution time and memory space). - Complexity calculation in worst-case, best-case, and average scenarios. - Cost estimation and asymptotic notations (Big O notation). - Interaction between data structures and algorithmic complexity. Français - L’analyse théorique d’un algorithme (temps d'exécution et espace mémoire). - Calcul de la complexité dans le pire des cas, le meilleur des cas et en moyenne. - Estimation du coût et notations asymptotiques (Grand O). - Interaction entre structures de données et complexité algorithmique.
-
Chapitre III : La Récursivité / Recursion
Par DR.HADJER LACHEHEB
English - Definitions and construction principles of recursive algorithms. - General schemas of recursive functions (base case and recursive step). - Direct and indirect (mutual) recursion. - Execution mechanism of recursion in memory (call stack). - Elimination of recursion (transformation into iterative algorithms). Français - Définitions et principes de construction d’algorithmes récursifs. - Récursivité directe et récursivité indirecte (croisée). - Fonctionnement de la récursivité en mémoire (pile d'exécution). - Élimination de la récursivité (transformation en algorithmes itératifs)
-
Chapitre IV : Les Piles / Stacks
Par DR.HADJER LACHEHEB
English - Definition and LIFO principle (Last In, First Out). - Contiguous representation (arrays) and linked representation. - Core operations: Push, Pop, Initialize, Emptiness test. - Applications and arithmetic expression transformation (infix, postfix, prefix). Français - Définition et principe LIFO (Last In, First Out). - Représentation contiguë (tableaux) et représentation chaînée. - Opérations fondamentales : Empiler (Push), Dépiler (Pop), Initialiser, Test de vacuité. - Applications et transformation d'expressions arithmétiques (infixe, postfixe, préfixe)
-
Chapitre V : Les Files / Queues
Par DR.HADJER LACHEHEB
English - Definition and FIFO principle (First In, First Out). - Contiguous representation (circular queue) and linked representation. - Core operations: Enqueue, Dequeue, Overflow and Underflow checks. Français - Définition et principe FIFO (First In, First Out). - Représentation contiguë (file circulaire) et représentation chaînée. - Opérations fondamentales : Enfiler (Enqueue), Défiler (Dequeue), Test de saturation et de vacuité.
-
Chapitre VI : Les Arbres / Trees
Par DR.HADJER LACHEHEB
English -Definitions, terminology, and representation of tree structures. - Tree traversal methods (breadth-first, pre-order, in-order, post-order). - Ordered trees (horizontally and vertically). - Binary Search Trees (BST): insertion, search, deletion. - Introduction to heaps and applications. Français - Définitions, terminologie et représentation des structures arborescentes. - Parcours d’un arbre (parcours en largeur, préfixe, infixe, postfixe). - Arbres ordonnés (horizontalement et verticalement). - Arbres Binaires de Recherche (ABR) : insertion, recherche, suppression. - Introduction aux tas (Heaps) et applications
-
Chapitre VII : Tables de Hachage / Hash Tables
Par DR.HADJER LACHEHEB
English - Principles of hash tables and hash functions. - Collision resolution methods (chaining, linear/quadratic/probing). - Performance and complexity of search and insertion operations. Français - Principe des tables de hachage et fonctions de hachage. - Gestion des collisions (méthodes par chaînage, sondage linéaire/quadratique). - Performances et complexité des opérations de recherche et d'insertion.
-
Chapitre VIII : Algorithmes de Tri / Sorting Algorithms
Par DR.HADJER LACHEHEB
English - Review of basic sorting methods (bubble sort, selection sort, insertion sort). - Advanced variants: binary insertion sort, bidirectional bubble sort (cocktail sort). - Efficient sorting: Heap sort (Heapsort). - Comparative analysis of time complexity for sorting algorithms. Français - Rappels sur les méthodes de tri de base (tri à bulles, par sélection, par insertion). - Variantes avancées : tri par insertion dichotomique, tri à bulle bidirectionnelle (cocktail sort). - Tris performants : tri par tas (Heapsort). - Analyse comparative de la complexité temporelle des algorithmes de tri.
-
Chapitre IX : Graphes / Graphs
Par DR.HADJER LACHEHEB
English - Basic concepts and terminology on graphs (directed, undirected, weighted). - Memory representation: adjacency matrix, contiguous and linked representations. - Graph traversal algorithms (Breadth-First Search - BFS, Depth-First Search - DFS). - Shortest path algorithms (e.g., Dijkstra's algorithm). Français - Notions de base et terminologie sur les graphes (orientés, non orientés, pondérés). - Représentation en mémoire : matrice d'adjacence, représentation contiguë et chaînée. - Algorithmes de parcours de graphes (Parcours en Largeur - BFS, Parcours en Profondeur - DFS). - Algorithme du plus court chemin (ex. algorithme de Dijkstra).