Introduction à la Programmation - MONTEFIORE...MacBook-Pro-de-Raph:Code raph$ ./valeureux Valeureux...

Introduction àla Programmation

Enseignant : Samuel Hiard

Année Académique 2020 - 2021

1

Agenda

• Introduction

• Chapitre 1: Blocs, Variables, Instructions Simples

• Chapitre 2: Structures de Contrôle

• Chapitre 3: Structures de Données

• Chapitre 4: Modularité du Code

2

Agenda

• Introduction• Question

• Organisation d'un Ordinateur

• Système d'Exploitation

• Algorithme

• Programme

3

Agenda

• Introduction• Question

• Organisation d'un Ordinateur

• Système d'Exploitation

• Algorithme

• Programme

4

Question

•C'est quoi l'informatique?

5

Agenda

• Introduction• Question

• Organisation d'un Ordinateur• Schéma Général

• Processeur

• Mémoire

• Entrées/Sorties

• Système d'Exploitation

• Algorithme

• Programme

6

Schéma Général

7

Bus

Processeur MémoiresEntrées

/Sorties

UC

UALRegistr

esMSMC

Processeur

• Central Principal Unit (CPU)

• Composé de 3 parties• Unité Centrale (UC)

• Registres

• Unité Arithmétique et Logique (UAL)

8

Processeur (2)

•Unité Centrale• transfert d'information depuis la mémoire

• décodage et exécution des instructions

•Registres• mémoires très rapides situées dans l'UC

• 3 types de registres:• registres adresses

• désignent un élément de la mémoire

• registres données• représentent une valeur

• registres d'état• représentent une partie de l'état du processeur

9

Processeur (3)

•Unité Arithmétique et Logique• décodage des fonctions

• opère sur les registres

• opérations arithmétiques de base• +, -, ×, /

• opérations logiques• &, |, >>, <<

•Performances d'un CPU?• liées à la fréquence d'horloge et à la nature du CPU

• mesurées en MIPS• millions of instructions per second

10

Mémoire

• Il existe deux types de mémoire•mémoire vive

• aka mémoire centrale

• RAM

•mémoire morte• aka mémoire secondaire

• ROM

1

1

Mémoire (2)

• Mémoire Centrale• cases numérotées

• taille standard d'une case: 8 bits

• toute valeur écrite dans une case persiste tant qu'elle n'est pas modifiée et que la machine fonctionne

• adresse: numéro de la case

• contenu• instructions du programme

• données du programme

12

18,896

bfda231c

adresse

valeur

Mémoire (3)

•Mémoire Secondaire• mémoire persistante même quand la machine est éteinte

• adressage symbolique (par nom) à des groupes de données (fichiers)

13

(c) Wikipedia

Un disque dur en fonctionnement

Entrées/Sorties

• Permet d'interagir avec le monde extérieur et l'utilisateur

• écran

• clavier

• disque dur

• réseau

• ...

15

Agenda

• Introduction• Question

• Organisation d'un Ordinateur

• Système d'Exploitation

• Algorithme

• Programme

16

Système d'Exploitation

• L'ordinateur "nu" est totalement inexploitable

•Un ordinateur dispose d'un mécanismed'initialisation• permet de charger un programme particulier

• système d'exploitation (OS)

• L'OS gère pour l'utilisateur les ressources de la machine et en assure une vision conviviale

•Exemples• Windows

• UNIX

• Linux

• BSD

• Mac OS17

Agenda

• Introduction• Question

• Organisation d'un Ordinateur

• Système d'Exploitation

• Algorithme• Définition

• Factorielle

• PGCD

• Programme

18

Définition

•Algorithme?• procédure permettant de résoudre un problème en

décrivant précisément les différentes opérations à effectuer sur base d'un ensemble de données

•Exemples• recette de cuisine

• racine carrée d’un nombre positif à une certaineprécision près

• déterminer si un nombre naturel est premier ou non

• calculer le plus court chemin entre 2 points dans un espace donné

• ...

19

Factorielle

•Fonction factorielle• n! = n × n-1 × n-2 × 1, n ≥ 1

