1

1.Nouveau programme informatique.

2.Historique.

3.Données & Information.

4.Primitives de l’algorithmique.

5.Les méthodes d’analyse.

6.Structures de données.

7.Langages.

8.Compilateurs.

2

Objectifs :

- Présenter les principes de l’algorithmique et de la programmation.

- Analyse et rédaction de programmes clairs, courts et précis.

La 1ère partie du programme est consacrée aux primitives de l’algorithmique et les méthodes de programmation.

Le but étant d’avoir les compétences suivantes :

1. Maîtrise de la méthode de programmation descendante.

2. Programmation modulaire.

3. Jeu de test pour validation des solutions et des documentations.

4. Maîtrise de quelques méthodes de programmation : itérative, récursive, …

Nouveau programme informatique

3

La 2ème partie du programme est consacrée aux structures des données.

L’élève doit acquérir les compétences suivantes :

1. Représentation optimale des données afin de les traiter dans un algorithme.

2. Réalisation d’algorithmes en fonction des structures de données utilisées (influence des structures sur l’algorithme).

3. Gestion de la mémoire dynamique.

4. Utilisation des traitements des structures des données dans la résolution des problèmes théoriques et réels (réservation, file d’attente, …)

4

Didactique :

• Choix des données en fonction de la problématique.

• Nécessité d’organisation de données et de traitement.

• Présentation et étude des différents types de structures des données.

• Choix de la méthode de programmation appropriée.

• Les exemples et applications sont issus des matières enseignées en CPGE.

• Une activité algorithmique intégrée dans les autres disciplines enseignées en termes d’applications (analyse numérique, …).

• Transcription des algorithmes en langage de programmation.

• Il est recommandé de mettre l’accent sur l’aspect algorithmique beaucoup plus que sur le langage de programmation lui-même.

5

I- Préliminaire ! :

1. Information et sa représentation sur PC (binaire, codage, conversion)

2. Structure d’un ordinateur : les principaux composants.

3. Principe de fonctionnement d’un ordinateur.

4. Définitions :

Algorithme.

Code machine.

Programme.

Langage de programmation.

Compilateur et Compilation.

Programme informatique

6

II- Méthodes de programmation :

1- Les éléments de base d’un algorithme :

Les données : Notion de Données, de Variables et de Constantes.Les types simples.Affectation.

Les entrées / sorties standards et fonctions prédéfinis.

La sélection : La sélection simple et réduite.La sélection imbriquée.Le choix multiple.Expression logique et algèbre de boole.

L’itération : La boucle déterministe.La boucle indéterministe.Les boucles imbriquées.

La démarche d’analyse descendante

7

Les tableaux et chaînes de caractères :

Tableau à une dimension.Tableau à deux dimensions.Manipulation de chaînes de caractères.

Programmation modulaire :

Définition et paramètres de Procédure et de Fonction.Variable locale et variable globale.Passage par valeur et passage par référence.

Les exemples sont issus du programme de mathématiques (arithmétique, algèbre linéaire, analyse,…) :

Algorithme d’exponentiation rapide, Pivot de Gauss, Algorithme d’Euclide, Calcul matriciel, résolution d’équations numériques, calcul polynômial, ...

Des algorithmes de Tri et de recherche : Recherche séquentielle, Tri simple d’un tableau, Tri par sélection, Tri par insertion, Tri à bulles, ...

8

2- Récursivité simple

• Principe de la récursivité simple.

• Exemples d’utilisation de la récursivité simple.

• Occupation de mémoire (Pile).

• Terminaison d’une fonction récursive.

• Récursivité et Itération (champs d’utilisation).

Exemples d’algorithmes récursifs et itératifs :

Factorielle, Puissances entières, Suites récurrentes, PGCD,…

9

III- Structures de données :

Définition et rôle des structures de données en programmation.

1- Les enregistrements :

Définition et manipulation d’enregistrement 

Manipulation globale et par champ.

2- Allocation dynamique de la mémoire

Notion d’adresse mémoire.

Allocation et libération de mémoire.

10

3- Les listes chaînées.

Déclaration d’une liste chaînée.

Création d’une liste chaînée.

Fonctions de manipulation de listes : insertion, suppression, recherche, tri, MAJ, … (utilisation de la récursivité et de l’itération).

4- Les Piles et les Files.

Définition d’une Pile / d’une File.

Fonctions de manipulation d’une Pile / d’une File.

