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

    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}
    Dernière mise à jour le 19/2/2025 12h00

    Rajout de TD.