Corrigé du sujet d’informatique du CAPES 2019

jeudi 25 avril 2019
par  Alain BUSSER , Sébastien HOARAU

Le sujet est disponible ici

Le premier problème portait sur la numération en base 3 équilibrée qui est une sorte de binaire signé chiffre par chiffre, et le second problème portait sur des problèmes de théorie de graphe qui apparaissent lorsqu’on veut allouer des registres à des variables.

Problème 1 : La base 3 équilibrée

PARTIE I --- Généralités

Question 1

  1. Voici la traduction décimale des 3 nombres en base 3 équilibrée :
    • 1(-1)0(-1)_e = 1 * 33 + -1 * 32 + 0 * 3 - 1 = 27-9-1 = 17
    • 1111_e = 1 * 33 + 1 * 32 + 1 * 3 + 1 = 27+9+3+1 = 40
    • 1(-1)(-1)(-1)(-1)_e = 34 - 33 - 32 - 3 - 1 = 81-27-9-3-1 = 41
  2. L’écriture en base 3_e des entiers de 1 à 9 :
base 10 base 3_e Explications
1 1 = 1
2 1(-1) = 3 - 1
3 10 = 3
4 11 = 3 + 1
5 1(-1)(-1) = 9 - 3 - 1
6 1(-1)0 = 9 - 3
7 1(-1)1 = 9 - 3 + 1
8 10(-1) = 9 - 1
9 100 = 9

Question 2

  • Ak = 1 1...1_e = 3k + 3k-1 + ... + 3 + 1 = (3k+1-1)/2 est numérotée 3462 sur OEIS
  • Bk = 1(-1)...(-1)_e = 3k - 3k-1 - ... - 3 - 1 = 3k-(3k-1)/2=(3k+1)/2 est la suite 7051 sur OEIS.

Question 3

On modélise par la liste [a_p-1, ... a_1, a_0] le nombre (a_0a_1...a_p-1)_e. Ci-dessous une définition de la fonction valeur(L) qui étant donnée une liste L représentant l’écriture en base 3_e d’un nombre, nous donne sa valeur décimale.

  1. def valeur(L):
  2.     return sum(a * 3 ** index for index, a in enumerate(L))

Explication du code : ici on utilise une fonction génératrice associée à la fonction prédéfinie sum pour avoir une écriture proche de la formule mathématique : la somme des puissances de 3 fois le coefficient pour tous les coefficients de la liste.

PARTIE II --- Existence et unicité

Question 4

(4a) On suppose qu’un entier n est tel que : n = 3q + r et q s’écrit (a0...ap-1)_e. Dès lors n s’écrit :

  • (a0...ap-10)_e si r = 0 ; multiplier q par 3 c’est décaler son écriture vers la gauche et on rajoute 0
  • (a0...ap-11)_e si r = 1 ; même chose mais on rajoute 1.

(4b) On suppose que q > 0 et q + 1 s’écrit (b0...bp-1)_e. Dès lors si r = 2, n = 3(q + 1) - 1 et donc s’écrit (b0...bp-1(-1))_e

(4c) On propose une récurrence sur q :

  • Initialisation : On a vu au début du sujet que les premiers entiers non nuls possèdent une écriture en base 3 équilibrée.
  • Hérédité : On vient de voir comment passer de l’écriture de n à celle de 3n ou 3n+1 (ce qui prouve que ces entiers ont une écriture), et comment on peut passer de l’écriture de 3n+3 à celle de 3n+2. Mais on peut passer de l’écriture de n+1 à celle de 3n+3 ce qui prouve que 3n+3 et 3n+2 ont une écriture.

Question 5

(5a) Définition récursive de incrementeR(L)

  1. def incrementeR(L):
  2.     if len(L) == 0:
  3.         return [1]
  4.     elif L[0] == 0:
  5.         return [1] + L[1:]
  6.     elif L[0] == -1:
  7.         return [0] + L[1:]
  8.     else:
  9.         return [-1] + incrementeR(L[1:])
  • Explication de la ligne 9 : On est dans le cas où n = n’ + 1 (L[0] vaut 1) représenté par L. Dès lors [0]+L[1 :] représente n’ et donc L[1 :] seul est un décalage à gauche de n’ et représente n’/3. L’appel récursif représente alors n’/3 + 1 et en redécalant à droite on a 3*(n’/3 + 1) soit n’ + 3 et en ajoutant -1 on obtient n’ + 2 soit n + 1.
  • Les lignes 1 et 2 sont là pour le cas terminal : à chaque appel récursif, la longueur de L diminue strictement de 1. En partant d’une liste non vide on finira par tomber sur le cas len(L) == 0.

