Cours IF121 (MIAS, Groupe Di Cosmo)
Enseignant: Roberto Di Cosmo
Page web du cours: http://www.dicosmo.org/IF121/
Objectifs:
connaissance elementaire des ordinateurs
connaissance elementaire d'un environnement graphique
connaissance elementaire d'un langage de programmation
(C++ restraint)
elements d'algorithmique, de conception de programmes
elements d'analyse de complexite d'un programme
Cours et TD/TP.
Cours : 4/10, 11/10, 18/10, 25/10, 8/11, 15/11, 29/11
TD/TP : 13 semaines
Contrôle des connaissances.
Pa Partiel le samedi 25 novembre
à 10h.
Ej Examen en janvier
Es Examen de septembre
CC 4 tests de 30 minutes effectués
pendant les TP.
Chaque test est noté sur
5
La présence aux tests est
obligatoires
Ecrit : NE = max (Ej, (Pa+Ej) / 2)
Note finale janvier : (2NE + CC) / 3
Note finale septembre : max(Es, (2Es + CC) / 3)
Bibliographie
Programmation en C
Méthodologie de la programmation
en langage C, J.-P. Braquelaire,
Masson, 1994. ISBN 2-225-84353-8
Programmation en C++
Le langage C++, B. Stroustrup,
Addison-Wesley, 1992. ISBN 2-87908-013-4
L'essentiel du C++, S.B. Lippman,
Addison-Wesley, 1992. ISBN 2-87908-002-9
Et aussi
Concepts fondamentaux de l?informatique,
A. Aho, J. Ullman,
Dunod, 1998. ISBN 2-10-003127-9
Cours 1
Presentation des ordinateurs:
Von Neumann:
I/O
clavier/ecran/ethernet/modem/souris etc.
CPU
UAL (ALU)
Registres
memoire: contient donnees ET programme (machine language)
primaire (centrale): RAM, (plutot volatile)
secondaire: disques, bandes, CD-R (persistente)
interconnections (bus,
reseau)
Informations de base:
bit/byte/mega/giga/tera octet Mhz etc. MIPS/MFLOPS
Difference entre calculette et ordinateur
Un peu d'histoire voir http://www.eingang.org/Lecture par exemple
Pascal (1623 - 1662), Pascaline
Babbage (1791-1871,1834 An. eng.),
http://ei.cs.vt.edu/~history/Babbage.html
Turing (1912-1954 (Turing
Machine:~1930's))
http://ei.cs.vt.edu/~history/Turing.html,
http://www.mills.edu/ACAD_INFO/MCS/CS/cs.wwwturing.html
Von Neumann (1903-1957)
http://ei.cs.vt.edu/~history/VonNeumann.html
Comment on programme un ordinateur:
Hierarchie de niveaux d'abstraction:
Materiel
Langage machine
Assembleur
Librairies systeme
Langages de programmation (C/C++/Fortran/Maple etc.)
Outils de programmation:
Editeurs (Kedit)
Compilateurs (g++)
Interface de commandes (shell)
Cycle: edition-compilation-execution
Exemple de programme simple: "Hello World"
suivi sous DDD
Exemple de programme simple: addition des premiers 10 nombres
entiers
Exemple de programme C++ plus complexe
Mandelbrot: compilation et execution
Introduction au C++
Structure d'un programme: declarations, puis programme (main())
Notion tres informelle d'instruction elementaire,
variable,
affectation,
entree/sortie
Pourquoi un pseudolangage?
Syntaxe plus libre
Niveau d'abstraction adapte au probleme a resoudre
(ex: parcourir un fichier)
lire les données
trier les données
afficher les données triées
Introduction de la structure du pseudolangage
Cours 2:
Structure d'un programme
déclarations de constantes
Pseudo :
CONSTANTE Max=100
C++ :
const int Max=100;
déclarations de types
Pseudo :
TYPE polynôme = tableau de Max réels
C++ :
typedef float polynome[Max];
déclarations de procédures et fonctions
Pseudo :
FONCTION nomFonction (liste de
paramètres) : typeRésultat
bloc
PROCEDURE nomProcédure (
liste de paramètres )
bloc
C++ :
nomType nomFonction ( liste de
paramètres )
bloc
déclaration du programme principal
Pseudo :
PROGRAMME nomProgramme
bloc
C++ :
void main ()
bloc
bloc
Pseudo :
DEBUT nom Fonction/Procédure/Programme
déclarations de constantes
déclarations de variables
liste d'instructions
FIN nom Fonction/Procédure/Programme
C++ :
{ // nom Fonction/Procédure/Programme
déclarations de constantes
déclarations de variables
liste d'instructions
} // nom Fonction/Procédure/Programme
Les variables.
Une variable est l'equivalent
au niveau du langage de programmation d'une case
mémoire de l'ordinateur:
on peut lire son contenu ou modifier son contenu.
Un programme écrit
dans un langage impératif comme C++ passe l'essentielle de
son temps à modifier
des variables, pour effectuer un calcul.
Une variable s'introduit à l'aide d'une déclaration, où l'on définit:
le nom de la variable,
le type de la variable,
eventuellement sa valeur initiale.
Dans notre pseudolangage,
on introduit au debut d'un bloc une ou plusieurs variables
dans une section nommée
variables, de la façon suivante:
variables
i:
entier
/ declaration simple /
i: entier initialisé à 320 / declaration simple avec valeur
initiale /
k,l: deux entiers
/ declaration multiple /
Aprés la déclaration
et l'initialisation, le contenu d'une variable peut etre utilisé
par
les instructions du programme.
Les instructions simples.
Pour commencer, on fera connaissance
avec les instructions simples, qui se classent
en 3 categories:
i) entree/sortie
on peut
lire une donnée en entrée, et la mémoriser dans une
variable (par ex. k)
avec l'instruction
lire k
on peut
écrire une donnée en sortie (par ex. une variable k)
avec l'instruction
ecrire k
mais on peut aussi écrire le résultat d'une expression, comme dans
ecrire 5/4-32i
On se permettra
aussi des formes generales comme
lire i j k
Au niveau
du pseudolangage, on ne se soucies pas des détails concernant l'affichage,
En C++:
lire k
devient cin>>k;
ecrire "k vaut" k "apres lecture"
comme
les espaces, les fin de ligne etc.
écrire k/2
écrire k j l
devient cout<<k<<j<<l;
et on dispose
d'une panoplie d'expressions accessoires pour passer à la ligne,
fixer le
format
de sortie etc. sur lesquels on ne passera pas de temps ici.
On se
limite à remarquer la forme C++
cout<<endl;
qui permet
de passer à la ligne suivante en sortie.
ii) affectation
on peut modifier le contenu d'une variable à l'aide de l'instruction
de affectation,
qui a la forme générale:
n <- expression
où n est le nom d'une variable, et expression est une constante,
une variable,
ou une opération plus complexe, dont le résultat deviendra
la nouvelle valeur
de la variable n
Quelques exemple:
k <- 2
k <- k
k <- i
k <- i2
Attention: dans ce dernier cas, on calcule d'abord k2 en utilisant l'ancienne
En C++:
n = expression
iii) incrementation et decrementation
à la place de
i<-i+1
on peut écrire
incrementer i
(en C++: i++; )
à la place de
i<-i-1
on peut écrire
decrementer i
(en C++: i--; )
iv)
sequencage
le corps d'un programme est essentiellement une liste d'instructions
Le fragment
lire k
valeur de k, et ensuite on utilise ce resultat comme nouvelle valeur de
k.
obtenue en juxtaposant des instructions simples
k <- k
imprime k
execute les 3 instructions dans l'ordre, en lisant un entier en entee
pour imprimer son double en sortie.
En C++, cette juxtaposition est materialisée par le caractère
;
Ainsi, le fragment ci-dessus s'ecrirait en C++
cin>>k;
k=x2;
cout<<k<<endl;
Voici enfin un exemple complet,
réalisé à l'aide des notions que l'on vient d'introduire
PROGRAMME
surface
DEBUT
surface
variables
x,y,s: trois reels
ecrire "Longueur du rectangle?"
lire x
/ modification d'une variable par lecture /
ecrire "Largeur du rectangle?"
lire y
/ modification d'une variable par lecture /
/ modification d'une variable par affectation /
s <- xy
imprimer "La surface du rectangle vaut " s
FIN
surface
Types
- en machine, toute donnée
est representée comme une séquence de bits
- dans les langages de programmation
évolués; on souhaite les classifier
(entiers, réels,
chaînes de caractéres, valeurs de verité (vrai, faux),
etc.)
Les types sont le moyen utilisé
dans ces langages pour opérer cette classification
Chaque langage propose un ensemble
de types dits "de base", plus des moyens diverses
et variés de construire
des autres types à partir des types de base, pour enrichir la
classification.
Exploration des types de base:
(à ce niveau, on
ne rencontre pas de différences substantielles entre langage C++
et pseudolangage)
C++ dispose de 5 types de
base qui nous interessent: int, float, char, string, bool,
et ces types peuvent etre
utilises dans les declarations de constantes ou variables
Exemple: le fragment de programme
int i;
float f;
char c;
string s;
bool b;
declare une variable de chacun de ces types.
Entiers
en pseudolangage: entier
en C++: int
literaux (comment écrire des constantes):
Attention! C++ permet d'ecrire des entiers en 3 bases:
10: 0 10 -1 32 etc.
8: 0 010 -011 etc.
16: 0x0 0x1 ... 0x9 0xA 0xB 0xC 0xD 0xE 0xF 0x10
On verra plus avant comment convaincre C++ à imprimer dans l'une
ou l'autre base,
si on ne fait rien, la sortie est en base dix.
opérations disponibles:
Reels
en pseudolangage: reel
literaux (comment écrire
des constantes):
Forme generale:
Formes possibles:
opérations disponibles:
+, -, , /, %
en C++: float
- un entier suivi d'un point, et eventuellement d'une partie fractionnaire
(ex: 123. 123.456)
- eventuellement suivi d'un exposant compose d'un E majuscule ou minuscule
suivi d'un entier positif ou negatif
(ex: 123.e-4 123.456E12)
- si l'exposant est present, on peut se passer du .
(ex: 2e10)
234.1231E10 (ou 234.1231e10)
234.1231E-10 (ou 234.1231e-10)
234.1231
2E3
2E-3
+, -,
Caractères
en pseudolangage: caractere
en C++: char
literaux (comment écrire des constantes):
'c' est le caractere c
SAUF pour le caractere \ qui est special: il est utilise
pour introduire les caracteres "non imprimables" comme
'\n' retour chariot
'\t' tabulation
on peut l'ecrire comme '\'
Chaînes de caractères
en pseudolangage:
chaine de caracteres
en C++: string
literaux (comment écrire des constantes):
"ceci est une chaine de caracteres"
opérations disponibles:
+ (concatenation)
s="Bonjour";
s=s+" tout le monde"; (ici s vaut "Bonjour
tout le monde")
Valeurs de verité
en pseudolangage: booleen
en C++: bool
literaux (comment écrire des constantes):
il y a seulement deux constantes
en pseudolangage: vrai, faux
en C++: true, false
opérations:
Il y a deux types d'opérations
qui font intervenir les
valeurs de verité:
les opérateurs booléens:
ils prennent en entree des valeurs booléens sur
lesquels ils effectuent une opération logique,
et renvoient un nouveau booléen
binaires: et, ou
(en C++: &&, ||)
implique
(non défini en C++)
unaires: non
(en C++: !)
les opérateurs de rélation:
ils prennent en entree des valeurs de type quelconque
sur lesquels ils effectuent une comparaison, et renvoient
un nouveau booléen
binaires: <=, >=, <, >
(identiques en C++)
= =/=
(en C++: ==, !=)
Par exemple, pour savoir
si l'entier contenu dans la variable an corresponde
à une année
bissextile, il suffira d'écrire:
(an % 4 = 0 et an % 100 =/= 0) ou (an % 400 = 0)
Présentation des opérations booléennes, et des tables de vérité pour en calculer la valeur.
Exemple: en fonction des valeurs des variables a et b, donner la valeur de l'expression
(a ou b et (non (a et b))