Jean-Jacques BOURDIN

Université Paris 8
Dépt. Programmation et Informatique Fondamentale,
2, rue de la Liberté
93526 Saint-Denis Cedex
FRANCE

Informatique Fondamentale
Computer Science 001

Winter 2025

Overview

Ch I) Logique et ensembles

    I.A) Algèbre booléenne

    I.A.1) Binaire

    I.A.2) Expressions booléennes

    I.A.3) Propriétés

    I.A.4) Premier TD

    I.B) Ensembles

Ch II) Relations

Ch III) Fonctions

Ch IV) Récurence

Ch V) Expressions régulières

  • TD 3
  • TD 4
  • TD 5

    Overview


    Contrôle continu, TD notés, réponses aux questions...

    Partiel 1

    Partiel 2

    Note finale, 20% CC 30% P1, 50%P2
    >

    Ch I) Logique et ensembles

        I.A) Algèbre booléenne

        I.A.1) Binaire

    De binaire à décimal et le contraire.

    Utilisons ^ pour signifier puissance :

    Dans une base x, le nombre (d_n d_(n-1) ... d_3 d_2 d_1 d_0) (où les d_ sont les chiffres) vaut :

    d_n * x^n + d_(n-1) * x^(n-1) + ... + d_3 * x^3 + d_3 * x^3 + d_2 * x^2 + d_1 * x^1 + d_0 * x^0 + 0 * 2^2

    Exemple 1001 en base deux vaut 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0 == 9

    La soustraction binaire se déroule en soustrayant les chiffres un à un et en remarquant que 0 moins 1 impose de trouver 1 avec une retenue à sousraire au prochain chiffre. 10111 - 1100 == 1011, on vérifie en décimal : 23 - 12 = 11

        I.A.2) Expressions booléennes

    Les opérateurs sont ET (&, *, ^), OU (|, +, v) et NON (~ ).

    Tables de vérité

    Premier exemple, a ET NON b (a*~b) ;

      a  b  ~b a*~b
  v  v   f    f
  v  f   v    v
  f  v   f    f     
  f  f   v    f

    L‘implication peut se noter =>   elle a la même table de vérité que b OU NON a (~a + b) ;

      a  b  ~a ~a+b  a=>b
  v  v   f    v     v
  v  f   f    f     v
  f  v   v    v     v     
  f  f   v    v     v

    L'équivalence est notée 

     a <=> b
    , elle signifie qu‘on a 
     a <= b
    et 
     b => a
    .

      a  b a=>b b=>a a<=>b
  v  v    v    v     v
  v  f    f    v     f
  f  v    v    f     f     
  f  f    v    v     v

        I.A.3) Propriétés

    Voir le premier TD.

        I.A.4) Premier TD

        I.B) Ensembles

        I.B.1) En extension

    Dans ce cas on donne tous les éléments : 
    A = { veau, vache, cochon, couvée }
    B = { 0, 1, 2, 3, 4, 5, 6 }
    Le nombre d‘éléments s‘écrit 

    |A| == 4
    |B| == 7

        I.B.2) En compréhension

    On donne une propriété qui caractérise les éléments. 
    C = {x/ x∈ A ^ P(x)}

    Exemple
    D = {x/ x∈ A ^ x est pair}

    • Ch III) Fonctions

    1. Rappels sur les suites numériques

      2. Nous avons vu des suites numériques où Ui est une valeur réelle et donc Ui = f(i) où f est une fonction de R vers R.

      Prenons U(i) = i^2 - 5.i + 6


      Calculons ses valeurs pour les premiers entiers.
      i	  O  1  2  3  4  5  6  7