(5b) Version itérative :

  1. def incremente(L):
  2.     p = len(L)
  3.     M = []
  4.     k = 0
  5.     while k < p and L[k] == 1:
  6.         M.append(-1)
  7.         k += 1
  8.     if k == p:
  9.         M.append(-1)
  10.     elif L[k] == 0:
  11.         M.append(1)
  12.         M = M + L[k+1:]
  13.     elif L[k] == -1:
  14.         M.append(0)
  15.         M = M + L[k+1:]
  16.     return M

Question 6

(6a) Si a0, ... , ap-1 sont les chiffres de C, alors C est la somme des ak3k qui sont tous divisibles par 3 sauf ap-1. C et ap-1 ont donc le même reste dans la division euclidienne par 3. Le reste de C est donc égal à ap-1 si celui-ci est positif et à ap-1+3=2 sinon.

(6b) Si a0, ... , ap-1 et b0, ... , bp-1 désignent les écritures de C en base 3 équilibrée, on veut prouver que qk=bk pour toute valeur de k. On peut le faire par récurrence décroissante sur k : D’après la question précédente, on a nécessairement ap-1=bp-1, et on continue la récurrence après divisions successives par 3.

Question 7

  1. def base3e(n):
  2.     chiffres = [0,1,-1]
  3.     ajout = [0, 0, 1]
  4.     L = []
  5.     while n > 0:
  6.         reste = n % 3
  7.         L.append(chiffres[reste])
  8.         n = n // 3 + ajout[reste]
  9.     return L

PARTIE III --- Chemins de Delannoy

Question 8

(8a) Chemin de 2019 : 2019 = (10-110-110)_e

HTML - 1.6 ko

(en cliquant sur le chemin de Delannoy ci-dessus, on ouvre une page interactive permettant de voir les chemins de Delannoy des nombres allant de 1 à 800)

(8b) Définir une fonction arrivee(n) qui donne les coordonnées du point d’arrivée du chemin de Delannoy associé à l’entier n.

  1. def arrivee(n):
  2.    
  3.     def add(a, b):
  4.         return a[0]+b[0], a[1]+b[1]
  5.    
  6.     steps = [(1,1), (1,0), (0,1)]
  7.     ajout = [0, 0, 1]
  8.     pt_arr = (0, 0)
  9.     while n > 1: # ici 1 pour ne pas prendre en compte le premier chiffre 1
  10.         reste = n % 3
  11.         pt_arr = add(pt_arr, steps[reste])
  12.         n = n // 3 + ajout[reste]
  13.     return pt_arr

Question 9

On considère N(a, b) = { n | arrivee(n) == (a, b) }

(9a) Le min de N(a, a) consiste à avoir le chemin le plus court jusqu’à A(a, a). Donc (10...0)_e Avec a zéros. Ce qui nous donne l’entier 3a. Pour le maximum on va maximiser les puissances de 3... donc (11...1-1...-1)_e (il y a a digits 1 et a digits -1) pour un entier égal à 32a + 32a-1 + ... + 3a - 3a-1 - ... - 3 - 1 =(32a+1-2×3a+1)/2.

(9b) Pour le max N(a, b) avec a < b, ça ne change pas : (11...1-1...-1)_e avec a digits 1 et b digits -1. Il s’agit du nombre (3a+b+1-2×3b+1)/2.

Pour le minimum : min N(a, b) = (10...0-1...-1)_e avec a digits 0 et b - a digits -1. Il s’agit du nombre (2×3a+b-3b-a+1+1)/2.


Problème 2 : Compilation et algorithmes

A0 - Les graphes des modules

La partie A porte sur l’ordre dans lequel on compile différents modules : C’est un ordre topologique sur un graphe orienté. Un tel graphe peut être dessiné à l’aide du logiciel adéquat qui a servi à faire les figures ci-dessous.

Voici le graphe donné au début de la partie A de l’énoncé :

 - 6.1 ko

Dessiné, il ressemble à ceci :

On constate qu’il ne possède qu’un sommet sans successeur (« arrivée ») et un seul sommet sans prédécesseur (« départ »). Cette dernière caractéristique permet de jouer à un jeu de Nim sur ce graphe, en plaçant un pion (noir ci-dessous) sur le sommet 5 (le départ) :

