Cours d’algorithme

S.A Tabbone
Université Nancy 2
Email: tabbone@univ-
[Link]
Avant de parler
d’algorithmique
 Un peu de structure des
ordinateurs utile pour la
compréhension des programmes
 Lien :
 [Link]
/
 [Link]
musee
 [Link]
 Et tous les cours en ligne sur internet
Définition d’un ordinateur
 Machine qui saisit (périphériques
d’entrée), stocke (mémoire), traite
(programmes) et restitue
(périphériques de sortie) des
informations
 Schéma fonctionnel
Saisie Traitement Restitution

Données UC Résultats
Instructions

Mémoire

Périphériques d’entrée Périphériques de sortie

Mémoires auxiliaires

Ecran Modem
Joystick Scanner Micro Souris Disquette

CD-ROM Modem Caméra Disque dur

Clavier Imprimante
Haut parleur
 Constituants
Composants matériels (Hardware)
 Tout ce qui compose l’ordinateur et ses
accessoires
 Chaque composant possède une
fonction particulière

calcul

stockage des données

affichage vidéo

gestion du clavier...
Logiciel (Software)
 immatériel (non tangible)
 ensemble de programmes exécutables par
l’ordinateur

Différents types de logiciels

 système d’exploitation (MS-DOS, Windows, Unix)
 logiciels standards comme Word, Excel...
 progiciels : logiciels spécifiques (paye,
comptabilité, ...)

 Le logiciel pilote le matériel

Codage binaire
 Le langage des ordinateurs

 Toutes communications à l'intérieur

de l'ordinateur sont faites avec des
signaux électriques

0: éteint (absence de signal électrique)

1: allumé (présence de signal
électrique)
 Un même nombre peut être
représenté dans plusieurs bases
 123 en base 10 (décimal)
 1111011 en base 2 (binaire)
 173 en base 8 (octale)
 7B en base 16 (hexadécimale)
 De la base 10 à la base 2
 Il faut diviser le nombre par 2 puis réitérer
l'opération en considérant que le nouveau
numérateur est l'ancien quotient jusqu'à ce
que ce dernier soit nul. La suite inverse des
restes représente le nombre binaire
 Exemple

Ecrire 2006 en base 2?

 De la base 2 à la base 10
 Il faut additionner la multiplication du
nombre représenté par chaque chiffre
avec la puissance de 2 correspondant
au rang du chiffre:
 Les opérations élémentaires en
base 10 s’appliquent de la même
façon en base 2
 Exemple: Addition, soustraction,
multiplication, division
Transcodage
binaire/hexadécimal
 Un autre système, l'hexadécimal
(base 16), est très souvent employé
en informatique
 facilite la représentation des longues
séquences de bits
 représentation :

0123456789ABCDEF

101101100010000001100011010011 (binaire)

2d8818d3 (hexadécimale)
 À l'aide d'un octet on peut représenter:
 Les nombres entiers compris entre 0 et 255
 Les nombres entiers compris entre 0 et
65535 ou entre -32768 et 32767 (entiers
signés)
 Les nombres réels (représentation virgule
flottante…)
 Des instructions

une table de correspondance entre nombre et
instruction
 Des caractères

une table de correspondance entre des nombres
et des caractères (exemple ASCII (7 bits), ASCII
étendu (1 octet), UTF8 (plusieurs octets)…)
Schéma fonctionnel
 L’unité Centrale
Fonctions



Sélectionner et exécuter les instructions du
programme en cours

Partie de l’ordinateur qui contient les circuits de
base
 la mémoire principale

la mémoire vive (RAM)

la mémoire morte (ROM)
 la mémoire cache
 le microprocesseur

les circuits de calcul (UAL)

l’unité de contrôle (ou de commande)
 l’horloge système
17
 l’unité d’entrée-sortie
La Mémoire

Définition
 Dispositif capable d’enregistrer, de stocker et de

restituer des informations

 Trois types


RAM ou mémoire vive

ROM ou mémoire morte

mémoire de masse ou secondaire