Exemples : Évaluation d’expressions arithmétiques, …

L’étude des structures de données (enregistrement, liste chaînée, etc.) doit se faire à l’aide d’exemples illustratifs accompagnés de schémas.

11

La science informatique

Une définition : « la science informatique est l’étude des algorithmes, incluant:• leurs propriétés formelles et mathématiques;• leurs réalisations concrètes;• leurs descriptions dans un langage donné; et,• leurs applications. »

selon cette définition … : les ordinateurs sont aux informaticiens ce que les télescopes sont aux astronomes (Dijkstra)

12

• Fondements mathématiques et théoriques– Logique.– mathématiques discrètes.

• Architecture des ordinateurs.• Systèmes d’exploitation.• Langages de programmation.• Réseaux informatiques.• Gestion de l’information.• Sécurité.• Systèmes intelligents.• Interaction entre ordinateurs et humains.• etc.

13

Algorithme du surnom latin Algorismi du mathématicien Arabe Al Khwarizmi.

Al Khwarizmi (780-850), natif de la région de Khwarezm (aujourd'hui Khiva), au sud de la Mer d'Aral (Ouzbékistan), mort à Bagdad.

On connaît son manuscrit d'algèbre "Kitab al-Mukhtasar fi Hisab al-Jabr w'al-Muqàbala", traitant de la résolution des équations traduit en occident sous le titre "Dixit Algorismi".

Autre ouvrage : "Kitab al Jami wa al Tafriq bi Hisab al Hind" (livre de l'addition et de la soustraction d'après le calcul des indiens). C'est le 1er livre arabe connu où la numération décimale de position et les méthodes de calcul d'origine indienne font l'objet d'explications détaillées.

Historique

14

• L’algorithmique est une science ancienne (ex: algorithme d’Euclide pour calculer le PGCD)

• pgcd(m, n) = pgcd(m − n, n) si m > n• pgcd(m, n) = pgcd(m, n − m) si m < n

• La programmation est une science nouvelle [Knuth, the Art of Computer programming]).

• Métier à tisser (1801) : ancêtre des cartes perforées• Développement de programmes assembleur à partir des 40’s.

15

• Une machine est un objet, réel ou théorique, qui est capable de :– mémoriser un algorithme, – exécuter les opérations élémentaires qui composent cet algorithme, – enchaîner ces opérations élémentaires en respectant l’ordre imposé par

l’algorithme.

• Exemples de telles machines– La machine de Turing– Un PC– La machine virtuelle de Java (JVM - Java Virtual Machine)

• L’algorithme est une solution conceptuelle, le programme est la solution technique mettant en œuvre l’algorithme.

• Au début de l’informatique, les langages étaient proches de la machine – une solution conceptuelle était difficile à mettre en œuvre sans de

bonnes connaissances techniques.

Machine

16

Architecture interne d’un ordinateur

unité centrale mémoireprincipale

contrôleur

lecteurCD/DVD

contrôleur

disquedur

contrôleur

port USB

cartegraphique

moniteur

carteréseau

internet

unité de contrôle

unitéarithmétique

et logiqueregistres

cachebus

carte

mère

17

Abaque romainchiffres notés par des cailloux (calculus)

Mémoire de sauvegarde

Données & information

RAMDisque Dur

– Identificateur : Y– Type : réel– Valeur : 3,7

Mémoire centrale(mémoire vive)

25X

3,7Y

– Identificateur : X– Type : entier– Valeur : 25

18

• Nombres entiers:– 8 bits donnent :

• nombres positifs : 0 à 255 nombres signés: -128 à +127• Nombres réels sur 32 bits (e.g. 6.02×1023)

• Caractères : codage (valeur numérique caractère)– ex.: code ASCII à 8 bits (256 choix)

ASCII : « American Standard Code for Information Interchange »– ex.: code Unicode à 16 bits (65536 choix)

Représenter de l’information binaire

Code ASCII caractère correspondant

50 ‘2’

51 ‘3’

19

La Fonction Mémoire

MEM

Adresse

Donnée

Ecriture

MEM

Adresse

Donnée

Lecture Caractéristiques

Nombre de mots(Largeur du bus d’adresse)

Taille d’un mot(Largeur du bus de données)

Temps d’accès

Coût

20

Code objet du programme

Valeurs constantes

Piles d’appels de fonctions

Allocation dynamique de mémoire

CodeCode

Données statiquesDonnées statiques

TasTas

PilePile

Mémoire et exécution