Les joueurs déplacent le pion selon une arête, chacun son tour. Celui qui mène le pion au sommet 1 (l’arrivée) gagne le jeu. On voit qu’il y a une stratégie gagnante pour celui qui joue en premier, consistant à mettre le pion sur le sommet 2. Ceci se voit par la coloration du graphe :

PARTIE A --- Ordre topologique sur un graphe

Le graphe de l’énoncé a été obtenu à partir du précédent en enlevant le sommet M2 :

Il est codé ainsi :

  1. N = 9
  2. App = [True, True, False, True, True, True, True, True, True]
  3. P = 8
  4. Succ = [[1], [], [], [6], [0], [3], [0], [4], [0, 1, 7]];
  5. G = [App, Succ, P]

Question 10

  1. def mem(i, g):
  2.     """renvoie True si le sommet numéro i est dans le graphe représenté par g"""
  3.     return g[0][i]

Question 11

  1. def pred(i, g):
  2.     """renvoie la liste des sommets j tels que j->i est présent dans le graphe g."""
  3.     return [j for j in range(N) if mem(j, g) and i in g[1][j]]

Par exemple :

>>> pred(0, G)
[4, 6, 8]

Question 12

  1. def sansSuccesseur(g):
  2.     """renvoie un numéro i tel que Mi n'a pas de successeur
  3.    ou -1 si un tel sommet n'existe pas dans le graphe g"""
  4.     for i in range(N):
  5.         if mem(i, g) and g[1][i] == []:
  6.             return i
  7.     return -1

Par exemple :

>>> sansSuccesseur(G)
1

Question 13

  1. import copy
  2. def suppr(i, g):
  3.     """crée et renvoie une copie de g privé du sommet i et des arcs qui s'y réfèrent"""
  4.     h = copy.deepcopy(g)
  5.     h[2] -= 1
  6.     h[0][i] = False
  7.     h[1][i] = []
  8.     for j in range(N):
  9.         if mem(j, h) and i in h[1][j]:
  10.             h[1][j].remove(i)
  11.     return h

Question 14

On considère un graphe G de p sommets, p ≤ N.

(14a)

Promenade : s0s1...sN... on a donc N+1 sommets. Supposons que les sommets soient tous différents alors p = N+1 ce qui contredit l’hypothèse.

(14b)

Encore une fois par l’absurde : si on suppose que le graphe ne possède pas de cycle, alors à chaque pas de si vers sj on est sur un sommet non déjà visité. Mais alors cela signifie qu’à la fin de la promenade on a N+1 sommets distincts ce qui contredit (14a).

(14c)

D’après (14b), soit si0,si1...sik=si0 le cycle. Supposons qu’il existe un ordre topologique N. Alors par définition à la fois de l’ordre et de la promenade, on a : N(si0) < N(si1) < ... < N(sik) = N(si0) d’où N(si0) est strictement inférieur à lui-même ce qui n’est pas possible. Il n’existe donc pas d’ordre topologique sur ce graphe.

Question 15

Soit s1 et s2 deux sommets de G. Si s1 et s2 ne sont pas s alors si s1 est successeur de s2 on aura NH(s2) < NH(s1) et donc N(s2) < N(s1) et raisonnement analogue s’il s’agit de s2 successeur de s1. Donc N vérifie bien la condition d’ordre topologique.

Si maintenant s2 est le noeud s, alors comme s n’a pas de successeur, s2 ne peut pas être le successeur de s. s peut être le successeur de s2. Dès lors, N(s2) = NH(s2) ≤ p - 2 < p - 1 = N(s). Là encore la contrainte est vérifiée. N est donc bien un ordre topologique sur G.

Question 16

(16a) On en déduit un algorithme pour trouver un ordre topologique (quand il existe)

  1. def ordreTopologique(g):
  2.     """renvoie une liste L telle que L[i] vaut N(i)
  3.    si N existe et None sinon"""
  4.     n = len(g[0])
  5.     L = [-1] * n
  6.    
  7.     def parcoursReussi(g):
  8.         p = g[2]
  9.         if p != 0:
  10.             s = sansSuccesseur(g)
  11.             if s == -1:
  12.                 return False
  13.             else:
  14.                 L[s] = p
  15.                 return parcoursReussi(suppr(s, g))
  16.         else:
  17.             return True
  18.    
  19.     b = parcoursReussi(g)
  20.     if b:
  21.         return L
  22.     else:
  23.         return None