Unité de stockage: Un composant électronique
capable de mémoriser des tensions:
 BIT (Binary DigiT) : unité de stockage élémentaire

 Les informations sont codées en binaires

composés de 0 et de 1
 Selon l’ordinateur, un mot mémoire est composé

de 2 (16 bits) ou 4 (32 bits) octets 18

 La Mémoire
Unités de mesure


1octet = 8 bits

1Ko (kilo octet) 1 000 octets (exactement 210

octets)

1Mo (méga octet)  1 000 000 octets (220 octets)

1Go (giga octet)  1 000 000 000 octets (230 octets)

1To (téra octet)  1 000 000 000 000 octets (240

octets)
19
La Mémoire

Structure

La mémoire est organisée en cellules (octets ou mots)

Chaque cellule est repérée par son adresse qui permet à
l’ordinateur de trouver les informations dont il a besoin

2 Modes d’accès à la mémoire

En lecture : aucun effet sur le contenu

En écriture : modifie son contenu

Caractéristiques

Capacité : nombre d’octets

Accès

direct : grâce à l’adresse, accès immédiat à
l’information (on parle de support adressable)

séquentiel : pour accéder à une information, il faut avoir
lu toutes les précédentes (ex : cassette audio)

Temps d’accès : temps écoulé entre l’instant où l’information
est demandée et celui où elle est disponible (en ms)
20
La Mémoire


Le contenu de la mémoire est composé
 de données
 et d’instructions

code de l’opération élémentaire

donnée(s) ou adresse des données


Programme
 Ensemble d’instructions et de données

Traduites en signaux électriques
compréhensibles par le matériel

21
Différentes mémoires
La mémoire vive ou RAM (Random Access
Memory)

mémoire à accès direct à taille limitée

son contenu est volatile, i.e. il est perdu à
chaque fois que l’ordinateur ne fonctionne
pas : d’où le besoin d’utiliser de la mémoire
auxiliaire rémanente

endroit où l’ordinateur stocke temporairement
les données et instructions (programmes) qu’il
est en train d’utiliser et d’exécuter

contient tous les programmes en cours d’exécution

Capacité standard de 256 Mo à 1 Go

22
La mémoire morte (Read Only
Memory)


mémoire permanente et inaltérable


contient des petits programmes écrits par le
constructeur pour la mise en route de
l’ordinateur BIOS (Basic Input/Output System)
 identifie les différents composants de la machine et
vérifie leur bon fonctionnement

23
Le mémoire cache



La transmission entre la RAM et le
microprocesseur est plus lente que le potentiel
de vitesse du microprocesseur


Mémoire cache (niveau L1 ou L2)
 zone de mémoire ultra-rapide où sont conservées
les données et instructions qui reviennent le plus
souvent
 mémoire interne de petite taille (dizaines de Ko)

Type non-volatile (Flash)


Capacité standard : 256Ko ou 512Ko
24
Le microprocesseur

Le cœur de l’ordinateur : il traite et fait circuler
les instructions et les données

Composé des éléments suivants

Unité Arithmétique et Logique (UAL)

Ensemble de circuits qui exécutent les
opérations arithmétiques et logiques
de base

Différents Registres (CO, Etat, Instruction…)

Unité de contrôle (ou de commande)

Son rôle est d’extraire une instruction
du programme en MC, de la faire
exécuter par l’UAL ou un périphérique
et de chercher l’instruction suivante

Elle décode les instructions et trouve
les données pour l’UAL

25
MICROPROCESSEUR
L’horloge


Elle contrôle et synchronise le microprocesseur
et les composants associés


Sa vitesse (fréquence) est exprimée
généralement en mégahertz (MHz) c’est-à-dire
en million de cycles par seconde


L’efficacité du microprocesseur est directement
proportionnelle à la fréquence de l’horloge :
une fréquence élevée est donc souhaitable


Exemples: Intel Pentium 4, environ 3 GHz
27
L’unité d’entrée-sortie



contrôle et gère le transfert d’informations
entre l’UC et les périphériques


Exemples
 carte graphique (écran)

 carte contrôleur (disque dur)

 carte son (micro, haut-parleur)