Ui	  6  2  0  0  2  6 12 20
diff        -4 -2  0  2  4  6  8

      La valeur de la différence peut être calculée :

        diff(i) = U(i+1) - U(i) = (i+1)^2 - 5x(i+1) + 6 - i^2 + 5xi - 6
  diff(i) = i^2 + 2xi + 1 - 5xi -5 + 6 - i^2 + 5xi - 6 = 2 i - 4

      Au lieu de calculer ui directement, si on a à calculer toutes les valeurs on peut le faire en ajoutant diff(i) à chaque itération.

      Cette différence est la "croissance" de U ou encore sa "vitesse", même si on utilise ce dernier mot surtout dans R.

      On peut aussi calculer diff(i) en fonction de diff(i-1) :


      l'écart est de 2 à chaque itération.

      Une itération sera donc :

          u = u + diff;
    diff = diff + 2;

    2. Des suites aux fonctions

      3. Nous prenons maintenant la fonction f qui a la même formule mais est définie dans ℝ. (et pas dans ℕ)  : 
      f(x) = x^2 - 5 x + 6

      Pour les valeurs entières on a f(i) == Ui

      La différence entre f(i) et f(i+1) devrait plutôt être calculée entre f(x) et f(x + ε) avec ε très, très très petit.

      Plus ε est petit et plus on va se rapprocher de 0, ce qui est sans intérêt. Par contre si on divise cette différence par ε on obtient, à la limite, une valeur tout à fait intéressante, la vitesse en un point.

      	  f'(x) = lim   (f(x + ε) - f(x))/ ε
	         ε → 0

      f' est nommée la dérivée de f.

      f'', la dérivée de la dérivée, est nommée la dérivée seconde de f. Elle correspond à l'accélération du mouvment.

    3. Exemple : la formule 1 et le mur

      4. Soit une formule 1 qui roule, en ligne droite, à 50 m/s. Logiquement elle parcourt 50 mètres à chaque seconde.

      Mais si le pilote accélère sa vitesse change. Nous considérerons une accélération de 2m/s/s, c'est-à-dire que, à chaque seconde, la vitesse augmente de 2 m/s.

      Quelle est sa vitesse à la seconde 0, à la seconde 1, à la seconde 2 ?

      Quelle distance aura été parcourue à chacun de ces instants ?

      temps   0     1     2     3     4     5    6    7    8    9    10   11  
acc     2     2     2     2     2     2    2    2    2    2     2    2
speed  50    52    54    56    58    60   62   64   66   68    70   72
dist    0    50   102   156   212   270  330  392  456  522   590  660
      À cet instant le pilote voit qu'il y a un mur à 340m de lui. Que fait-il ? Vérifiez ce que ça donne comme valeurs. Vous pouvez (devriez) écrire un programme qui fait ces calculs à votre place.

      Voici une structure pour faire celà : 
      typedef struct instant {
  int tps;
  float acc;
  float speed;
  float dist;
} instant_t;

typedef struct vect {
  int nbval;
  instant_t * vec;
} vect_t;
      Et une fonction pour afficher un tel vecteur. 
      void affichevec (vect_t v) {
  int i;
  printf("Nouveau cas \n");
  for (i = 0; i < v.nbval; i++) {
    printf("en %3d acc %5.2f ", i, v.vec[i].acc);
    printf("vit  %5.2f distance  %6.2f \n",v.vec[i].speed, v.vec[i].dist);
  }
  printf("\n");
}
      Qui donne ; 
      en   0 acc  2.00 vit  50.00 distance    0.00 
en   1 acc  2.00 vit  52.00 distance   50.00 
en   2 acc  2.00 vit  54.00 distance  102.00 
en   3 acc  2.00 vit  56.00 distance  156.00 
en   4 acc  2.00 vit  58.00 distance  212.00 
en   5 acc  2.00 vit  60.00 distance  270.00 
en   6 acc  2.00 vit  62.00 distance  330.00 
en   7 acc  2.00 vit  64.00 distance  392.00 
en   8 acc  2.00 vit  66.00 distance  456.00 
en   9 acc  2.00 vit  68.00 distance  522.00 
en  10 acc  2.00 vit  70.00 distance  590.00 
en  11 acc  2.00 vit  72.00 distance  660.00
    Dernière mise à jour le 13/3/2025 12h00

    Rajout d'un plan plus détaillé.

    Rajout de la fonction d'affichage et des structures