(16b) La seule fonction susceptible de boucler est parcoursReussi qui est récursive. Mais si p vaut 0 ou si on ne trouve pas de sommet sans successeur, ça termine. L’appel récursif se fait avec un graphe qui possède un de sommet de moins. On tombera donc sur un des deux cas :

  • il n’y a plus de sommet : L’algorithme termine alors
  • chaque sommet restant a au moins un successeur : Là encore l’algorithme termine.

Par exemple :

>>> print(ordreTopologique(G))
[7, 8, -1, 4, 6, 3, 5, 2, 1]

B0 - Python et les registres

La partie B porte sur l’allocation de 4 registres aux variables a, b, c et d utilisées dans cette fonction Python :

def capes():
    d = 1
    b = 2*d
    a = 3
    d = a*b
    print(d)
    c = 2*a-b
    print(a)
    d = c+b
    b = 2*a
    print(c,d)

Pour avoir les affichages du programme il suffit de lancer la fonction en entrant

capes()

Mais pour savoir comment Python fait réellement l’allocation de registres, on pense naturellement à cet algorithme :

  1. Compiler la fonction capes() ci-dessus ;
  2. désassembler le bytecode ainsi obtenu ;
  3. regarder le résultat du désassemblage.

Pour cela on importe le module dis (comme « disassemble ») qui possède une fonction dis s’appliquant à toute fonction Python, comme par exemple la fonction capes() ci-dessus. En précédant la définition de la fonction d’un

from dis import *

et en la suivant d’un

dis(capes)

on obtient ceci :

4           0 LOAD_CONST               1 (1)
             3 STORE_FAST               0 (d)

 5           6 LOAD_CONST               2 (2)
             9 LOAD_FAST                0 (d)
            12 BINARY_MULTIPLY
            13 STORE_FAST               1 (b)

 6          16 LOAD_CONST               3 (3)
            19 STORE_FAST               2 (a)

 7          22 LOAD_FAST                2 (a)
            25 LOAD_FAST                1 (b)
            28 BINARY_MULTIPLY
            29 STORE_FAST               0 (d)

 8          32 LOAD_GLOBAL              0 (print)
            35 LOAD_FAST                0 (d)
            38 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            41 POP_TOP

 9          42 LOAD_CONST               2 (2)
            45 LOAD_FAST                2 (a)
            48 BINARY_MULTIPLY
            49 LOAD_FAST                1 (b)
            52 BINARY_SUBTRACT
            53 STORE_FAST               3 (c)

10          56 LOAD_GLOBAL              0 (print)
            59 LOAD_FAST                2 (a)
            62 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
            65 POP_TOP

11          66 LOAD_FAST                3 (c)
            69 LOAD_FAST                1 (b)
            72 BINARY_ADD
            73 STORE_FAST               0 (d)

12          76 LOAD_CONST               2 (2)
            79 LOAD_FAST                2 (a)
            82 BINARY_MULTIPLY
            83 STORE_FAST               1 (b)

13          86 LOAD_GLOBAL              0 (print)
            89 LOAD_FAST                3 (c)
            92 LOAD_FAST                0 (d)
            95 CALL_FUNCTION            2 (2 positional, 0 keyword pair)
            98 POP_TOP
            99 LOAD_CONST               0 (None)
           102 RETURN_VALUE

Ce qui permet de suivre la chronologie de l’exécution du programme :

  • t=0 : La constante 1 est chargée par la machine Python
  • t=3 : La constante est stockée dans la variable d (la ligne 1 du programme est effectuée)
  • t=6 : La constante 2 est chargée
  • t=9 : Le contenu de d est chargé
  • t=12 : La multiplication 2*d est effectuée
  • t=13 : Le résultat est stocké dans b (la ligne 2 est alors effectuée)
  • t=16 à 21 : 3 est mis dans a (ligne 3 du programme Python)
  • t=22 à 31 : a*b est mis dans d
  • t=32 : C’est une fonction (globale) et non une constante qui est chargée : print
  • t=35 : d est chargé aussi
  • t=36 : La fonction print est appelée avec l’argument (contenu de) d
  • t=39 : puis dépilée (ce qui se passe à chaque return ; en effet la machine Python est basée sur une pile)
  • t=42 à 55 : 2*a-b est mis dans c (on constate que la suite des opérations est menée sur la pile avec la notation polonaise inversée 2 a * b - dans l’ordre d’exécution)
  • t=56 à 65 : L’affichage de a est effectué
  • t=66 à 75 : c+b est mis dans d
  • t=76 à 85 : 2*a est mis dans b
  • t=86 : La fonction print est empilée
  • t=89 : La variable c est chargée
  • t=92 : La variable d est chargée
  • t=95 : La fonction print est appelée (mais cette fois-ci avec deux arguments)
  • t=98 : La fonction est dépilée
  • t=99 : La constante 0 (signifiant qu’il n’y a pas eu d’erreur) est chargée
  • t=102 : La constante 0 est renvoyée par la fonction capes()

