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

Récurrences

Spring 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 et fonctions

Ch II.A) Relations

Ch II.B) Fonctions

Ch III) Récurrence

Ch IV) Langages

Ch IV.A) Langages

Ch IV.B) Expressions régulières

Ch IV.C) Automates

Ch IV) Machines de Turing

  • TD 3
  • TD 4
  • TD 5

    Ch IV) Récurences

    Pour faire une démonstration d'une propriété P(n) par récurrence il faut
    1. Valider pour une ou deux valeurs initiales, en général p(0), parfois P(1), parfois P(0) et P(1).
    2. Vérifier l'héritage, i.e. vérifier que P(n)=>p(n+1)

    L‘informaticien commencera souvent par valider la propriété par un petit programme.

    Voici un exemple. La suite U est donnée par :

    U(0) == 1
  U(n+1) == U(n) + 2*n + 3
    On veut vérifier que U(n)=(n+1)^2. 
    #include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef struct vect {
  int nb;
  int * v;
} vect_t;

void creevec (vect_t * v, int nbelements) {

  v->nb = nbelements;
  v->v = malloc(nbelements * sizeof(int));
  assert(v->v);
}
void remplitsuite (vect_t * v) {
  int n, i;

  n = v->nb;
  v->v[0] = 1;
  for (i = 1; i < n; i++) {
    v->v[i] =  v->v[i - 1] + 3 +((i-1)<<1);
  }
  return;
}
void voirsuite  (vect_t v) {
  int n, i;
  n = v.nb;
  printf("La suite :\n");
  for (i = 0; i < n; i++) {
    printf("%2d %5d\n", i, v.v[i]);
  }
  return;
}
void comparsuite(vect_t v) {
  int i, nb, carre, wrong;
  nb = v.nb;
  carre = 0;
  wrong = 0;
  for (i = 0; i < nb; i++) {
    carre += 1 + (i << 1);
    if (carre != v.v[i]) {
      printf("%d != %d\n", carre, v.v[i]);
      wrong ++;
    }
  }
  if (! wrong)
    printf("\nidentiques\n");
}
int main (int argc, char ** argv) {
  vect_t w;
  int nb;

  if (argc == 2) {
    nb = atoi(argv[1]);
  }
  else
    nb = 10;
  creevec(&w, nb);
  remplitsuite(&w);
  voirsuite (w);
  comparsuite(w);
}

    La propriété étant vraisemblablement juste il faut maintenant la prouver.