28
 Les Périphériques
Définition
Tout ce qui gravite autour de l’UC c’est-à-dire
l’écran, le clavier, la souris, les mémoires
auxiliaires, l’imprimante, le scanner, le micro, les
haut-parleurs....

3 Catégories de périphériques
d’entrée (clavier, souris, scanner, joystick)

de sortie (écran, imprimante, haut-parleur)

les mémoires auxiliaires (disque dur, disquette,

CD-ROM)
29
 Les périphériques d’entrée

Définition
 Recueillent les informations qui sont ensuite
transformées (numérisées i.e. codées en binaires)
pour être utilisables par la machine et transférées
en mémoire principale (mémoire de l’UC)


Exemples
 clavier
 souris : dispositif de pointage complémentaire du
clavier et de l’écran
 scanner : permet de numériser un document
 autres : écran tactile, lecteur de codes barres,
crayon optique, caméra, joystick...

30
Les périphériques de sortie



Définition
 Transmettent l’information binaire de l’UC

vers l’extérieur sous une forme

compréhensible par l’utilisateur


Exemples
 écran

 imprimante

 haut-parleurs

31
La mémoire de masse (secondaire ou
auxiliaire)
Définition
 Mémoire externe de grande capacité mais
d’accès moins rapide que la mémoire de
l’UC
 Utilisée pour stocker avant et après la mise
en marche de l’ordinateur (support
rémanent)
Exemples
 disquette : support magnétique amovible
adressable

comporte 2 faces

taille exprimée en pouces (3,5 pouces)

capacité de 1,44 Mo

temps d’accès de 15 à 100 ms

pour être utilisable, une disquette doit
être formatée, c’est-à-dire préparée à
recevoir des informations binaires
32
disque dur : support adressable
amovible ou non
 capacité : plusieurs Go
 accès plus rapide que les
disquettes
CD-ROM : support adressable
amovible
 non inscriptible (mode
lecture uniquement)
 capacité : environ 650 Mo
 Variante: inscriptible CD-RW
(lecture/écriture)
33
 Exécution d’un programme
Microprocesseur MC
Horloge 2
Unité de Contrôle 3
5

4
4
UAL

4
E/S
1
4
34
Exécution d’un programme


Chargement des instructions et des
données en MC

À chaque top d’horloge, l’unité de
contrôle ...
récupère une instruction et les
données nécessaires et les analyse
 déclenche le traitement adapté en
envoyant un signal à l’UAL ou à
l’unité des entrées-sorties
35
 Exemple simplifié
 Pour calculer 12+5, il faut une suite
d'instructions
 Transférer:

le nombre 12 saisi au clavier dans la mémoire

le nombre 5 saisi au clavier dans la mémoire

le nombre 12 de la mémoire vers un registre du
microprocesseur

le nombre 5 de la mémoire vers un registre du
microprocesseur
 demander à l'unité de calcul de faire l'addition
 Transférer:

le contenu du résultat dans la mémoire

le résultat (17) se trouvant en mémoire vers l'écran de la
console (pour l'affichage)
Du point de vue matériel:carte
mère
 Carte
électronique qui
permet aux
différents
composants de
communiquer via
différents bus de
communication
 On enfiche ces
composants sur
des connecteurs
Connecteur E/S
Microprocesseur
Pour effectuer le traitement


de l'information, le
microprocesseur possède un
ensemble d'instructions,
appelé « jeu d'instructions
», réalisées grâce à des
circuits électroniques. Plus
exactement, le jeu
d'instructions est réalisé à
l'aide de semiconducteurs, «
petits interrupteurs » utilisant
l'effet transistor, découvert
en 1947 par John Barden,
Walter H. Brattain et William
Shockley qui reçurent le prix
Nobel en 1956 pour cette
 Support pour le transistor le silicuim
 Un processeur est composé de
transistors permettant de réaliser des
fonctions sur des signaux numériques.
Ces transistors, assemblés entre eux
forment des composants permettant de
réaliser des fonctions très simples. A
partir de ces composants il est possible
de créer des circuits réalisant des
opérations très complexes. L'algèbre de
Boole (du nom du mathématicien anglais
Georges Boole 1815 - 1864) est un
moyen d'arriver à créer de tels circuits.
 L'algèbre de Boole est une algèbre se
proposant de traduire des signaux en
expressions mathématiques.

Pour cela, on définit chaque signal élémentaire
par des variables logiques et leur traitement par
des fonctions logiques.

Des méthodes (table de vérité) permettent de définir
les opérations que l'on désire réaliser, et à transcrire le
résultat en une expression algébrique.

un circuit logique un circuit qui schématise
l'agencement des composants de base (au
niveau logique) sans se préoccuper de la
réalisation au moyen de transistors (niveau
physique).
Variables logiques
 Un ordinateur ne manipule que des