Comme on le voit, les registres du processeur et la manière dont les variables a, b, c et d leur sont allouées, ne sont pas affichés. C’est parce que la machine virtuelle Python n’est basée que sur cette pile. Ce sont les longueurs successives de la pile qui sont affichées dans l’avant-dernière colonne.

On note que c’est la deuxième année de suite que le sujet de Capes porte sur la notion de graphe d’intervalles.

PARTIE B --- Allocation de registres

Question 17

ligne a b c d
0 M M M M
1 M M M V
2 M V M M
3 V V M M
4 V V M V
5 V V M M
6 V V V M
7 V V V M
8 V M V V
9 M M V V

Question 18

Si par exemple la variable a est vivante en ligne 0, cela signifie qu’elle est utilisée sans avoir été initialisée. Dans ce cas le programme ne s’exécute pas, il s’interrompt avec ce message :

Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
NameError: name 'a' is not defined

Il ne serait donc pas exécutable.

Question 19

  1. """ PROG_EX:"""
  2. d=1
  3. b=2∗d
  4. a=3
  5. d=a∗b
  6. print(d)
  7. c=2∗a−b
  8. print(a)
  9. d=c+b
  10. b=2∗a
  11. print(c,d)
  12. PROG_EX = [(3,[]), (1,[3]), (0,[]), (3,[0,1]), (None ,[3]), (2,[0,1]), (None ,[0]), (3,[1,2]), (1,[0]), (None ,[2,3])]
  1. def determineVie(prog, p):
  2.     """retourne le tableau de vie d'un programme prog de p variables"""
  3.     nb_instructions = len(prog)
  4.     vie = [[False] * p for _ in range(nb_instructions+1)]
  5.     for index in range(nb_instructions - 1, -1, -1):
  6.         left, variables = prog[index]
  7.         for v in range(p):
  8.             if v in variables:
  9.                 vie[index][v] = True
  10.             else:
  11.                 vie[index][v] = vie[index+1][v]
  12.         if left is not None:
  13.             vie[index][left] = left in variables
  14.     return vie[:-1]

Pas de difficulté particulière sur ce code : on parcourt les lignes de la table en remontant et en mettant à jour la vie d’une variable comme expliqué. Petite astuce la liste de vie comporte une ligne de plus pour ne pas avoir à traiter comme cas particulier la dernière ligne, d’où le vie[:-1] à la fin.

Par exemple :

>>> VIE_EX = determineVie(PROG_EX, 4)
>>> for line in VIE_EX:
          print(line)
[False, False, False, False]
[False, False, False, True]
[False, True, False, False]
[True, True, False, False]
[True, True, False, True]
[True, True, False, False]
[True, True, True, False]
[True, True, True, False]
[True, False, True, True]
[False, False, True, True]

Question 20

  1. def periodesVie(vie, v):
  2.     n = len(vie)
  3.     periodes = []
  4.     enCours = False
  5.     i = n - 1
  6.     while i >= 0:
  7.         if vie[i][v]:
  8.             if not enCours:
  9.                 periode = (i,)
  10.                 enCours = True
  11.         else:
  12.             if enCours:
  13.                 periode = (i,) + periode
  14.                 enCours = False
  15.                 periodes.append(periode)
  16.         i -= 1
  17.     return periodes

Par exemple :

>>> periodesVie(VIE_EX, 3)
[(7, 9), (3, 4), (0, 1)]

PARTIE C --- Graphe de coexistence

Dans cette partie, c’est le logiciel des graphes non orientés qui sera utilisé. Il a servi notamment à dessiner les graphes ci-dessous.

