Algorithmique I - 2023/2024 - Marrakech
Document Details
Uploaded by Deleted User
Université Cadi Ayyad
2023
Ilyass OUAZZANI TAYBI
Tags
Summary
These are course notes from an Algorithmic course for the 2023/2024 academic year, offered at the University Cadi Ayyad, in Marrakech. The course covers fundamental topics in computer science, specifically computer architecture and algorithms, using an introductory approach.
Full Transcript
Royaume du Maroc Université Cadi Ayyad Faculté des Sciences Semlalia Marrakech Algorithmique I Prof. Ilyass OUAZZANI TAYBI E-mail : [email protected] Département : Informatique FSSM Université Cadi...
Royaume du Maroc Université Cadi Ayyad Faculté des Sciences Semlalia Marrakech Algorithmique I Prof. Ilyass OUAZZANI TAYBI E-mail : [email protected] Département : Informatique FSSM Université Cadi Ayyad Filière TC Informatique (S1) 1 Année universitaire : 2023/2024 Compétences à acquérir 01 02 APPRENDRE LES CONCEPTS DE APPRENDRE COMMENT BASE DE L’ALGORITHMIQUE TRANSCRIRE LES DIFFÉRENTES ÉTAPES DE RÉSOLUTION D'UN PROBLÈME SOUS FORME D’ALGORITHME, DE FAÇON STRUCTURÉE ET INDÉPENDANTE DU LANGAGE DE PROGRAMMATION 2 Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 2 Plan du cours Généralités Introduction à l’Algorithmique Notions et instructions de base Structures de contrôle Tableaux Fonctions et procédures Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 3 Plan du cours CHAPITRE 1 : GÉNÉRALITÉS 1. Introduction 2. Matériel d’un ordinateur 3. Système d’exploitation 4. Langages informatiques (binaire, Assembleur, langage évolué) 5. Compilateur/Interpréteur 6. Étapes de réalisation d’un programme Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 4 I. Généralités Introduction INFORMATIQUE ? INFORMATION AUTOMATIQUE L’informatique est la science du traitement automatique de l’information. Cette informatisation permettra de réaliser un gain considérable en temps et en effort. 5 I. Généralités Introduction Un système informatique est défini comme étant composé de deux parties : Le matériel (Hardware) : l'ensemble des composantes électroniques. Le logiciel (Software) : Ensemble de programmes (ensemble d'instructions qui doivent être exécutées dans un certain ordre par la machine) a pour rôle de faire fonctionner la partie matérielle. 6 I. Généralités Introduction Un ordinateur est un appareil électronique qui permet de traiter les informations de façon automatique. 7 I. Généralités Périphériques d’entrée/sortie ENTREE SORTIE Unité centrale ENTREE SORTIE Périphériques d’entrée Périphériques de sortie Supports de stockage 8 I. Généralités Schéma fonctionnel Unité Centrale d’un ordinateur Unité Centrale de Traitement Périphériques de sortie Périphériques d’entrée Données Mémoire Centrale Unité Arithmétique Résultats et Logique Instructions de programme Unité de Commande Circulation d’informations Périphériques Circulation de commandes de Stockage 9 I. Généralités Matériel d’un ordinateur Un ordinateur est composé de plusieurs parties. L'élément principal est l'unité centrale à laquelle viennent s'ajouter des périphériques. Pour communiquer avec ses périphériques, l'ordinateur dispose de connexions filaires ou sans fil. Pour conserver ses informations, l'ordinateur dispose de supports de stockage fixes (disques durs) ou amovibles (CD, DVD ou clé USB). 10 I. Généralités Matériel d’un ordinateur - Unité centrale L’unité centrale est l’élément le plus important de l’ordinateur, c’est elle qui contient tous les organes nécessaires au fonctionnement de l’ordinateur. Elle se compose essentiellement de : La carte mère Le processeur (Central Processing Unit, CPU) La mémoire centrale Les cartes d’extension 11 I. Généralités Matériel d’un ordinateur - La carte mère L’élément constitutif principal de l’ordinateur est la carte mère (en anglais « mainboard » ou « motherboard »). La carte mère permet d’inter-connecter tous les éléments de l’ordinateur. C’est un gros circuit imprimé avec: Puces (chips) Connexions Autres pièces électroniques installé dessus. 12 I. Généralités Matériel d’un ordinateur - La carte mère 13 I. Généralités Matériel d’un ordinateur - La carte mère 14 I. Généralités Matériel d’un ordinateur – Le processeur Un processeur (ou unité centrale de traitement, UCT, en anglais Central Processing Unit, CPU) est un composant présent dans de nombreux dispositifs électroniques qui exécute les instructions machine des programmes informatiques. Sa puissance est exprimée en Hertz. 15 I. Généralités Matériel d’un ordinateur - Le processeur Un processeur est un circuit contenant les unités suivantes: Unité de Contrôle, de commande et de synchronisation (UC) Unité Arithmétique et Logique (UAL) UAL Registres Unité d’Entrées/Sorties (E/S) Registres E/S Bus internes UC 16 I. Généralités Matériel d’un ordinateur - Le processeur L’unité d'instruction (ou unité de commande, en anglais Control Unit) « Chef d’orchestre » qui pilote et synchronise les unités de l’appareil. Elle s’occupe de gérer l’exécution des instructions d’un programme, qui lui sont communiquées l’une après l’autre par la mémoire centrale puis donne les ordres aux autres organes pour coordonner leur fonctionnement lors de l’exécution de chaque instruction. 17 I. Généralités Matériel d’un ordinateur - Le processeur L‘Unité Arithmétique et Logique (UAL ou en anglais ALU pour Arithmetical and Logical Unit). L'UAL contient tous les circuits électroniques qui effectuent principalement : l’addition, la soustraction, la multiplication, la division, la négation et les opérations logiques (ET, OU, Ou exclusif, etc). 18 I. Généralités Matériel d’un ordinateur - Le processeur Lorsque le processeur exécute des instructions, les données sont temporairement mémorisées dans des petites mémoires rapides de 8, 16, 32 ou 64 bits que l'on appelle registres. Suivant le type de processeur le nombre global de registres peut varier d'une dizaine à plusieurs centaines. 19 I. Généralités Matériel d’un ordinateur - Le processeur L’Unité d’entrées/Sorties permet l’échange des informations avec l’extérieur (nécessaire au fonctionnement du CPU) Bus de donnée Unité d’entrées/ sorties (E/S) Bus d’adresse Bus de commande Intérieur du processeur Extérieur du processeur L’unité d’E/S assure les liaisons entre les bus internes et les bus externes; Les bus d’adresse sont unidirectionnels. 20 I. Généralités Matériel d’un ordinateur - La mémoire 21 I. Généralités Matériel d’un ordinateur - La mémoire vive La mémoire vive, en anglais Random Access Memory (RAM), permet de stocker des informations pendant tout le temps de fonctionnement de l’ordinateur, son contenu est modifiable c-à-d, on peut lire et écrire, et s’efface quand la machine est éteinte. Elle est caractérisée par sa capacité. On distingue généralement deux grandes catégories de mémoires vives : Les mémoires dynamiques (DRAM, Dynamic Random Access Memory), peu coûteuses. Elles sont principalement utilisées pour la mémoire centrale de l’ordinateur; Les mémoires statiques (SRAM, Static Random Access Memory), rapides et onéreuses. Les SRAM sont notamment utilisées pour les mémoires cache du processeur ; 22 I. Généralités Matériel d’un ordinateur - La mémoire morte La mémoire morte est un type de mémoire capable de stocker des données de façon permanente. C’est une mémoire qui ne peut qu’être lue. Une mémoire morte est une mémoire utilisée pour enregistrer des informations qui ne doivent pas être perdues lorsque l’appareil, qui les contient, n’est plus alimenté en électricité. La mémoire morte est une mémoire permanente, non volatile et en lecture seule. 23 I. Généralités Matériel d’un ordinateur - La mémoire morte La mémoire morte standard ROM (Read Only Memory) est un circuit programmé par son fabriquant pour contenir des informations fixes telles que les fonctions du BIOS, et qui ne peut plus être effacé ni modifié. Une mise à jour de son contenu implique donc un remplacement du circuit. La PROM (Programmable Read Only Memory) est une ROM dont le contenu est crée par un utilisateur à l’aide d’un programmateur PROM (ou brûleur). Ce dispositif utilise des tensions élevées pour détruire définitivement ou créer des liens internes (fusibles ou anti-fusibles) dans la puce (PROM). Par conséquent, une PROM ne peut être programmée qu’une seule fois. 24 I. Généralités Matériel d’un ordinateur - La mémoire morte Les EPROM (Erasable Programmable Read Only Memory) sont des PROM pouvant être effacées. Ces puces possèdent une petite fenêtre de quarte permettant de laisser passer des rayons ultra- violets provenant d’un Effaceur d’EPROM ou Brûleur d’EPROM ou Prommer. Lorsque la puce est en présence de rayons ultra-violets d’une certaine longueur d’onde, les liaisons sont reconstitués, c’est-à-dire que tous les bits de la mémoire sont à nouveau à 1. Les EEPROM (Electrically Erasable Read Only Memory) sont aussi des PROM effaçables. Contrairement aux EPROM, celles-ci peuvent être effacées par un simple courant électrique. 25 I. Généralités Matériel d’un ordinateur - Le disque dur Un ordinateur possède au moins un disque dur afin de stocker de grande quantité d’information d’une manière permanente. L’ordinateur peut avoir plusieurs disques durs en interne, connectés à la nappe de la carte mère, et/ou en externe connectés à des ports. Le boîtier d’un disque dur ne doit pas être démonté (en dehors d’une chambre blanche, sans poussière ni bactéries…) 26 I. Généralités Matériel d’un ordinateur - Le disque dur 27 I. Généralités Matériel d’un ordinateur - Les chipsets Un chipset est un ensemble de composants électroniques dans un circuit intégré qui gère le flux de données entre le processeur, la mémoire et les périphériques. Il est généralement trouvé sur la carte mère. 28 I. Généralités Matériel d’un ordinateur - Les chipsets Le chipset est souvent constitué (décomposé) de deux composants électroniques, le pont nord (Northbridge) et le pont sud (Southbridge). Le pont nord gère les échanges entre processeur, mémoire vive et mémoire vidéo, et le pont sud qui gère les échanges entre périphériques d’entrée/sortie. Les chipsets sont des composants essentiels d’une carte mère. C’est pour quoi il est important de choisir une carte mère intégrant un chipset récent afin de maximiser les possibilités d’évolutivité de l’ordinateur. 29 I. Généralités Système d’exploitation Ensemble de programmes qui gèrent le matériel et contrôlent les applications : Utilisateur 1 Utilisateur 2 … Utilisateur N Gestion des périphériques (affichage à l'écran, lecture du clavier, pilotage d’une imprimante, …) Gestion des utilisateurs et de leurs données (comptes, Compilateur Editeur Base de données Applications partage des ressources, gestion des fichiers et répertoires, …) Système d’exploitation Interface avec l’utilisateur (textuelle ou graphique): Interprétation des commandes Matériel Contrôle des programmes (découpage en taches, partage du temps processeur, …) Exemple de système d’exploitation : MS-DOS, Linux, Mac OS, Windows 10... 30 I. Généralités Langages informatiques Un langage informatique, également appelé langage de programmation, est un ensemble de règles et de conventions utilisées pour écrire des programmes informatiques. Il s'agit d'une méthode normalisée qui permet aux programmeurs de communiquer avec un ordinateur et de lui donner des instructions spécifiques pour effectuer des tâches ou résoudre des problèmes. Il existe de nombreux langages informatiques différents, chacun étant adapté à des tâches et à des domaines d'application spécifiques. 31 I. Généralités Langages informatiques - langage machine Le langage machine, également connu sous le nom de langage machine binaire, est le langage de programmation de base compréhensible par un ordinateur. Il est composé de séquences de chiffres binaires (0 et 1) qui représentent des instructions spécifiques comprises par un processeur. Chaque type de processeur a son propre ensemble d'instructions en langage machine. Écrire des programmes directement en langage machine est extrêmement difficile et propice aux erreurs. 32 I. Généralités Langages informatiques - langage assembleur Problème : le langage machine est difficile à comprendre par l'humain. Idée : trouver un langage compréhensible par l'homme qui sera ensuite converti en langage machine Assembleur : exprimer les instructions élémentaires de façon symbolique ADD A, 4 traducteur langage machine LOAD B MOV A, OUT … + : déjà plus accessible que le langage machine - : dépend du type de processeur (n’est pas portable) - : pas assez efficace pour développer des applications complexes 33 I. Généralités Langages informatiques - langage évolué Intérêts multiples pour les langage évolués (langage haut niveau) : proche du langage humain (compréhensible) permet une plus grande portabilité (indépendant du matériel) Manipulation de données et d’expressions complexes (réels, objets, a*b/c, …) Nécessité d’un traducteur (compilateur/interpréteur), Exécution plus ou moins lente selon le traducteur Code source Compilateur ou Langage machine en langage évolué interpréteur 34 I. Généralités Langages informatiques - langage évolué Langages impératifs (Pascal, C …) : Il s'agit de faire exécuter une suite d'ordres par une machine bête mais disciplinée. Langages Déclaratifs: l'activité de programmation consiste essentiellement à décrire le rapport qui existe entre les données et les résultats que l'on veut obtenir, plutôt que la séquence de traitements qui mène des unes aux autres fonctionnels (Lisp, Scheme …) logiques (Prolog … ) Langages orientés objets (C++, Java …) 35 I. Généralités Compilateur/interpréteur Compilateur : traduire le programme entier une fois pour toutes Compilateur exécution exemple.c exemple fichier source fichier exécutable + : plus rapide à l’exécution + : sécurité du code source - : il faut recompiler à chaque modification Interpréteur : traduire au fur et à mesure les instructions du programme à chaque exécution Interprétation+exécution exemple.bas fichier source + : exécution instantanée - : exécution lente par rapport aux programmes compilés 36 I. Généralités Étapes de réalisation d’un programme Enoncé du problème Spécification Cahier des charges Analyse Algorithme Traduction en langage Programme source Compilation Programme exécutable Tests et modifications Version finale et résultats 37 Merci de votre attention Pr. Ilyass OUAZZANI TAYBI Faculté des Sciences Semlalia - Marrakech 37 Royaume du Maroc Université Cadi Ayyad Faculté des Sciences Semlalia Marrakech Algorithmique I Prof. Ilyass OUAZZANI TAYBI E-mail : [email protected] Département : Informatique FSSM Université Cadi Ayyad Filière TC Informatique (S1) Année universitaire : 2023/2024