données binaires, on appelle donc
variable logique une donnée
binaire, c'est-à-dire une donnée
ayant deux états possibles: 0 ou 1.
Fonction logique
 On appelle «fonction logique»
une entité acceptant plusieurs
valeurs logiques en entrée et dont
la sortie (il peut y en avoir
plusieurs) peut avoir deux états
possibles : 0 ou 1.
 Les fonctions logiques de bases sont appelées
portes logiques. Il s'agit de fonctions ayant
une ou deux entrées et une sortie:
 La fonction OU (en anglais OR) positionne sa sortie
à 1 si l'une ou l'autre de ses entrées est à 1
 La fonction ET (en anglais AND) positionne sa sortie
à 1 si ses deux entrées sont à 1
 La fonction OU EXCLUSIF (en anglais XOR)
positionne sa sortie à 1 si l'une ou l'autre de ses
entrées est à 1 mais pas les deux simultanément
 La fonction NON (appelée aussi inverseur)
positionne sa sortie à 1 si son entrée est à 0, et
vice-versa
 Tables de vérité
Exemple: additionneur 1
bit
 LOI DE MOORE

 Lors de la préparation de son discours en

1965, Gordon Moore (un des Présidents
d'Intel) fit une remarque qui reste toujours
d'actualité.

le nombre de transistors des processeurs devrait
doubler tous les 18 mois et permettre ainsi une
croissance exponentielle régulière des
performances. Cette loi s'est vérifiée au fil du
temps, et elle permet d'avoir un bon ordre de
grandeur des performances des futurs processeurs.


Exemple 6000 mille transistors en 1974, 9,5M
en1999
Mémoire
 Barrette qui s’enfichent sur la carte
mère
 Type de mémoire
 Quatre types de mémoires:
 la mémoire "EDO" (Extended Data Out),
ce type de mémoire se trouve sur les
ordinateurs déjà anciens.
 la mémoire "SDRAM" (Synchronous
Dynamic Random Access Memory), plus
rapide que l'EDO, ce type de mémoire
se trouve sur les ordinateurs récents.
 la mémoire "SDRAM DDR" (SD RAM
Double Data Rate), comme son nom
l'indique, cette mémoire est deux fois
plus rapide que la SDRAM. Ce type de
mémoire se trouve de plus en plus
dans les nouveaux ordinateurs.
 la mémoire "RDRAM" (Rambus
DRAM), cette mémoire permet un
transfert de données à des vitesses
beaucoup plus supérieures que les
technologies précédentes (SDRAM,
SDRAM DDR, etc.).
Le format
 Les barrettes SIMM à 72 connecteurs
(dont les dimensions sont
108x25mm): des mémoires capables
de gérer 32 bits de données
simultanément. Ces mémoires
équipent des PC allant du 386DX aux
premiers Pentium.
 les barrettes au format DIMM (Dual
Inline Memory Module) sont des
mémoires 64 bits. Elles possèdent
des puces de mémoire de part et
d'autre du circuit imprimé.
 les barrettes au format RIMM
(Rambus Inline Memory Module,
appelées également RD-RAM ou DRD-
RAM) sont des mémoires 64 bits
développée par la société Rambus.
 Carte d’extension
 Permet d’ajouter des fonctionnalités
(souvent de communication) comme
par exemple les cartes graphiques,
son, modem, usb, etc.
 Dans le PC et Mac, il existe
aujourd’hui deux grandes catégories
de carte qui se différencient par le
bus utilisé : PCI et AGP
Exemple carte vidéo
Bus
 On appelle bus, en informatique, un
ensemble de liaisons physiques (câbles,
pistes de circuits imprimés, etc.) pouvant
être exploitées en commun par plusieurs
éléments matériels afin de communiquer.
 Les bus ont pour but de réduire le
nombre de « voies » nécessaires à la
communication des différents
composants, en mutualisant les
communications sur une seule voie de
données.
Caractéristiques du bus
 Largeur du bus: nombre de bits
transmis simultanément
 fréquence (exprimée en Hertz): le
nombre de paquets de données
envoyés ou reçus par seconde
 Exemple débit maximal du bus:

Un bus d'une largeur de 16 bits, cadencé à une
fréquence de 133 MHz:
 16 * 133.106 = 2128*106 bit/s = 266 Mo/s
Sous-ensemble de bus
 Le bus d'adresses (appelé parfois bus d'adressage
ou bus mémoire) transporte les adresses mémoire
auxquelles le processeur souhaite accéder pour lire
ou écrire une donnée. Il s'agit d'un bus
unidirectionnel.

 Le bus de données véhicule les instructions en

