Algorithmes et C appliqués aux Systèmes Numériques

John Samuel

CPE Lyon

Année: 2019-2020
Courriel: john(dot)samuel(at)cpe(dot)fr

Creative Commons License

Algorithmes et C appliqués aux Systèmes Numériques

Objectifs

Algorithmes et C appliqués aux Systèmes Numériques

Bonjour le Monde!!

/* Fichier: bonjour1.c
* affiche 'Bonjour le Monde!!!' à l'écran.
* auteur: John Samuel
* Ceci est un commentaire sur plusieurs lignes
*/

#include <stdio.h> // headers

// Ceci est un commentaire sur une ligne
int main() {
  printf("Bonjour le Monde !!!");
  return 0;
}

Algorithmes et C appliqués aux Systèmes Numériques

Structures de contrôle

Algorithmes et C appliqués aux Systèmes Numériques

Memoire virtuelle

Adresses physiques
la conversion des adresses virtuelles en adresses physiques
La conversion des adresses virtuelles en adresses physiques

Algorithmes et C appliqués aux Systèmes Numériques

La chaine de compilation

Compilation:gcc

Algorithmes et C appliqués aux Systèmes Numériques

File

File

Algorithmes et C appliqués aux Systèmes Numériques

Pile

Pile

Algorithmes et C appliqués aux Systèmes Numériques

Graphe

Graphe

Algorithmes et C appliqués aux Systèmes Numériques

Déroulement du module

Groupe Déroulement
Groupe TP Cours et Travaux pratiques
Groupe Projet Projet

Algorithmes et C appliqués aux Systèmes Numériques

Environnement de programmation:

Cours:

Algorithmes et C appliqués aux Systèmes Numériques

Cours Dates
Cours 1 9 septembre
Cours 2 24 septembre
Cours 3 8 octobre
Cours 4 22 octobre
Cours 5 6 novembre

Cours

Déroulement du cours

Algorithmes et C appliqués aux Systèmes Numériques

Travaux pratiques et Projet

Algorithmes et C appliqués aux Systèmes Numériques

Évaluation

Groupe Évaluation
Groupe TP 40% TP et 60% DS
Groupe Projet 40% Projet et 60% DS

Algorithmes et C appliqués aux Systèmes Numériques

TP Points
TP 1 1
TP 2 3
TP 3 3
TP 4 4
TP 5 4
TP 6 5
TP 7 (BONUS, max. 2)

Algorithmes et C appliqués aux Systèmes Numériques

Travaux pratiques

Chaque question a un niveau de difficulté

Algorithmes et C appliqués aux Systèmes Numériques

Travaux pratiques et Projet: Rendus

  1. Il y a deux parties de rendu: rapport d’auto-évaluation et les sources
  2. Votre dossier de rendu doit contenir les fichiers suivants:
    1. README: rapport d’auto-évaluation
    2. INSTALL: Description de la compilation et l’exécution de votre application
    3. Makefile
    4. CONTRIBUTORS: Noms et prénoms de contributeurs
    5. src/ : les sources (Extensions de fichiers: .c, .h )

Algorithmes et C appliqués aux Systèmes Numériques

Travaux pratiques: Rendus

  1. Votre rendu doit renommer comme groupe_N1_N2, où N1 et N2 sont les noms (e.g., groupe_DUPONT_SMITH.).
  2. Ecrivez README, INSTALL et CONTRIBUTORS en format markdown.
  3. Le contenu de README rapport d’auto-évaluation :
    1. Objectif: Quel est l’objectif de votre projet/TP?
    2. Exercice N (N: [1..7])
      1. Fichiers: Noms de fichiers
      2. Bibliothèques: les bibliothèques standards
      3. Références: les URLs, les numéros de groupes
      4. Difficulté: niveau de difficulté (facile, moyenne, difficile)
      5. Commentaires (optionnels): remarques etc.

Questions

Donnez des exemples de logiciels écrits en C

Algorithmes et C appliqués aux Systèmes Numériques

Exemples

  1. Noyau Linux: https://github.com/torvalds/linux
  2. GCC: https://gcc.gnu.org/viewcvs/gcc/
  3. GIT: https://git.kernel.org/pub/scm/git/git.git/
  4. Apache HTTP Server: https://github.com/apache/httpd
  5. Python: https://github.com/python/cpython

Algorithmes et C appliqués aux Systèmes Numériques

Travaux pratiques et Projet