On a vu dans la question 17 que toute variable parmi a, b, c et d est utilisée en même temps que toute autre variable parmi elles. Si on représente par un graphe la relation « est utilisée en même temps que », le graphe correspondant, pour ces 4 variables, est le graphe K_4 complet à 4 sommets (0 pour a, 1 pour b etc) :

Si on représente chaque registre par une couleur, il faut donc 4 couleurs pour colorier ce graphe. Ce qui signifie qu’au moins 4 registres seront nécessaires pour faire tourner ce programme. La partie C porte sur un autre graphe, que voici au format Nirina974 :

 - 3 ko

Le graphe ressemble à ceci :

On remarque que ce graphe est dessiné comme un réseau social, avec des sommets dont le diamètre est fonction croissante du degré.

Question 21

  • Un problème de décision (de la forme existe-t-il... ?) est dit dans la classe NP s’il existe un algorithme en temps polynomial pour vérifier qu’une solution donnée en est une.
  • Un problème est NP-complet si tout problème de la classe NP se ramène à celui-là par une réduction polynomiale (en pratique il suffit d’en trouver un).

Dans la suite on se donne :

  1. COLORS = ['bleu', 'rouge', 'vert']
  2. G_EX = [[], [2, 3, 4], [1, 4, 5], [1], [1, 2, 5], [2, 4]]
  3. COLOR_EX = [0, 0, 1, 1, 2, 0]

Question 22

  1. def bonnesCouleurs(g, couleurs):
  2.     """retourne True si et seulement si couleurs est une coloration correcte
  3.    des sommets de g ie que tous les sommets de g sont bien coloriés."""
  4.    
  5.     def sommet_bien_colorie(s):
  6.         # un sommet s est bien colorié s'il n'a pas la même couleur que ses voisins
  7.         # autrement dit : si tous ses voisins ont une couleur différente
  8.         return all(couleurs[s] != couleurs[v] for v in g[s])
  9.    
  10.     return all(sommet_bien_colorie(s) for s in range(len(g)))

La fonction python all (présentée dans cet article) permet une solution particulièrement concise et élégante de la fonction bonnesCouleurs : un graphe est bien colorié si tous ses sommets sont bien coloriés. Un sommet est lui même bien colorié s’il ne partage pas sa couleur avec l’un de ses voisins.

Par exemple :

>>> bonnesCouleurs(G_EX, COLOR_EX)
True

Question 23

L’énoncé donnait cet algorithme pour trouver une bonne coloration (aucune garantie sur la minimalité de cette coloration) :

  1. choisir la première couleur disponible ;
  2. tant qu’il existe un sommet non colorié répéter les étapes 3 à 6 :
  3. choisir un sommet s non colorié, et le colorier avec la couleur courante ;
  4. répéter l’étape 5 pour tout sommet t non colorié ;
  5. si t n’est adjacent à aucun sommet colorié avec la couleur courante, le colorier avec la couleur courante ;
  6. choisir une nouvelle couleur ;
  7. fin de l’algorithme.

Voici la traduction de l’algorithme sous forme de fonction Python :

  1. def coloriage(g):
  2.     nb_sommets = len(g)
  3.     une_couleur = 0
  4.     couleurs = [None] * nb_sommets
  5.     s_non_colories = list(range(nb_sommets))
  6.     while s_non_colories:
  7.         s = s_non_colories.pop()
  8.         couleurs[s] = une_couleur
  9.         for t in s_non_colories[:]:
  10.             if coloriable(g[t], couleurs, une_couleur):
  11.                 couleurs[t] = une_couleur
  12.                 s_non_colories.remove(t)
  13.         une_couleur += 1
  14.     return couleurs
  15.        
  16.        
  17. def coloriable(voisins, couleurs, c):
  18.     return all(couleurs[v] != c for v in voisins)

Par exemple :

>>> coloriage(G_EX)
[0, 0, 2, 1, 1, 0]

C’est bien le coloriage de l’énoncé :


Portfolio

JPEG - 57.2 ko

Commentaires

Annonces

Prochains rendez-vous de l’IREM

Réunion de rentrée de l’IREM

- Mercredi 11 septembre 2019, 14h-18h, salle S23.6, PTU, Saint-Denis.

Séminaire de l’IREM

- Mercredi 9 octobre 2019, 14h-18h : amphi 120B, campus du Tampon.
- Mercredi 6 novembre 2019, 14h-18h : salle S23.6, PTU, Saint-Denis.
- Mercredi 27 novembre 2019, 14h-18h : campus du Tampon.
- Mercredi 5 février 2020, 14h-18h : salle S23.6, PTU, Saint-Denis.
- Mercredi 4 mars 2020, 14h-18h : campus du Tampon.
- Mercredi 8 avril 2020, 14h-18h : salle S23.6, PTU, Saint-Denis.