provenance ou à destination du processeur. Il s'agit
d'un bus bidirectionnel.

 Le bus de contrôle (parfois bus de commandes)

transporte les ordres et les signaux de
synchronisation en provenance de l’unité de
commande et à destination de l'ensemble des
composants matériels. Il s'agit d'un bus directionnel
dans la mesure où il transmet également les signaux
de réponse des éléments matériels.
 Principaux bus
 le bus système (appelé aussi bus interne). Le bus
système permet au processeur de communiquer
avec la mémoire centrale du système

 le bus d'extension (parfois appelé bus

d'entrée/sortie) permet aux divers composants de
la carte-mère (USB, série, parallèle, cartes
branchées sur les connecteurs PCI, disques durs,
lecteur/graveur de CD-ROM…) de communiquer
entre eux mais il permet surtout l'ajout de
nouveaux périphériques grâce aux
connecteurs d'extension (appelés slots)
connectés sur le bus d'entrées-sorties.
 Slots:
 des prises qui sont présentes sur la
carte mère. Ces connecteurs sont
prévus pour recevoir des cartes qui
conviennent à ces différents standards.
 Ce qui différencie ces trois types de
cartes c'est leur rapidité. Dans l'ordre,
du plus lent au plus rapide :

Les cartes au format ISA

Les cartes au format PCI

Les cartes au format AGP
Norme Largeur du bus (bits) Vitesse du bus (MHz) Bande passante (Mo/sec)

ISA 8-bit 8 8.3 7.9

ISA 16-bit 16 8.3 15.9

EISA 32 8.3 31.8

VLB 32 33 127.2

PCI 32-bit 32 33 127.2

PCI 64-bit 2.1 64 66 508.6

AGP 32 66 254.3

AGP(x2 Mode) 32 66x2 528

AGP(x4 Mode) 32 66x4 1056

AGP(x8 Mode) 32 66x8 2112

ATA33 16 33 33

ATA100 16 50 100

ATA133 16 66 133

Serial ATA (S-ATA) 1 180

Serial ATA II (S-ATA2) 2 380

USB 1 1.5

USB 2.0 1 60

Firewire 1 100

Firewire 2 1 200

SCSI-1 8 4.77 5

SCSI-2 - Fast 8 10 10

SCSI-2 - Wide 16 10 20

SCSI-2 - Fast Wide 32 bits 32 10 40

SCSI-3 - Ultra 8 20 20

SCSI-3 - Ultra Wide 16 20 40

SCSI-3 - Ultra 2 8 40 40

SCSI-3 - Ultra 2 Wide 16 40 80

SCSI-3 - Ultra 160 (Ultra 3) 16 80 160