contenu_cours_1.md

Algorithmes et structures de données 2020-21

Contenu du cours 1 du 16.09.2020

---

Présentation personnelle

Paul Albuquerque, resp. de filière
bureau B410
022 546 2554
paul.albuquerque@hesge.ch

Organisation du module (2 cours, 50 % chacun)

• Algorithmes et structures de données
  • 1er semestre
    • Bases de la programmation en C jusqu'à Noël
    • Algorithmique jusque fin janvier
  • 2ème semestre
    • Algorithmique

Au moins 2 évaluations par semestre

• Programmation séquentielle en langage C
  • 1er & 2ème semestre :travaux pratiques en langage C
    • Chaque semestre des travaux pratiques sont répartis dans deux gros projets d'env. 7 semaines

Qu'est-ce qu'un algorithme ?

Informellement, c'est une recette ou une marche à suivre.

Plus formellement:

Définition
Un algorithme est une suite finie et non ambiguë d'opérations
ou d'instructions permettant de résoudre un problème.

Le mot algorithme vient du nom latinisé du mathématicien perse Al-Khawarizmi

Les algorithmes des grecs : Euclide, Erastosthène

Le père de l'algorithmique : Muhammad Ibn Mūsā al-Khuwārizmī

Résolution d'un problème

• Décomposition en sous-problèmes
• Résolution des sous-problèmes
• Assemblage des résultats

Notions de base d'algorithmique séquentielle

• Définition d'une variable (nom, type, valeur, adresse)
• Séquences d'instructions
• Boucles et tests (for, while, do...while, if...else)

Algorithme de vérification qu'un nombre est 1^er

• Comment demander le nombre
• Forme de l'algorithme (boucle et tests)
• Condition d'arrêt de la boucle

Qu'est qu'un programme C ?

• Importations de librairies (paquetages) :

     #include <stdlio.h>
     #include <stdlib.h>

• Entête du programme : int main()
• Déclaration de variables : int x = 5;
• Bloc d'instructions :

     {
         int x = 5;
         printf("x=%d\n",x);

     }

Les types de base : les entiers (int, unsigned int)

• Numérotation binaire en particulier sur 32 bits

• Nombres négatifs => complément à 2

  numération sur 3 bits :

  binaire	entier≥0	binaire	entier<0
  000	0	111	-1
  001	1	110	-2
  010	2	101	-3
  011	3	100	-4

• Nombres négatifs => complément à 1 par simple inversion des bits

  **problème **: 0 possède alors deux représentations !

• Opérations particulières

  • Division entière : 5 / 2 = 2 , 10 / 3 = 3 , 18 / 5 = 3
  • Reste de la division entière (modulo) : 5 % 2 = 1 , 10 % 3 = 1 , 18 % 5 = 3

• Constantes de la librairie <limits.h>: INT_MAX, INT_MIN

Les types de base : les réels (float, double)

• Float: écriture, opérations, exemples complets d'exponentiation
  pow(A,B) où A, B sont des double => le résultat est un double !
  Attention ! Le calcul effectué par pow utilise un logarithmes et une exponentielle.

Sur 32 bits : 1 bit de signe, 8 bits pour l'exposant et 23 bits pour la mantisse.

• Exemple : coder 19,625 en binaire

19 : 10011 = 2⁴ + 2¹ + 2⁰; 0,625 : 0,101 = 2^-1 + 2^-3

19,625 : 10011,101 = 0,10011101 * 2⁵

Le signe du nombre est stocké sur dans le 1^er bit (0 positif / 1 négatif).

L'exposant est stocké sur 8 positions => 256 valeurs => -128..127.

Donc 5 = 00000101

La mantisse de 23 bits stockée est 00111010000000000000000
(le 1^er 1 est omis car obligatoire)

19,625 stocké en binaire : 0 00000101 00111010000000000000000

• Questions : quelles sont les valeurs les plus petite, grande, petite positive (>0)?

Les booléens bool

• Librairie: <stdbool.h>
  Valeurs possibles: true, false
  Conversion possible en entier

Exemples:

        bool x = true;  // booléen vrai
        bool x = false; // booléen faux
        bool x = 17;    // 17 converti en booléen vrai
        bool x = -5;    // -5 converti en booléen vrai
        bool x = 0;     // 0 converti en booléen faux
        int y = false;  // booléen faux converti en 0
        int y = true;   // booléen vrai converti en 1

• Vérification => table de vérité
  • not (A and B) = (not A) or (not B) : !(A && B) == (!A)|| (!B)
  • not (A or B) = (not A) and (not B) : ! --|| B) == (!A) && (!B)
• Opérateurs logiques : *==, !=, &&, ||, !, <, >, <=, >=
• Comparaisons bit à bit : & (et), | (ou), ^ (xor), ! (not)
• Comparaisons bit à bit avec assignation : &=, |=, ^=

Structures de boucle

• Syntaxe

      for (initialisation;condition;increment) {
          instructions;
      }

      while (condition) {
          instructions;
      }

      do {
          instructions;
      } while (condition);

• Instructions : break, continue

Les caractères (type prédéfini) char

• On considère les caractères sont des valeurs encodées sur 1 octet (code ASCII étendu).
  Il y a donc 256 valeurs possibles. La conversion entre entier et caractère est effective.
  Par exemple, le caractère 'A' correspond à 65 et 'a' à 96.

      char ch = 'a'; // Caractère 'a'
      printf("La variable ch est %c\n",ch); // affiche 'a'
      char x = 96;
      printf("La variable x est %c\n",x);   // affiche aussi 'a'
      int v = 'a';
      printf("La variable v est %d\n",v);   // affiche 96

Structures de test

• Syntaxe

      if (condition) {
          instructions;
      } else if (condition) {
          instructions;
      } else {
          instructions;
      }

Exemple de boucles (for, while, do ... while)

• La factorielle