Fête de la science

- Jeudi 14 novembre 2019 : campus du Moufia et IUT de Saint-Pierre.
- Vendredi 15 novembre 2019 : campus du Moufia et campus du Tampon.

Semaine des mathématiques

- Du 23 au 28 mars 2020.


Brèves

Concours externes 2016

dimanche 14 août 2016

Félicitations aux lauréats des concours externes de mathématiques dans l’académie de la Réunion !

Agrégation externe : TESTUD Philippe

CAPES externe : AAH-KENG Julien - ANTOINE Médi - AUBRY Mathieu - DAOUD Issop - ELLIN Thomas - FORICH Romain - FULBERT Cyril - GUEDES Audrey - LAFOSSE Gérard - LEBON Marie - LEONG Élodie - NATIVEL David - PAYET Samuel - PAYET Stéphane - SAUGER Raphaël - SIHOU Erika - SOUCANE Marina - TRULES Florent - TRUPIANO Haris

3e CAPES : ROUX Cécile

CAPLP externe : AKOURI Pierre - CADJEE Oussama - DALLEAU Jérémie - GAZEMONT Brice - GETOIS Flora - HOARAU Julien - PAYET Elisabeth - PAYET Geneviève - RUBEL Vincent - SAVOURY Mickaël - TECHER Frédérique - TELEF Leila

CAFEP-CAPLP : LEMARCHAND Pierre

Concours internes 2016

dimanche 14 août 2016

Félicitations aux lauréats des concours internes de mathématiques dans l’académie de la Réunion !

Agrégation interne : ALVANITAKIS Christophe - FONTAINE Bernard - HAYON Valérie - ROBERT Michaël

CAPES interne : GRAU Jeremy - LALLEMAND Valérie - PERRY Stéphane - ZAGJIVAN Chandane

CAPES réservé : VINGUEDASSALOM Fabrice

CAER-CAPES : AQUILIMEBA Muriel - DOBI Alexandre - VELLIN Olivier - VERDIER Géraldine

CAPLP interne : COMEAU Élodie

CAPLP réservé : GRONDIN Sonia

Concours internes 2015

mercredi 8 juillet 2015

Félicitations aux lauréats des concours internes de mathématiques dans l’académie de la Réunion !

Agrégation interne : AUBERTIN Sébastien - COETANA Sandrine - ÉTHÈVE Emmeric - GOPAL-PANON Mathieu - PAYET Loïc - TIRANO Hérode

CAPES interne : ARNOULD Xavier - GIRAUD François - SERIACAROUPIN Johann - SEVERIN Didier - ZETTOR Émilie

CAER-CAPES : HOAREAU Laurent

CAPLP interne : BÉNARD Laurent - FREDELiSY Samuel

Concours externes 2015

mercredi 8 juillet 2015

Félicitations aux lauréats des concours externes de mathématiques dans l’académie de la Réunion !

Agrégation externe : DODAT Mohammad

CAPES externe : BARBEYROL Yann - BOYER Julien - BUFFO THomas - CLAIN Thomas - CONJODESOLEYEN Haridasse - COUFFINHAL Thierry - D’EURVEILHER Samuel - DODAT Mohammad - JALA Marjorie - LEBON Valérie - LEBRETON Olivier - MAHOT Anaïs - MOUTOUSSAMY Laurent - NAMLACAMOURIMA Olivier - PAYET Benoît - PITOU Bruny - ROBERT Daride - SOUILLOT Quentin - TÉCHER Lénaïc - VAITILINGOM Laurent - VILY Adrien - VIRIN Nicolas - ZETTOR Jonathan

CAFEP-CAPES : DESHAYES Jean-Gabriel

CAPLP externe : AUBEELUCK Ibrahim - BELKESSAM Isma - COURTIN Louis - ELIAC Julien - IGOUF Dimitri - MOULAN Loukman - PONTHIEUX Loïc

Inscription en master MEEF 2015-2016

dimanche 22 mars 2015

Les candidats doivent se pré-inscrire et télécharger le dossier de candidature du 23 mars au 23 avril 2015 sur le site de l’ESPE de la Réunion.

