Problème 1 : La base 3 équilibrée
PARTIE III --- Chemins de Delannoy
Question 8
(8a) Chemin de 2019 : 2019 = (10-110-110)_e
(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.
def arrivee(n):
def add(a, b):
return a[0]+b[0], a[1]+b[1]
steps = [(1,1), (1,0), (0,1)]
ajout = [0, 0, 1]
pt_arr = (0, 0)
while n > 1: # ici 1 pour ne pas prendre en compte le premier chiffre 1
reste = n % 3
pt_arr = add(pt_arr, steps[reste])
n = n // 3 + ajout[reste]
return pt_arrQuestion 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é :
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 :
N = 9
App = [True, True, False, True, True, True, True, True, True]
P = 8
Succ = [[1], [], [], [6], [0], [3], [0], [4], [0, 1, 7]];
G = [App, Succ, P]Question 10
def mem(i, g):
"""renvoie True si le sommet numéro i est dans le graphe représenté par g"""
return g[0][i]Question 11
def pred(i, g):
"""renvoie la liste des sommets j tels que j->i est présent dans le graphe g."""
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
def sansSuccesseur(g):
"""renvoie un numéro i tel que Mi n'a pas de successeur
ou -1 si un tel sommet n'existe pas dans le graphe g"""
for i in range(N):
if mem(i, g) and g[1][i] == []:
return i
return -1Par exemple :
>>> sansSuccesseur(G)
1Question 13
import copy
def suppr(i, g):
"""crée et renvoie une copie de g privé du sommet i et des arcs qui s'y réfèrent"""
h = copy.deepcopy(g)
h[2] -= 1
h[0][i] = False
h[1][i] = []
for j in range(N):
if mem(j, h) and i in h[1][j]:
h[1][j].remove(i)
return hQuestion 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)
def ordreTopologique(g):
"""renvoie une liste L telle que L[i] vaut N(i)
si N existe et None sinon"""
n = len(g[0])
L = [-1] * n
def parcoursReussi(g):
p = g[2]
if p != 0:
s = sansSuccesseur(g)
if s == -1:
return False
else:
L[s] = p
return parcoursReussi(suppr(s, g))
else:
return True
b = parcoursReussi(g)
if b:
return L
else:
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]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 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 :
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 :
COLORS = ['bleu', 'rouge', 'vert']
G_EX = [[], [2, 3, 4], [1, 4, 5], [1], [1, 2, 5], [2, 4]]
COLOR_EX = [0, 0, 1, 1, 2, 0] Question 22
def bonnesCouleurs(g, couleurs):
"""retourne True si et seulement si couleurs est une coloration correcte
des sommets de g ie que tous les sommets de g sont bien coloriés."""
def sommet_bien_colorie(s):
# un sommet s est bien colorié s'il n'a pas la même couleur que ses voisins
# autrement dit : si tous ses voisins ont une couleur différente
return all(couleurs[s] != couleurs[v] for v in g[s])
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)
TrueQuestion 23
L’énoncé donnait cet algorithme pour trouver une bonne coloration (aucune garantie sur la minimalité de cette coloration) :
- choisir la première couleur disponible ;
- tant qu’il existe un sommet non colorié répéter les étapes 3 à 6 :
- choisir un sommet s non colorié, et le colorier avec la couleur courante ;
- répéter l’étape 5 pour tout sommet t non colorié ;
- si t n’est adjacent à aucun sommet colorié avec la couleur courante, le colorier avec la couleur courante ;
- choisir une nouvelle couleur ;
- fin de l’algorithme.
Voici la traduction de l’algorithme sous forme de fonction Python :
def coloriage(g):
nb_sommets = len(g)
une_couleur = 0
couleurs = [None] * nb_sommets
s_non_colories = list(range(nb_sommets))
while s_non_colories:
s = s_non_colories.pop()
couleurs[s] = une_couleur
for t in s_non_colories[:]:
if coloriable(g[t], couleurs, une_couleur):
couleurs[t] = une_couleur
s_non_colories.remove(t)
une_couleur += 1
return couleurs
def coloriable(voisins, couleurs, c):
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é :
Commentaires