Algorithmes et C appliqués aux Systèmes Numériques

Objectifs

  1. Créer, compiler et exécuter un projet C
  2. Comprendre la chaine de compilation en utilisant GCC (GNU compilation chain) : prétraitement jusqu’à l’exécution
  3. Travailler avec les bibliothèques standards et les appels de système d’exploitation (fichiers, les sockets réseau etc.)
  4. Comprendre les pointeurs et manipuler les buffers en utilisant les pointeurs
  5. Travailler avec les différents formats de données comme BMP
  6. Utilisation des structures de données et des algorithmes
  7. Créer un simple programme client-serveur pour le transfert de fichiers et messages
  8. Exécuter les applications existantes sur la machine (e.g. GNU plot)
  9. Documenter et tester une application

C Programming Language

C

C est un langage de programmation

Extensions de fichiers

Remarque: Pas de classes (Ce n'est pas un langage de programmation orienté-objet!!!)

Algorithmes et C appliqués aux Systèmes Numériques

C

Bonjour le Monde!!

/* Fichier: bonjour1.c
* affiche 'Bonjour le Monde!!!' à l'écran.
* auteur: John Samuel
* Ceci est un commentaire sur plusieurs lignes
*/

#include <stdio.h> // headers

// Ceci est un commentaire sur une ligne
int main() {
  printf("Bonjour le Monde !!!");
  return 0;
}

Bonjour le Monde!!

/* Fichier: bonjour2.c
* affiche un message à l'écran en utilisant une variable
* auteur: John Samuel
* Ceci est un commentaire sur plusieurs lignes
*/

#include <stdio.h> // headers

int main() {
  int year = 2017; //déclaration d'une variable
  printf("Bonjour le Monde!!! C'est l'annee %d", year);
  return 0;
}

Compilation

La compilation

$ gcc bonjour1.c

L'exécution

$./a.out
Bonjour le Monde!!!

La compilation

La compilation

$ gcc -o bonjour bonjour2.c

L'exécution

$./bonjour
Bonjour le Monde!!! C'est l'annee 2017

Les commentaires

Commentaires sur une ou plusieurs lignes

// Ceci est un commentaire sur une ligne

/* Ceci est un
 * commentaire sur
 * quatre lignes
 */

Les types de base

Types Mots clés Exemples
caractères char 'h', 'a', ...
entiers short, int, long, long long ...,-1,0,1,...
nombres en flottant float, double, long double 3.14, 3.14e23
énumrérations enum ETUDIANT, STAGIAIRE

Les types caractères et entiers

Un octet, deux octets, quatre octets ou huit octets

Les types caractères et entiers

Types Mots-clés
caractères signed char, unsigned char
entiers signed short, signed int, signed long, signed long long, unsigned short, unsigned int, unsigned long, unsigned long long

La taille des types de base n'est pas standardisée!

Declaration des variables

Variables char

char my_char_var1 = 'a';
char my_char_var2 = -125;
unsigned char my_char_var3 = 225;

Remarque: Remarquez-bien l'utilisation de sous-tiret en nommant les variables

Declaration des variables

Variables

char my_char_var = 'a';
unsigned char my_uchar_var = 234;
short my_short_var = -12;
unsigned short my_ushort_var = 65535;
int my_int_var = 12;
unsigned int my_uint_var = 3456;
long my_long_var = -1234553L;
unsigned long my_ulong_var = 234556UL;
long long my_llong_var = 1123345LL;
unsigned long long my_ullong_var = 1234567ULL;
float my_float_var = 3.14;
double my_double_var = 3.14E-12;
long double my_long_double_var = 3.14E-22;

Declaration des variables

Énumrérations

enum status {ETUDIANT, STAGIAIRE};
enum status s = ETUDIANT;
enum status {ETUDIANT=1, STAGIAIRE};
enum boolean {FAUX=0, VRAI};

Remarque: enum: unsigned int

L'intervalle minimum et maximum

limits.h

L'intervalle minimum et maximum de types de base en utilisant limits.h

Mots clés Intervalle
signed char [SCHAR_MIN, SCHAR_MAX]
unsigned char [UCHAR_MIN, UCHAR_MAX]

L'intervalle minimum et maximum

Mots clés Intervalle
(signed) short int [SHRT_MIN, SHRT_MAX]
unsigned short int [0, USHRT_MAX]
(signed) int [INT_MIN, INT_MAX]
unsigned int [0, UINT_MAX]
(signed) long [LONG_MIN, LONG_MAX]
unsigned long [0, ULONG_MAX]
(signed) long long [LLONG_MIN, LLONG_MAX]
unsigned long long [0, ULLONG_MAX]

L'intervalle minimum et maximum

float.h

L'intervalle minimum et maximum de types flottant en utilisant float.h

Mots clés Intervalle
float [FLT_MIN, FLT_MAX]
double [DBL_MIN, DBL_MAX]
long double [LDBL_MIN, LDBL_MAX]

taille (en octets)

sizeof

sizeof (char) //type
sizeof (my_uchar_var) //variable

Afficher à l'écran

Afficher à l'écran

printf("%d", my_int_var);
printf("%f", my_float_var);

printf: Afficher à l'écran

Mots clés Code de conversion
char c
unsigned char hhu
short hd
unsigned short hu
int d, i
unsigned int u
long int ld
unsigned long int lu

printf: Afficher à l'écran

Mots clés Code de conversion
long long int lld
unsigned long long int llu
float f, F
double g, G
long double Lg
string of characters s

printf: Afficher à l'écran

Character Code de conversion
Retour-chariot \n
Tabulation \t

Les notations

Notation binaire

  int valeur = 0b10100100;

Les notations

Notation octale

  int valeur = 0b10100100;
  printf("notation octale: %o\n", valeur);

Les notations

Notation héxadecimale

  int valeur = 0b10100100;
  printf("notation hexadecimale: %x\n", valeur);

Les opérateurs arithmétiques

Opérateur Objectif
+ addition
- soustraction
* multiplication
/ division
% modulus

Les opérateurs arithmétiques

int a = 20, b = 10;
Opérateur Exemple Résultat
+ a + b 30
- a - b 10
* a * b 200
/ a / b 2
% a % b 0

Les opérateurs relationnels

Opérateur Objectif
< inférieur
<= inférieur ou égale
> supérieur
>= supérieur ou égale
== égale
!= différent

Les opérateurs relationnels

int a = 20, b = 10;
Opérateur Exemple Résultat
< a < b 0
<= a <= b 0
> a > b 1
>= a >= b 1
== a == b 0
!= a != b 1

Les opérateurs logiques

int a = 20, b = 0;
Opérateur Objectif Exemple Résultat
! Négation !a 0
&& Et a && b 0
|| Ou a || b 1

Les opérateurs d'incrementation

int a = 20, b = 0;
Opérateur Exemple Résultat
a++ b = a++ a = 21, b = 20
++a b = ++a a = 21, b = 21
a-- b = a-- a = 19, b = 20
--a b = --a a = 19, b = 19

Les opérateurs de manipulation de bits

Bit 1 Bit 2 & | ^ (XOR)
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0

Les opérateurs de manipulation de bits

int a = 0b01000100;
Opérateur Objectif Exemple Résultat
~ Négation ~a 0xffffffbb
& ET a & 0x4 0x4
| OR a | 0x2 0x46
^ XOR a ^ 0x4 0x40
<< décalage à gauche a << 1 0x88
>> décalage à droite a >> 1 0x22

Les opérateurs d'affectation

int a = 20, b = 0;
Opérateur Objectif Exemple
= equal a = b
+= addition a += b
-= substraction a -= b
*= multiplication a *= b
/= division a /= b
%= modulo a %= b

Remarque: a op = b ::- a = a op b

Les opérateurs d'affectation

Opérateur Objectif Exemple
&= ET a &= b
|= OU a |= b
^= XOR a ^= b
<<= décalage à gauche a <<= b
>>= décalage à droite a >>= b

Remarque: a op = b ::- a = a op b

Structures de contrôle: les branchements conditionnels

if

if (condition) {
 ...
}

Structures de contrôle: les branchements conditionnels

if

int a = 20, b = 0;
if (a > b) {
 printf("a est supérieur à b");
}

Structures de contrôle: les branchements conditionnels

if

if (condition1) {
 ...
} else if (condition2) {
 ...
} else {
 ...
}

Remarque 1: Toutes les nombres non nulles sont ont considérées comme vrai ('TRUE')
Remarque 2: else est optionnel

Structures de contrôle: les branchements conditionnels

if

int a = 20, b = 0;
if (a > b) {
 printf("a est supérieur à b");
} else if (a < b) {
 printf("a est inférieur à b");
} else {
 printf("a égale b");
}

Structures de contrôle: les branchements conditionnels (choix)

switch

switch (expression) {
 case valeur1 : statements1
 case valeur2 : statements2
 ...
 default : statementsn
}

Remarque: expression doit être soit: char, short, int ou long

Structures de contrôle: les branchements conditionnels (choix)

switch

int a = 20;
switch (a) {
 case 10 : statement1
  break;
 case 20 : statement2
 case 30 : statement3
  break;
 ...
 default : statementn
}

Remarque: Les deux instructions statement2 et statement3 seront exécutées.

Questions

Que sera-t-il affiché à l'écran suite à l'exécution de ce programme?

if (1) {
  printf("Hi");
} else {
  printf("Bonjour");
}

Structures de contrôle: les boucles

for

for(initialisation;condition;actualisation){
 ...
}

Structures de contrôle: les boucles

for

int a = 0;
for( a = 0; a > 10; a++){
 ...
}

Structures de contrôle: les boucles

for

int a = 0;
for(; a > 10; ){
 ...
}

Remarque: Une ou toutes les instructions d'initialisation, de condition ou d'actualisation peuvent être manquant.

Structures de contrôle: les boucles

for

int a = 0;
for( a = 0; a > 10; a++){
 ...
  a += 2 ;
 ...
}

Structures de contrôle: les boucles

while

while(condition){
 ...
}

Structures de contrôle: les boucles

while

int a = 20;
while(a > 0){
 ...
 a--;
 ...
}

Structures de contrôle: les boucles

while

int a = 0;
while(a < 20){
 ...
 a++;
 ...
}

Structures de contrôle: les boucles

do..while

do{
 ...
} while(condition);

Structures de contrôle: les boucles

do..while

int a = 20;
do{
 ...
  a --;
 ...
} while(a > 0);

Structures de contrôle: les boucles

do..while

int a = 0;
do{
 ...
  a ++;
 ...
} while(a < 20);

Structures de contrôle: les sauts (branchements inconditionnels)

break

do{
 ...
 if (condition 1) {
  ...
  break;
 }
 ...
} while(condition 2);

Structures de contrôle: les sauts (branchements inconditionnels)

continue

do{
 ...
 if (condition 1) {
  ...
  continue;
 }
 ...
} while(condition 2);

Structures de contrôle: les sauts (branchements inconditionnels)

break

while(condition 1){
 ...
 if (condition 2) {
  ...
  break;
 }
 ...
};

Structures de contrôle: les sauts (branchements inconditionnels)

continue

while(condition 1){
 ...
 if (condition 2) {
  ...
  continue;
 }
 ...
};

Structures de contrôle: les sauts (branchements inconditionnels)

break

for(initialisation;condition 1;actualisation){
 ...
 if (condition 2) {
  ...
  break;
 }
 ...
};

Structures de contrôle: les sauts (branchements inconditionnels)

continue

for(initialisation;condition 1;actualisation){
 ...
 if (condition 2) {
  ...
  continue;
 }
 ...
};

Questions

Écrivez un programme qui affiche 0..20 en ordre croissant et décroissant utilisant for, while et do..while.

Questions

Écrivez un boucle infini en utilisant for, while, do..while.

Les tableaux

Tableau

est un ensemble d'éléments homogènes

Tableau de Tableau

Tableaux de tableaux

Tableaux à deux indices

Tableaux de tableaux

Tableaux de tableaux

Tableaux à plusieurs indices

Tableaux de caractères

Déclaration

char name[20];

Remarque: Langage C n'a pas un type nommé 'string'.

Tableaux d'entiers

Déclaration

int iarray[20];
float farray[20];
double darray[20];

Tableaux

Initialisation

int i;
int array[20];
for ( i = 0; i < 20; i++) {
 array[i] = i;
}

Les tableaux

Initialisation

int prices[5] = { 11, 12, 13, 14, 15 };
int rooms[] = { 301, 302, 303 };
char message[] = "Bonjour Le Monde!!";

Remarque: Nous n'avons pas écrit la taille de rooms, message

Les tableaux

Initialisation

int prices[2][2] = {
  {11, 12},
  {13, 14}
};
int rooms[][2] = {
  {201, 202},
  {301, 302}
};
char message[2][11] = {"Bonjour", "Le Monde!!"};

Algorithmes et C appliqués aux Systèmes Numériques

Références

Crédits d'images