Le dossier de candidature complété et accompagné des pièces demandées, est à retourner par courrier ou sur place à l’ESPE, au plus tard le 24 avril 2015 à 12h00 (heure locale), le cachet de la Poste faisant foi.

Concours externes 2014

samedi 12 juillet 2014

Félicitations aux lauréats des concours externes de mathématiques dans l’académie de la Réunion !

CAPES externe : ARAYE Jocya - BOMINTHE Julien - CARO Stéphanie - DÉSIRÉ Jean-Pierre - DODAT Mohammad - ELLIN Thomas - FRANÇOISE Armelle - FRONTIN Hortense - GASP Richard - GUICHARD Audrey - JAGLALE Priscilla - MAILLOT David - MARTIN Élodie - RASSABY Reine-Claude - ROBERT Amandine - TOBÉ FLorian - VALMONT Guilllaume

CAFEP-CAPES : AUBRY François

CAPLP externe : : RIVIÈRE Jean-François - VERHILLE Arnaud

CAPES externe exceptionnel : ABRAHAM Christophe - CADET Bertrand - CARPAYE Romain - FONTAINE Paul - HOAREAU Julien - HUGONNET Marion - MAILLOT Carine - PAYET Jean-Willy - RANDRIANARIVONY Salim - ROBERT Indira - ROBINSON Lorenza - RODRIGUEZ Laëtitia

CAFEP-CAPES exceptionnel : TOARD Natacha

3e CAPES exceptionnel : FRUTEAU DE LACLOS Désiré

CAPLP externe exceptionnel : FLORENTIN Matthieu - HOARAU Johnny

Concours internes 2014

jeudi 10 juillet 2014

Félicitations aux lauréats des concours internes de mathématiques dans l’académie de la Réunion !

Agrégation interne : ESPINASSE Oriane - HOUSSEN Haroune

CAPES interne : FONTAINE Yohann - LANCIANI Sophie - LEVOYER Nicolas - SIVARADJAM Kamala - WOLTER Audrey

CAPLP interne : RAMAKISTIN Laurent - RIVIÈRE Jean-François

Mathématiques pour biologie et chimie

samedi 22 mars 2014

Khalid Addi, Daniel Goeleven et Rachid Oujja publient chez Ellipses un livre intitulé Principes mathématiques pour biologistes, chimistes et bioingénieurs . Une approche pluridisciplinaire avec de nombreuses et riches applications. Ce livre sera utile aux étudiants qui préparent le CAPES de mathématiques et le CAPLP mathématiques-sciences physiques et chimiques, notamment pour illustrer leurs leçons d’oral.

Concours externes 2013

mardi 6 août 2013

Félicitations aux lauréats des concours externes de mathématiques dans l’académie de la Réunion !

Agrégation externe : TSANG-CHIN-SANG Melissa

CAPES externe : ALI Fayadhui - APALAMA Ambigueï - FAILLE Benjamin - HOARAU Jenny - IATALESE Mickaël - K/BIDI Yndranye - PAYET Raphaël - TACITE Aurélie - TESTUD Philippe

CAFEP-CAPES : CHASSAGNE Alain

3e concours du CAPES : DÉSIGNÉ David - FALOYA Marie-Astrid

CAPLP externe : GERVAIS Sylvain - GONTHIER Alexandre - HASNAOUI Ghania - IMIZA Marie-Annick - LANGREZ Amandine - PAYET Emeline - SALMI Elmustafa - SETRUK Guillaume - VALMAR Nicolas - WATERSTONE May

Concours internes 2013

samedi 29 juin 2013

Félicitations aux lauréats des concours internes de mathématiques dans l’académie de la Réunion !

Agrégation interne : BLANC David - COTTON Gilles - DUQUESNOY Thierry - GARNIER Olivier - GATINEAU Emmanuel - GAUTRET Laurent - GIGANDET Nathalie - MESTRE Philippe

CAER agrégation : GOUELO Fabrice

CAPES interne : CADET Jean-Paul - DIONOT Carla - HOARAU Sandrine - SALMI Elmustafa

CAER CAPES : CHASSAING Boris - HUBERT Michaël

CAPLP interne : KARIM Samir

Statistiques

Dernière mise à jour

jeudi 5 septembre 2019

Publication

847 Articles
Aucun album photo
140 Brèves
11 Sites Web
145 Auteurs

Visites

100 aujourd'hui
1678 hier
2938987 depuis le début
25 visiteurs actuellement connectés