•Solution:• calculer explicitement le produit de tous les entiers

strictement positifs qui sont inférieurs ou égaux à n

20

PGCD

•Plus grand commun diviseur (PGCD)•∀ a, b ≥ 1, calculer le nombre entier pgcd(a, b) qui divise à la fois a et b

•Exemples:• pgcd(24, 18) = 6

• pgcd(10, 10) = 10

• pgcd(1, 107) = 1

21

PGCD (2)

•Solution 1 (brute force approach)• déduction de l’énoncé

• 1 ≤ pgcd(a, b) ≤ min(a, b)

•Algorithme• énumérer tous les entiers dans l’intervalle [1, min(a,b)]

• tester si ils divisent à la fois a et b

• garder le plus grand entier qui satisfait cette condition

•Ca fonctionne...• ...mais coût prohibitif pour de grandes valeurs de a et

b

22

PGCD (3)

• Solution 2 (Algorithme d’Euclide)• Observation

• ∀ a, b ≥ 1: pgcd(a, b) = pgcd(b, a)

• Si un nombre divise à la fois a et b, alors il divise également leurdifférence

• Déduction: ∀ a, b ≥ 1, a ≤ b, on a

✦pgcd(a, b) = pgcd(a, b-a)

✦pgcd(a, b) = pgcd(a, b % a)• en considérant que

✦∀ n ≥ 1, pgcd(n, 0) = n

✦x % y dénote le reste de la division (modulo) de x par y

• Modulo?• x/y ⇒ x = q × y + r

• 0 ≤ q, r < y,

• q = ⎣x/y⎦ et r = x % y

23

PGCD (4)•Algorithme d’Euclide pgcd(a,b)

1.si a > b • alors permuter a et b

• sinon ∅

2.Tant que a ≠ 0, répéter• remplacer (a, b) par (b % a, a)

3.Retourner la valeur de b

• Illustration: pgcd(24, 18)

24

Etape a b

0 24 18

1 18 24

26 18

0 6

3 0 6

Agenda

• Introduction• Question

• Organisation d'un Ordinateur

• Système d'Exploitation

• Algorithme

• Programme• 3 Etapes

• Code Source

• Compilation

25

3 Etapes

• 3 étapes pour un programme• lire les données en entrées

• effectuer des calculs

• écrire les données en sortie

26

TraitementInput Output

Code Source

27

/*

* Exemple de programme

* valeureux.c

*/

#include <stdio.h>

int main(){

printf(“Valeureux Liégeois,\n”);

printf(“Fidèles à ma voix,\n”);

printf(“Volez à la victoire!\n”);

}//fin programme

Commentaires

dérive de compilation

bloc d'instructionsordonnancement

instruction

Code Source (2)

28

Code Source (3)

•Comment exécuter le programme?• l'ordinateur ne comprend pas les langages de

programmation

•Nécessité de transformer le programme enquelque chose de compréhensible par l'ordinateur• compilation

29

Compilation

•Compilation• transforme un programme écrit dans un langage de

haut niveau (e.g., C) en un ensemble d'instructionsexécutables par la machine

• vérifie aussi• la syntaxe

✦principes et règles permettant de construire des phrases

✦façon dont les mots-clés du langage se combinent pour construire un programme

• la sémantique

✦donne un sens au programme

•Compilateur• programme qui effectue le processus de compilation• en C, il s'agit de gcc

30

Compilation (2)

31

Compilation

valeureux.c Optimisation

Machine Cible

Analyse

Syntaxique

Analyse

SémantiqueGénération

Code

Compilation (3)

32

• Exemple de compilation et exécution

Compilateur

Exécutable

Source

MacBook-Pro-de-Raph:Code raph$ gcc -o valeureux valeureux.c

MacBook-Pro-de-Raph:Code raph$ gcc -o valeureux valeureux.c

MacBook-Pro-de-Raph:Code raph$ ./valeureux

Valeureux Liégeois,

Fidèles à ma voix,

Volez à la victoire!

MacBook-Pro-de-Raph:Code raph$