Corrigé du sujet d’informatique au CAPES 2017

apparition de Python au concours
dimanche 28 mai 2017
par  Alain BUSSER

Voici le sujet en pdf [1] :

Dans cet article, on complètera les scripts Python par l’équivalent en CoffeeScript, pour permettre d’utiliser ce logiciel en ligne, programmé en français, et doté de possibilités graphiques.

On se permettra également, dans cet article, une digression sur le langage Prolog, qui est fondé sur le backtracking.

Problème 1 : Sudoku

Introduction

L’annexe du sujet comprend des exemples de découpage en tranches, et le début rappelle qu’une matrice est une liste de listes. La grille de Sudoku est donc une liste de lignes :

  1. M = [[2]+[0]*3+[9,0,3]+[0]*2, [0,1,9,0,8]+[0]*2+[7,4],
  2. [0]*2+[8,4]+[0]*2+[6,2,0], [5,9,0,6,2,1]+[0]*3,
  3. [0,2,7]+[0]*3+[1,6,0], [0]*3+[5,7,4,0,9,3],
  4. [0,8,5]+[0]*2+[9,7]+[0]*2, [9,3]+[0]*2+[5,0,8,4,0],
  5. [0]*2+[2,0,6]+[0]*3+[1]]

Télécharger

Chaque ligne est une liste de nombres. La matrice 9×9 ci-dessus ressemble à ceci :

200
019
008
090
080
400
300
074
620
590
027
000
621
000
574
000
160
093
085
930
002
009
050
060
700
840
001

CoffeeScript

Pour tester les scripts de la partie CoffeeScript, il n’y a qu’à les copier-coller vers alcoffeethmique. Déjà, la définition de la matrice M pour la suite, se fait sans les raccourcis de Python :

  1. M = [[2,0,0,0,9,0,3,0,0], [0,1,9,0,8,0,0,7,4],
  2. [0,0,8,4,0,0,6,2,0], [5,9,0,6,2,1,0,0,0],
  3. [0,2,7,0,0,0,1,6,0], [0,0,0,5,7,4,0,9,3],
  4. [0,8,5,0,0,9,7,0,0], [9,3,0,0,5,0,8,4,0],
  5. [0,0,2,0,6,0,0,0,1]
  6. ]

Télécharger

Préliminaire

1. Si la grille est complète, la somme des éléments d’une ligne est 1+2+3+4+5+6+7+8+9 puisque cette somme ne change pas si on trie les termes dans l’ordre croissant. Réciproquement, si la somme est inférieure à 45, c’est qu’il y a au moins un 0 quelque part dans la ligne : La grille est alors incomplète. On va utiliser ce résultat pour simplifier le code de la question suivante.

2. Pour tester si la ligne i est complète, il suffit de comparer la somme de ses termes avec 45 :

  1. def ligne_complete(L,i):
  2.         return sum(L[i]) == 45
  3.        

Télécharger

Pour tester avec un ordinateur les fonctions suivantes, il est nécessaire de programmer aussi les fonctions évoquées dans le sujet sans obligation de les écrire. Les voici donc :

  1. def colonne_complete(L,i):
  2.         return sum(L[j][i] for j in range(9)) == 45
  3.  
  4. def carre_complet(L,i):
  5.         return sum(L[j+3*(i//3)][k+(3*i)%9] for j in range(3) for k in range(3)) == 45

Télécharger

3. La fonction préliminaire qui teste si une grille est complète peut alors s’écrire ainsi :

  1. def complet(L):
  2.         ok = True
  3.         for i in range(8):
  4.                 ok &= ligne_complete(L,i)
  5.                 ok &= colonne_complete(L,i)
  6.                 ok &= carre_complet(L,i)
  7.         return ok

Télécharger

CoffeeScript

Voici les mêmes fonctions en CoffeeScript :

  1. ligne_complete = (L,i) ->
  2.     (laSommeDe L[i]) == 45
  3.  
  4. colonne_complete = (L,i) ->
  5.     (laSommeDe (M[j][i] pour j dans [0...9])) == 45
  6.  
  7. carre_complet = (L,k) ->
  8.     (laSommeDe _.flatten (M[i+3*troncature(k/3)][(j+3*k)%9] pour j dans [0...3] pour i dans [0...3])) == 45
  9.  
  10.  
  11. complet = (L) ->
  12.     ok = true
  13.     pour i dans [0...9]
  14.         ok &&= ligne_complete L, i
  15.         ok &&= colonne_complete L, i
  16.         ok &&= carre_complet L, i
  17.     ok

Télécharger

Annexes

4. Le code de la fonction ligne de l’énoncé, une fois complété, ressemble à ceci :

  1. def ligne(L,i):
  2.         chiffre = []
  3.         for j in range(9):
  4.                 if L[i][j]>0:
  5.                         chiffre.append(L[i][j])
  6.         return chiffre

Télécharger

Mais avec une liste en compréhension, on pouvait faire plus court :

  1. def ligne(L,i):
  2.         return [L[i][j] for j in range(9) if L[i][j]>0]

Télécharger

La fonction colonne va d’ailleurs être définie de façon similaire, puisqu’elle n’était pas demandée sous une forme précise :

  1. def colonne(L,i):
  2.         return [L[j][i] for j in range(9) if L[j][i]>0]

Télécharger

5. Pour l’abscisse, il suffit de calculer les valeurs successives du quotient euclidien de i par 3 : 0,0,0,1,1,1,2,2,2, puis les produits par 3 : 0,0,0,3,3,3,6,6,6. Idem pour les ordonnées.

6. La fonction attendue dans l’énoncé est celle-ci :

  1. def carre(L,i,j):
  2.         icoin, jcoin = 3*(i//3), 3*(j//3)
  3.         chiffre = []
  4.         for i in range(icoin,icoin+3):
  5.                 for j in range(jcoin,jcoin+3):
  6.                         if (L[i][j] > 0):
  7.                                 chiffre.append(L[i][j])
  8.         return chiffre

Télécharger

Mais la lettre i désigne, dans ce code, deux variables différentes : Celle qui est passée en argument à la fonction carre, et l’indice de boucle qui est une variable locale : Il n’y a donc pas de risque de conflit entre ces deux variables, mais nommer autrement les indices de boucles (k et l par exemple) aboutit à un code plus clair :

  1. def carre(L,i,j):
  2.         icoin, jcoin = 3*(i//3), 3*(j//3)
  3.         return [L[k][l] for k in range(icoin,icoin+3) for l in range(jcoin,jcoin+3) if L[k][l]>0]

Télécharger

7. La fonction conflit attendue dans l’énoncé peut ressembler à ceci :

  1. def conflit(L,i,j):
  2.         return ligne(L,i)+colonne(L,j)+carre(L,i,j)

Télécharger

Mais avec les ensembles, on évite les redondances et on se simplifie la suite (la question suivante demande le complément d’un ensemble dans un autre) :

  1. def conflit(L,i,j):
  2.         return set(ligne(L,i)+colonne(L,j)+carre(L,i,j))-set([L[i][j]])

Télécharger

8. La fonction complétée ressemble maintenant à ceci :

  1. def chiffres_ok(L,i,j):
  2.         ok = []
  3.         conflit = conflit(L,i,j)
  4.         for k in range(1,10):
  5.                 if (k not in conflit):
  6.                         ok.append(k)
  7.         return ok

Télécharger

Cependant, il est étrange d’avoir nommé « ok » une variable qui n’est pas booléenne, et le mot « conflit » désigne deux choses différentes : une liste (variable locale) et une fonction. En plus, la version avec ensembles est nettement plus concise :

  1. def chiffres_ok(L,i,j):
  2.         return set(range(1,10)) - conflit(L,i,j)

Télécharger

CoffeeScript

Avec les ensembles d’alcoffeethmique :

  1. ligne = (L,i) ->
  2.     nouvel Ensemble _.flatten ([L[i][j] pour j dans [0..8] quand L[i][j]>0])
  3.  
  4. colonne = (L,i) ->
  5.     nouvel Ensemble _.flatten [L[j][i] pour j dans [0..8] quand L[j][i]>0]
  6.  
  7.  
  8. carre = (L,i,j) ->
  9.         [icoin, jcoin] = [3*troncature(i/3), 3*troncature(j/3)]
  10.         S = nouvel Ensemble []
  11.         pour k dans [icoin..icoin+2]
  12.             pour l dans [jcoin..jcoin+2]
  13.                 S.ajoute L[k][l] si L[k][l]>0
  14.         S
  15.  
  16. conflit = (L,i,j) ->
  17.     (ligne M, i).union(colonne M, j).union(carre M, i, j)
  18.  
  19. chiffres_ok = (L,i,j) ->
  20.     conflit(L,i,j).complémentDans( nouvel Ensemble [1..9])

Télécharger

Naïf

9. Les chiffres que l’on peut écrire à la case (i,j) peut alors être calculé avec

  1. def nb_possible(L,i,j):
  2.         return len(chiffres_ok(L,i,j))

Télécharger

10. La fonction « corrigée » est celle-ci (les erreurs volontairement introduites concernaient l’indexation à partir de 0 et le double-égal pour les tests) :

  1. def un_tour(L):
  2.         changement = False
  3.         for i in range(9):
  4.                 for j in range(9):
  5.                         if (L[i][j] == 0):
  6.                                 if (nb_possible(L,i,j) == 1):
  7.                                         L[i][j] = chiffres_ok(L,i,j)[0]
  8.                                         changement = True
  9.         return changement

Télécharger

CoffeeScript

Voici la version CoffeeScript avec les ensembles d’alcoffeethmique :

  1. nb_possible = (L,i,j) ->
  2.     chiffres_ok(L,i,j).cardinal()
  3.  
  4. un_tour = (L) ->
  5.     changement = false
  6.     pour i dans [0..8]
  7.         pour j dans [0..8]
  8.             si L[i][j] == 0
  9.                 si nb_possible(L,i,j) == 1
  10.                     L[i][j] = chiffres_ok(L,i,j).support[0]
  11.                     changement = true
  12.     changement

Télécharger

Effet obtenu

Avec la matrice M de l’énoncé :

200
019
008
090
080
400
300
074
620
590
027
000
621
000
574
000
160
093
085
930
002
009
050
060
700
840
001

Après un tour, la matrice est devenue :

200
019
008
090
080
400
300
574
629
590
027
061
621
038
574
487
165
293
085
936
002
009
050
060
730
842
951

11. La fonction qui résout par algorithme « naïf » le Sudoku est celle-ci :

  1. def complete(L):
  2.         pas_fini = True
  3.         while pas_fini:
  4.                 pas_fini = un_tour(L)
  5.         return complet(L)

Télécharger

CoffeeScript

La version alcoffeethmique :

  1. complete = (L) ->
  2.     pas_fini = true
  3.     tant que pas_fini
  4.         pas_fini = un_tour L
  5.     complet L

Télécharger

Elle fournit la grille complétée :

254
619
378
796
382
415
318
574
629
593
427
861
621
938
574
487
165
293
185
936
742
249
157
863
736
842
951

Backtracking

12. La fonction « case suivante » balaye, ligne par ligne, le sudoku :

  1. def case_suivante(pos):
  2.         if (pos[1]<8):
  3.                 return [pos[0],pos[1]+1]
  4.         else:
  5.                 return [pos[0]+1,0]

Télécharger

13. La résolution du sudoku par bracktracking se fait par

  1. def backtracking(L,pos):
  2.         if pos == [9,0] :
  3.                 return True
  4.         i,j = tuple(pos)
  5.         if L[i][j] != 0 :
  6.                 return backtracking(L,case_suivante(pos))
  7.         for k in chiffres_ok(L,i,j):
  8.                 L[i][j] = k
  9.                 if backtracking(L,case_suivante(pos)):
  10.                         return True
  11.         L[i][j] = 0
  12.         return False
  13.  
  14.  
  15.        
  16. def solution_sudoku(L):
  17.         return backtracking(L,[0,0])

Télécharger

14. Si p cases sont remplies, il reste 81-p cases. Chacune d’elles est testée au maximum 9 fois, donc l’arbre des appels récursifs de la fonction backtracking ne comprend pas plus de 981-n nœuds.

15. Si le sudoku admet plusieurs solutions, la fonction solution_sudoku renvoie True puisqu’il y a au moins 1 solution. Il en est de même avec la grille initialisée à 0.

16. Une suite de de Bruijn d’ordre 4 sur 3 symboles permettrait de parcourir l’arbre en appelant moins souvent la variable pos.

à propos de Backtracking

Prolog

Le langage de programmation Prolog ne sait faire qu’une chose : Le backtracking. Autant dire que pour résoudre un sudoku, ce langage est particulièrement adapté. C’est l’occasion d’explorer un peu Prolog en ligne et pas seulement sur des sudokus.

sudoku

Pour résoudre le sudoku de l’énoncé, on peut utiliser ce script :

  1. :- use_rendering(sudoku).
  2.  
  3. :- use_module(library(clpfd)).
  4.  
  5. sudoku(Rows) :-
  6.         length(Rows, 9), maplist(length_(9), Rows),
  7.         append(Rows, Vs), Vs ins 1..9,
  8.         maplist(all_distinct, Rows),
  9.         transpose(Rows, Columns), maplist(all_distinct, Columns),
  10.         Rows = [A,B,C,D,E,F,G,H,I],
  11.         blocks(A, B, C), blocks(D, E, F), blocks(G, H, I).
  12.  
  13. length_(L, Ls) :- length(Ls, L).
  14.  
  15. blocks([], [], []).
  16. blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-
  17.         all_distinct([A,B,C,D,E,F,G,H,I]),
  18.         blocks(Bs1, Bs2, Bs3).
  19.  
  20. problem(1,[[2,_,_,_,9,_,3,_,_],
  21.                    [_,1,9,_,8,_,_,7,4],
  22.                    [_,_,8,4,_,_,6,2,_],
  23.                    [5,9,_,6,2,1,_,_,_],
  24.                    [_,2,7,_,_,_,1,6,_],
  25.                    [_,_,_,5,7,4,_,9,3],
  26.                    [_,8,5,_,_,9,7,_,_],
  27.                    [9,3,_,_,5,_,8,4,_],
  28.                    [_,_,2,_,6,_,_,_,1]]).
  29.            

Télécharger

Explications

Ici, sudoku est un prédicat. En Prolog on lit le symbole  :- par un « si ». Le début de script se lit donc « Rows est une grile de sudoku si chacune des conditions suivantes est réalisée » :

  • Il y a 9 lignes, et chacune a 9 cases ;
  • les lignes Vs de Rows comprennent tous les nombres de 1 à 9 ;
  • les éléments de chaque ligne sont tous différents deux à deux ;
  • les lignes de la transposée (c’est-à-dire les colonnes de la grillede sudoku) sont elles aussi composées de nombres tous différents ;
  • les lignes de la grille peuvent être nommées de A à I ;
  • les lignes A, B, C forment une liste de 3 blocs 3×3 corrects ;
  • idem pour les lignes D, E, F ;
  • idem pour les lignes G, H, I.

S’ensuit une redéfinition de la longueur d’une liste pour qu’on puisse donner le nombre avant la liste ; puis il reste à définir ce qu’on entend par « blocs 3×3 corrects » :

  • Les blocs vides sont considérés comme corrects (bizarre mais il faut bien une condition d’arrêt pour la récursivité ; on peut toujours dire que « correct » veut dire « pas contradictoire avec les règles du jeu »).
  • En concaténant Bs1 aux lignes A, B et C, et en faisant de même pour Bs2 avec D, E, F et Bs3 avec G, H et I, on obtient un bloc correct si
    • les lignes de A à I ne contiennent que des éléments distincts ;
    • Bs1, Bs2 et Bs3 forment des blocs 3×3 corrects.

La question

?- problem(1, Rows), sudoku(Rows).

(ne pas oublier le point) fournit alors la solution

Rows = [[2, 5, 4, 7, 9, 6, 3, 1, 8], [6, 1, 9, 3, 8, 2, 5, 7, 4], [3, 7, 8, 4, 1, 5, 6, 2, 9], [5, 9, 3, 6, 2, 1, 4, 8, 7], [4, 2, 7, 9, 3, 8, 1, 6, 5], [8, 6, 1, 5, 7, 4, 2, 9, 3], [1, 8, 5, 2, 4, 9, 7, 3, 6], [9, 3, 6, 1, 5, 7, 8, 4, 2], [7, 4, 2, 8, 6, 3, 9, 5, 1]]

Que swi-prolog sait afficher plus joliment :

clpfd

La résolution du sudoku avec swi-prolog fait appel à clpfd : Cet acronyme signifie Constraint Logic Programming over Finite Domains, ce qu’on peut traduire par les faits suivants :

  • Le domaine que l’on considère est fini (pour le facteur de Mafate par exemple, il y a un nombre fini d’ilets et un nombre fini d’échelles).
  • On considère une relation sur ce domaine fini.
  • Cette relation est soumise à des contraintes (pour la grille de sudoku, il n’est par exemple pas possible d’avoir deux nombres différents sur une même ligne).
  • Le problème peut se résoudre par backtracking (« Logic programming » s’abrège en Prolog) ;
  • Le domaine fini peut être représenté par des entiers. C’est par exemple le cas pour le facteur de Mafate.

Voitures

Voici un extrait du sujet de Rallye 2014 :

Cinq voitures disputent une course.

 Reconstituez le classement final à l’aide des indices suivants :

  • La voiture verte, qui n’a pas gagné, est arrivée avant la voiture bleue, qui ne figure pas sur le podium.
  • Deux voitures séparent la voiture jaune de la voiture bleue.
  • La voiture rouge a terminé avant la voiture violette, séparées par une voiture.
  • La voiture jaune et la voiture rouge ne se suivent pas.

Pour modéliser ce problème en Prolog, on se propose de considérer 5 variables entières Bleue, Jaune, Rouge, Verte et Violette (en Prolog, les noms des variables commencent par des majuscules) puis de traduire les diverses contraintes de l’énoncé. L’égalité est donnée par is et la négation par +. La conjonction est notée par une virgule et la disjonction est notée par un point-virgule :

ÉnoncéProlog
Cinq voitures permutation([Bleue,Jaune,Rouge,Verte,Violette], [1,2,3,4,5])
La voiture verte, qui n’a pas gagné, Verte > 1
est arrivée avant la voiture bleue, Verte < Bleue
qui ne figure pas sur le podium Bleue > 3
Deux voitures séparent la voiture jaune de la voiture bleue (Jaune is Bleue+3; Bleue is Jaune+3)
La voiture rouge a terminé avant la voiture violette, séparées par une voiture Violette is Rouge+2
La voiture jaune et la voiture rouge \+ (Jaune is Rouge+1)
ne se suivent pas \+ (Rouge is Jaune+1)

Le script Prolog au complet est celui-ci :

  1. course([Bleue,Jaune,Rouge,Verte,Violette]) :-
  2.     permutation([Bleue,Jaune,Rouge,Verte,Violette], [1,2,3,4,5]),
  3.     Verte > 1,
  4.     Verte < Bleue,
  5.     Bleue > 3,
  6.     (Jaune is Bleue+3; Bleue is Jaune+3),
  7.     Violette is Rouge+2,
  8.     \+ (Jaune is Rouge+1),
  9.     \+ (Rouge is Jaune+1).

Télécharger

Il fournit cette solution :

Mafate

Voici un niveau du facteur de Mafate :

Il signifie que

  • les échelles sont, dans l’ordre croissant, de longueurs 3,4,5,6,7,8 et 9 (on va donc imposer, comme contrainte, que la variable Echelles soit une permutation de ces nombres) ;
  • les ilets autres que ceux de départ et d’arrivée) sont, dans l’ordre croissant, de hauteurs 1,2,4,7,8 et 10 (une fois qu’on ajoute les ilets de hauteur 3 et 9, on va donc également avoir comme contrainte, que la variable Ilets soit une permutation de 1,2,3,4,7,8,9,10) ;
  • le premier ilet que le facteur doit visiter est de hauteur 3 (en Prolog on écrira ça debut(Ilets,3)) ;
  • le dernier ilet que le facteur visitera sera de hauteur 9 en Prolog on écrira ça fin(Ilets,9)).

Reste à programmer les utilitaires debut, fin, et surtout deltas, qui associe à la liste des hauteurs, celle des différences entre hauteurs :

  • s’il y a moins de deux ilets, la liste des échelles est vide.
  • sinon, c’est que la liste des ilets commence par les ilets de hauteurs A et B, suivis par une liste résiduelle T, et que
    • N est la différence entre A et B, dans un certain ordre ;
    • N est positif (c’est une distance) ;
    • les échelles disposées entre l’ilet B et les suivants constituent une liste D1 ;
    • En ajoutant cette liste D1 à N, on obtient la liste d’échelles D.
  • Dans ce cas la liste D est celle des échelles joignant les ilets de la liste L :
  1. deltas(L,[]) :-
  2.     length(L,N),
  3.     N < 2.
  4. deltas([A,B|T],D) :-
  5.     (   N is B-A; N is A-B),
  6.     N > 0,
  7.     deltas([B|T],D1),
  8.     append([N],D1,D).

Télécharger

Pour dire que la liste commence par D, on demande juste que l’élément de la liste de numéro 1 soit égal à D ; par contre pour dire que la liste se termine par Fin, on demande que, si la liste est de longueur N, l’élément numéro N de la liste soit égal à Fin :

  1. fin(Liste,Fin) :-
  2.     length(Liste,N),
  3.     nth1(N,Liste,Fin).
  4. debut(Liste,D) :-
  5.     nth1(1,Liste,D).

Télécharger

Avec ces utilitaires, le script résolvant le niveau du facteur de Mafate est celui-ci :

  1. mafate(Ilets,Echelles) :-
  2.     debut(Ilets,3),
  3.     fin(Ilets,9),
  4.     permutation(Ilets,[1,2,3,4,7,8,9,10]),
  5.     deltas(Ilets,Echelles),
  6.     permutation(Echelles,[3,4,5,6,7,8,9]).

Télécharger

En entrant ?- mafate(I,E). on apprend alors que

E = [5, 4, 3, 6, 9, 8, 7],
I = [3, 8, 4, 7, 1, 10, 2, 9]

(on rappelle qu’en Prolog, la virgule représente une conjonction).

Script complet

  1. deltas(L,[]) :-
  2.     length(L,N),
  3.     N < 2.
  4. deltas([A,B|T],D) :-
  5.     (   N is B-A; N is A-B),
  6.     N > 0,
  7.     deltas([B|T],D1),
  8.     append([N],D1,D).
  9.  
  10. fin(Liste,Fin) :-
  11.     length(Liste,N),
  12.     nth1(N,Liste,Fin).
  13. debut(Liste,D) :-
  14.     nth1(1,Liste,D).
  15.  
  16. mafate(Ilets,Echelles) :-
  17.     debut(Ilets,3),
  18.     fin(Ilets,9),
  19.     permutation(Ilets,[1,2,3,4,7,8,9,10]),
  20.     deltas(Ilets,Echelles),
  21.     permutation(Echelles,[3,4,5,6,7,8,9]).

Télécharger

Skyscrapers

Ce sujet est extrait du rallye 2017 (sujet d’entraînement). On constate (même si ce n’était pas évoqué dans le sujet) qu’il s’agit de sudoku 4×4, au sens où les blocs 2×2 contiennent chacun une seule fois chacun des chiffres 1,2,3 et 4. Le premier des utilitaires ad hoc est celui qui donne la liste, dans l’ordre décroissant, des gratte-ciels visibles depuis la droite (ou l’Est). On la définit par récurrence :

  • s’il n’y a qu’un seul gratte-ciel, il est le seul à être visible ;
  • sinon,
    • si le gratte-ciel suivant est plus petit que le dernier gratte-ciel visible, on ne le voit pas et il n’est pas rajouté à la liste ;
    • sinon, il est visible et on le rajoute au début de la liste.

En Prolog, cette fonction s’écrit ainsi :

  1. ndecr([A],[A]).
  2. ndecr([N|L],D) :-
  3.     ndecr(L,D),
  4.     nth0(0,D,M),
  5.     N < M.
  6. ndecr([N|L],D) :-
  7.     ndecr(L,D1),
  8.     nth0(0,D1,M),
  9.     N > M,
  10.     append([N],D1,D).

Télécharger

Pour obtenir la liste des immeubles visibles depuis la gauche,

  • on inverse la liste des immeubles de la rangée ;
  • on calcule, par la fonction précédente, la liste des immeubles visibles depuis la droite, de la rangée inversée ;
  • on inverse le résultat :
  1. ncr(L,D) :-
  2.     reverse(L,M),
  3.     ndecr(M,D1),
  4.     reverse(D1,D).

Télécharger

Le nombre nd (dans l’ordre décroissant) des immeubles visibles depuis la droite, est tout simplement la longueur de la liste précédente. Idem pour le nombre des immeubles visibles depuis la gauche. Et les nombres d’immeubles visibles depuis le nord et depuis le sud, s’obtiennent en appliquant ces fonctions à la transposée de la matrice des immeubles :

no(L,N) :-
   ncr(L,D),
   length(D,N).
nd(L,N) :-
   ndecr(L,D),
   length(D,N).


ouest([A,B,C,D],[Aw,Bw,Cw,Dw]) :-
   no(A,Aw), no(B,Bw), no(C,Cw), no(D,Dw).
est([A,B,C,D],[Ae,Be,Ce,De]) :-
   nd(A,Ae), nd(B,Be), nd(C,Ce), nd(D,De).
nord(M,N) :-
   transpose(M,P),
   ouest(P,N).
sud(M,N) :-
   transpose(M,P),
   est(P,N).

Le fait qu’il n’y a jamais deux immeubles de même hauteur dans une rangée s’exprime en disant que la matrice est stochastique :

  1. stochastique([A,B,C,D]) :-
  2.     permutation(A,[1,2,3,4]),
  3.     permutation(B,[1,2,3,4]),
  4.     permutation(C,[1,2,3,4]),
  5.     permutation(D,[1,2,3,4]).

Télécharger

Et le fait qu’il en est aussi de même pour les colonnes, s’exprime en disant que la matrice est bistochastique, ce qui veut dire qu’elle est stochastique et que sa transposée est aussi stochastique :

  1. bistochastique(M) :-
  2.     stochastique(M),
  3.     transpose(M,N),
  4.     stochastique(N).

Télécharger

Ces utilitaires permettent maintenant de définir une fonction skyscraper ayant pour arguments

  • une liste N des nombres d’immeubles visibles depuis le nord ;
  • une liste W des nombres d’immeubles visibles depuis l’ouest ;
  • une liste E de nombres d’immeubles visibles depuis l’est ;
  • une liste S de nombres d’immeubles visibles depuis le sud (ce sont les listes qui bordent la matrice dans le sujet) ;
  • et une matrice M (ou NY !) contenant les hauteurs (a priori, inconnues) des immeubles (autrement dit, M est une carte tridimensionnelle de la ville).

Cette fonction est maintenant plutôt courte (on a tout fait pour) :

  1. skyscraper(N,W,E,S,M) :-
  2.     bistochastique(M),
  3.     nord(M,N),
  4.     ouest(M,W),
  5.     est(M,E),
  6.     sud(M,S).

Télécharger

Elle résout les deux questions du sujet :

Le script complet

L’affichage des tableaux a été mis en œuvre :

  1. :- use_module(library(clpfd)).
  2. :- use_rendering(table).
  3.  
  4. ndecr([A],[A]).
  5. ndecr([N|L],D) :-
  6.     ndecr(L,D),
  7.     nth0(0,D,M),
  8.     N < M.
  9. ndecr([N|L],D) :-
  10.     ndecr(L,D1),
  11.     nth0(0,D1,M),
  12.     N > M,
  13.     append([N],D1,D).
  14. ncr(L,D) :-
  15.     reverse(L,M),
  16.     ndecr(M,D1),
  17.     reverse(D1,D).
  18. no(L,N) :-
  19.     ncr(L,D),
  20.     length(D,N).
  21. nd(L,N) :-
  22.     ndecr(L,D),
  23.     length(D,N).
  24.  
  25. stochastique([A,B,C,D]) :-
  26.     permutation(A,[1,2,3,4]),
  27.     permutation(B,[1,2,3,4]),
  28.     permutation(C,[1,2,3,4]),
  29.     permutation(D,[1,2,3,4]).
  30. bistochastique(M) :-
  31.     stochastique(M),
  32.     transpose(M,N),
  33.     stochastique(N).
  34.  
  35. ouest([A,B,C,D],[Aw,Bw,Cw,Dw]) :-
  36.     no(A,Aw), no(B,Bw), no(C,Cw), no(D,Dw).
  37. est([A,B,C,D],[Ae,Be,Ce,De]) :-
  38.     nd(A,Ae), nd(B,Be), nd(C,Ce), nd(D,De).
  39. nord(M,N) :-
  40.     transpose(M,P),
  41.     ouest(P,N).
  42. sud(M,N) :-
  43.     transpose(M,P),
  44.     est(P,N).
  45.  
  46.    
  47. skyscraper(N,W,E,S,M) :-
  48.     bistochastique(M),
  49.     nord(M,N),
  50.     ouest(M,W),
  51.     est(M,E),
  52.     sud(M,S).
  53.    

Télécharger


Problème 2 : Enveloppes convexes

Introduction

Dans le sujet, un point est une liste de 2 nombres. Mais pour peu que l’on importe les fonctions du module turtle, on a un objet Vec2D qui peut, en tant que vecteur, être soustrait à un autre « vecteur » (un point en fait) et qui possède une norme notée abs. Pour connaître la distance entre les points (des points Vec2D en l’occurence) P(3,2) et Q(8,5) il suffit donc de faire ainsi :

  1. from turtle import *
  2.  
  3. P = Vec2D(3,2)
  4. Q = Vec2D(8,5)
  5.  
  6. print abs(Q-P)

Télécharger

alcoffeethmique

Dans alcoffeethmique il y a sylvester.js qui permet de faire de la géométrie repérée. Mais aussi, l’objet Point qui permet de faire de la géométrie plane : Si on fait

  1. P = nouveau Point 3, 2
  2. affiche (attrib for attrib of P)

Télécharger

on constate que le point P(3,2) possède les attributs suivants :

x,y,toString,milieu,vecteur,distance

Les deux premiers attributs sont, on s’en doute, les coordonnées de P. Mais le dernier est une fonction, comme le montre ce script :

  1. P = nouveau Point 3, 2
  2. affiche P.distance

Télécharger

Le code affiché est celui d’une fonction en JavaScript, qui rappelle que la distance entre P et Q est la norme du vecteur allant de P à Q. On peut alors se livrer à une introspection sur un vecteur, pour voir comment on calcule sa norme...

Avec sylvester.js on est plus proche du sujet du Capes 2017, comme le montre cette séance d’introspection :

  1. P = $V [3, 2]
  2. affiche (attrib for attrib of P)

Télécharger

La réponse est

elements,e,dimensions,modulus,eql,dup,map,each,toUnitVector,angleFrom,isParallelTo,isAntiparallelTo,isPerpendicularTo,add,subtract,multiply,x,dot,cross,max,indexOf,toDiagonalMatrix,round,snapTo,distanceFrom,liesOn,liesIn,rotate,reflectionIn,to3D,inspect,setElements

Outre les fonctions cross (produit vectoriel) et distanceFrom on constate qu’il y a aussi e ou elements qui est une liste des coordonnées du point (ou du vecteur). Et cette liste est comme celle de l’énoncé ; on peut donc compléter

Un point P du plan muni d’un repère est représenté en Python par une liste de deux valeurs

par

Un point P du plan muni d’n repère est représenté dans sylvester.js par un vecteurs dont les éléments sont une liste de deux valeurs

Pour connaître la distance entre deux points, on peut donc faire

  1. P = $V [3, 2]
  2. Q = $V [8,5]
  3. affiche P.distanceFrom Q

Télécharger

Préliminaires

1. L’annexe du sujet ne fait aucune allusion au module turtle (voir onglet précédent) et il n’était donc pas prévu d’utiliser les vec2D de la tortue. Mais il est explicitement fait allusion au module math qui possède une fonction hypot permettant de calculer la longueur de l’hypoténuse d’un triangle, à partir des longueurs (ou mesures algébriques) des côtés de l’angle droit. Le code suivant devait donc, a priori, être autorisé :

  1. from math import *
  2.  
  3.  
  4. def distance(P,Q):
  5.         return hypot(Q[0]-P[0],Q[1]-P[1])

Télécharger

2. Ce script permet d’obtenir la distance minimale en

  • établissant la liste des distances non nulles entre deux points du nuage ;
  • triant cette liste dans l’ordre croissant ;
  • lisant le premier terme de la liste triée : C’est forcément le minimum :
  1. def distance_minimale(L):
  2.         ds = [distance(p,q) for p in L for q in L if distance(p,q)>0]
  3.         ds.sort()
  4.         return ds[0]

Télécharger

Fini de rire, charmante Elvire

En fait, le but de cette partie de l’exercice était d’évaluer la complexité de certains algorithmes et à moins de savoir quel est l’algorithme de tri utilisé par Python, on est coincé avec cette version.

a. En fait, la variable j n’étant jamais réinitialisée, on ne fait que n calculs de distance, plus l’initialisation de la variable minimum, soit n+1 calculs de distance en tout. Cette variante du script de l’énoncé permet de le vérifier :

  1. def distance_minimale(L):
  2.         c = 0
  3.         n = len(L)
  4.         c += 1
  5.         minimum = distance(L[0],L[1])
  6.         i, j = 0, 0
  7.         while i<n :
  8.                 while j<n :
  9.                         c += 1
  10.                         a = distance(L[i],L[j])
  11.                         if a<minimum :
  12.                                 minimum = a
  13.                         j += 1
  14.                 i += 1
  15.         print c, "appels"
  16.         return minimum

Télécharger

b. La valeur renvoyée par cette fonction est 0.0 (le flottant 0), parce que la distance minimale entre deux points quelconques du nuage est toujours 0, distance atteinte lorsqu’on prend deux fois le même point.

c. La version corrigée du script est celle-ci :

  1. def distance_minimale(L):
  2.         n = len(L)
  3.         minimum = distance(L[0],L[1])
  4.         i= 0
  5.         while i<n :
  6.                 j = 0
  7.                 while j<i :
  8.                         c += 1
  9.                         a = distance(L[i],L[j])
  10.                         if a<minimum :
  11.                                 minimum = a
  12.                         j += 1
  13.                 i += 1
  14.         return minimum

Télécharger

3. Pour avoir la distance maximale, on peut faire ainsi :

  1. def distance_maximale(L):
  2.         ds = [distance(p,q) for p in L for q in L if distance(p,q)>0]
  3.         ds.sort()
  4.         return ds[len(ds)-1]

Télécharger

Trop de distances !

La liste crée ci-dessus par compréhension est de longueur n(n-1) alors que l’énoncé ne demandait que la moitié. L’algorithme proposé n’est donc pas conforme à l’énoncé. Celui-ci l’est :

  1. def distance_maximale(L):
  2.         n = len(L)
  3.         maximum = 0.0
  4.         i= 0
  5.         while i<n :
  6.                 j = 0
  7.                 while j<i :
  8.                         a = distance(L[i],L[j])
  9.                         if a>maximum :
  10.                                 maximum = a
  11.                         j += 1
  12.                 i += 1
  13.         return maximum

Télécharger

CoffeeScript

Avec le tri de JavaScript, il suffit

  • de faire la liste des distances mutuelles des points, en aplatissant une liste de listes avec « flatten »
  • d’enlever les 0 de cette liste avec « without »
  • de trier les distances dans l’ordre croissant avec « sort »
  • de lire le premier élément (distance minimale) et le dernier élément (distance maximale) de la liste triée :
  1. distance = (p,q) ->
  2.     ($V p).distanceFrom($V q)
  3.  
  4.  
  5. dmM = (n) ->
  6.     ds = _.flatten(distance(p,q) pour p dans n pour q dans n)
  7.     ds = _.without ds, 0
  8.     ds.sort()
  9.     [ds[0],ds[ds.length-1]]
  10.  
  11.  
  12. distance_minimale = (n) ->
  13.     dmM(n)[0]
  14.  
  15. distance_maximale = (n) ->
  16.     dmM(n)[1]

Télécharger

à gauche toute !

La fonction donnant l’indice du point d’abcisse minimale peut ressembler à ceci :

  1. def point_abs_min(L):
  2.         indice= 0
  3.         i = 1
  4.         minx = L[0][0]
  5.         miny = L[0][1]
  6.         while i<len(L) :
  7.                 if L[i][0]<minx:
  8.                         minx = L[i][0]
  9.                         indice = i
  10.                 if L[i][0] == minx:
  11.                         if L[i][1]<miny:
  12.                                 miny = L[i][1]
  13.                                 indice = i
  14.                 i += 1
  15.         return indice

Télécharger

Cet algorithme est en O(n) puisqu’il n’y a qu’une boucle et qu’elle n’est parcourue qu’une fois.

CoffeeScript

Et voici la version underscore+CoffeeScript :

  1. point_abs_min = (n) ->
  2.     as = (p[0] pour p dans n)
  3.     as.sort()
  4.     _.indexOf (p[0]==as[0] pour p dans n), true

Télécharger

Orientation

5. Si (P,Q,R) est en orientation directe, (Q,R,P) l’est aussi et (P,R,Q) ne l’est pas. On peut justifier cela à l’aide des propriétés du déterminant ou par les permutations : (Q,R,P) est une permutation paire (un cycle) donc ne change pas le signe du déterminant, et (P,R,Q) est une permutation impaire.

6. Avec le module turtle on a une conversion en vecteurs (via une conversion en tuple) qui permet de raccourcir le code :

  1. from turtle import *
  2. def vecteur(A,B):
  3.         a = Vec2D(*tuple(A))
  4.         b = Vec2D(*tuple(B))
  5.         return b-a
  6.  
  7. def orientation(P,Q,R):
  8.         u = vecteur(P,Q)
  9.         v = vecteur(P,R)
  10.         d = u[0]*v[1]-v[0]*u[1]
  11.         if d>=0 :
  12.                 return 1
  13.         else :
  14.                 return -1

Télécharger

CoffeeScript

On

  • calcule les deux vecteurs u et v ;
  • fabrique une matrice M ayant u et v comme colonnes ;
  • calcule le déterminant d de cette matrice ;
  • renvoie le « signe » de ce déterminant.
  1. orientation = (P,Q,R) ->
  2.     u = Q.subtract P
  3.     v = R.subtract P
  4.     M = ($M u).augment v
  5.     d = M.determinant()
  6.     d/abs(d)

Télécharger

Tri

7. Voici l’algorithme de tri à bulle proposé dans le sujet :

  1. def tri_bulle(L):
  2.         n = len(L)
  3.         for i in range(n):
  4.                 for j in range(n-1,i,-1):
  5.                         if L[j]<L[j-1]:
  6.                                 L[j],L[j-1] = L[j-1],L[j]

Télécharger

a. Avec la liste L proposée dans le sujet, les états successifs de L sont donnés ici :

[5, 2, 3, 1, 4]
[1, 5, 2, 3, 4]
[1, 2, 5, 3, 4]
[1, 2, 3, 5, 4]
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]

b. La propriété « Après k itérations, les k premiers éléments sont dans l’ordre croissant et inférieurs aux autres éléments » se démontre par récurrence sur k. En appliquant cette propriété à k=n, on démontre que après n itérations, la liste est triée.

c. Dans le meilleur cas, la liste est déjà triée et aucun échange n’est fait. La complexité se mesure alors au nombre de comparaisons, et est proportionnelle au nombre de passages dans la boucle interne. Ce nombre est (n-1)+(n-2)+...+3+2+1=n(n-1)/2 : Complexité en O(n²). Dans le pire cas, la liste est triée dans l’ordre décroissant, et n(n-1)/2 affectations simultanées seront faites : Là encore, la complexité est en O(n²).

8. La fonction fusion est celle-ci :

  1. def fusion(L1,L2):
  2.         if len(L1) == 0 :
  3.                 return L2
  4.         elif len(L2) == 0 :
  5.                 return L1
  6.         else:
  7.                 if L1[0]<=L2[0] :
  8.                         return [L1[0]]+fusion(L1[1:],L2)
  9.                 else:
  10.                         return [L2[0]]+fusion(L1,L2[1:])

Télécharger

a. On s’en sert pour la fonction tri_fusion :

  1. def tri_fusion(L):
  2.         n = len(L)
  3.         if n<=1 :
  4.                 return L
  5.         else:
  6.                 m = n//2
  7.         return fusion(tri_fusion(L[0:m]), tri_fusion(L[m:n]))

Télécharger

b. La fonction tri_fusion se termine parce qu’à chaque appel récursif, la longueur des listes à fusionner est divisée par 2.

c. Si n=2p, à chaque appel récursif, les listes à fusionner sont de longueur moitié de la longueur à l’étape précédente, donc de la forme 2k. La complexité de la fusion des listes est alors en O(2k+2k) soit en O(2k+1). Ce qui permet de démontrer par récurrence sur p que, tant dans le meilleur cas que dans le pire cas, la complexité est en O(p×2p).

CoffeeScript

Comme pour la version Python, le tri par bulles se fait in situ :

  1. tri_bulle = (L) ->
  2.     n = L.length
  3.     pour i  dans [0...n]
  4.         pour j dans [n-1...i] by -1
  5.             si L[j]<L[j-1]
  6.                 [L[j],L[j-1]] = [L[j-1],L[j]]

Télécharger

Comme pour la version Python, le tri fusion est une fonction retournant la liste triée :

  1. fusion = (L1,L2) ->
  2.     si L1.length==0
  3.         L2
  4.     sinon
  5.         si L2.length==0
  6.             L1
  7.         sinon
  8.             si L1[0]<=L2[0]
  9.                 [L1[0]].concat fusion(L1[1...L1.length],L2)
  10.             sinon
  11.                 [L2[0]].concat fusion(L1,L2[1...L2.length])
  12.  
  13. tri_fusion = (L) ->
  14.     n = L.length
  15.     si n<=1
  16.         L
  17.     sinon
  18.         m = troncature n/2
  19.         fusion tri_fusion(L[0...m]), tri_fusion(L[m...n])

Télécharger

Jarvis

9. Voici la fonction « naïve » :

  1. def jarvis(L):
  2.         n=len(L)
  3.         EnvConvexe=[]
  4.         for i in range (n) :
  5.                 for j in range (n) :
  6.                         Listeorientation=[]
  7.                         if i!= j :
  8.                                 for k in range (n) :
  9.                                         if k!= i and k!= j :
  10.                                                 Listeorientation.append(orientation(L[i],L[j],L[k]))
  11.                                 a=Listeorientation[0]
  12.                                 sommet=True
  13.                                 for v in Listeorientation:
  14.                                         if (v!=a):
  15.                                                 sommet=False
  16.                                 if sommet and (i not in EnvConvexe) :
  17.                                         EnvConvexe.append(i)
  18.                                 if sommet and (j not in EnvConvexe):
  19.                                         EnvConvexe.append(j)
  20.         return EnvConvexe

Télécharger

a. La variable sommet est initialisée à True parce qu’on suppose que le point d’indice k est un sommet de l’enveloppe convexe. On parcourt, dans la boucle sur v, les orientations des points du nuage, à la recherche d’un point qui infirmerait cette hypothèse. Si on en trouve un, la variable sommet est positionnée à False puisqu’il suffit d’un contre-exemple pour infirmer l’hypothèse.

b. La double boucle sur i et j donne lieu à n² tests d’égalité entre i et j. La boucle sur k est donc parcourue n²-1 fois et k est affecté n(n²-1)=n³-n fois. Comme i est différent de j, la fonction append est donc appelée n³-n-2 fois. Ensuite on parcourt n²-n fois la liste des orientations, laquelle est de taille n-2. La fonction append est donc encore appelée, au maximum, (n²-n)(n-2)=n³-3n²+2n fois. En tout elle est donc exécutée n³-3n²+n-2 fois, et la complexité de l’algorithme est en O(n³).

c. Le script suivant trace bien un polygone puisque ses arguments sont une liste d’abscisses et une liste d’ordonnées. Mais si ce polygone passe bien par les sommets de l’enveloppe convexe,

  • d’une part il n’est pas fermé puisque les coordonnées de son dernier point ne sont pas les mêmes que celle du premier point ;
  • d’autre part les points ne sont pas parcourus dans l’ordre qui aurait fait de ses côtés, ceux de l’enveloppe convexe.

Les deux défauts sont apparents sur ce nuage de points gaussiens :

Voici le script en question :

  1. import matplotlib.pyplot as plt
  2. Enveloppe = jarvis(L)
  3. plt.plot([L[i][0] for i in Enveloppe], [L[i][1] for i in Enveloppe])
  4. plt.show()

Télécharger

Qu’attend-on des candidats ?

Le seul module cité dans l’annexe et le sujet est le module math :

  • On n’attendait donc pas des candidats qu’ils se simplifient la vie sur les vecteurs, avec la tortue ;
  • on n’attendait pas non plus des cadidats qu’ils se simplifient la vie chaque fois qu’il y a des matrices (c’est-à-dire quasiment tout le temps) en utilisant le module de calcul matriciel numpy ;
  • Mais sans prévenir, tout d’un coup, on pose une question sur le graphique permis par matplotlib qui est issu de numpy : Comment un candidat qui n’avait pas utilisé régulièrement matplotlib pouvait-il se souvenir de sa syntaxe par écrit ?

Peut-être considère-t-on que matplotlib fait partie de la version officielle de Python « spécial Capes » mais dans ce cas, n’était-il pas intéressant, pédagogiquement (et surtout qu’il s’agit quand même du Capes de mathématiques), de former les candidats à l’utilisation des modules turtle, fractions, complex ?

Si matplotlib doit faire partie de la panoplie de tout candidat au Capes, pour la bonne et simple raison qu’il permet de faire des dessins, c’est tout le choix de Python qui devient critiquable, puisque alcoffeethmique est doté de possibilités graphiques plus accessibles de par une concision accrue.

CoffeeScript

La version CoffeeScript de l’algorithme de Jarvis, avec les ensembles d’alcoffeethmique [2] :

  1. jarvis = (L) ->
  2.     n=L.length
  3.     EnvConvexe = nouvel Ensemble []
  4.     pour i dans [0...n]
  5.         pour j dans [0...n]
  6.             Ensorientation = nouvel Ensemble []
  7.             si i!=j
  8.                 pour k dans [0...n]
  9.                     si k!=i et k!=j
  10.                         Ensorientation.ajoute orientation(L[i],L[j],L[k])
  11.                 sommet = (Ensorientation.cardinal()==1)
  12.                 si sommet
  13.                     EnvConvexe.ajoute i
  14.                     EnvConvexe.ajoute j
  15.     EnvConvexe.support

Télécharger

La partie graphique se fait en

  • fabriquant, avec la fonction jarvis, le tableau nS contenant les indices des sommets ;
  • créant une liste ec (comme « enveloppe convexe ») de points, initialement vide ;
  • rajoutant au fur et à mesure, les points du nuage dont l’indice est celui d’un sommet (en bref, les sommets...)
  • rajoutant à la fin le premier de ces sommets pour que le polygone soit fermé ;
  • dessinant le polygone, en rouge, sans remplissage :
  1. nS = jarvis nuage
  2. ec = []
  3. pour p dans nS
  4.     ec.empile nuage[p]
  5. ec.empile nuage[nS[0]]
  6. dessinePolygone ec, 'red', 'none'

Télécharger

Cela produit ce genre de dessin, avec un nuage gaussien :

Jarvis 2

10. Sur la figure de l’énoncé, l’ordre des points par rapport au point 6 est : 0,4,1,7,2,5,8,3.

11. La fonction donnant l’indice du prochain sommet de l’enveloppe convexe dans le nuage de points est celle-ci :

  1. def prochain_sommet(L,p):
  2.         q = EJ[0]
  3.         if q==p:
  4.                 q=EJ[1]
  5.         for k in EJ:
  6.                 if k!=p and k!=q and orientation(L[p],L[k],L[q])>0:
  7.                         q = k
  8.         return q

Télécharger

Pour aller plus vite, on a stocké dans la variable EJ la liste des points de l’enveloppe convexe donnée par l’algorithme de Jarvis.

12. La fonction de l’énoncé donnant l’enveloppe convexe à l’aide de la fonction précédente, une fois complétée, ressemble à ceci :

  1. def jarvis2(L):
  2.         i = point_abs_min(L)
  3.         suivant = prochain_sommet(L,i)
  4.         Enveloppe = [i,suivant]
  5.         while (suivant != i):
  6.                 suivant = prochain_sommet(L,suivant)
  7.                 Enveloppe.append(suivant)
  8.         return Enveloppe

Télécharger

Elle donne ce genre de dessin :

CoffeeScript

Voici la version alcoffeethmique :

  1. prochain_sommet = (L,p) ->
  2.     q = nS[0]
  3.     si q==p
  4.         q=nS[1]
  5.     pour k dans nS
  6.         si k!=p et orientation(L[p],L[k],L[q])>0
  7.             q=k
  8.     q
  9.  
  10. jarvis2 = (L) ->
  11.     i = point_abs_min(L)
  12.     suivant = prochain_sommet(L,i)
  13.     Enveloppe = [i,suivant]
  14.     jusqu'à ce que suivant==i
  15.        suivant = prochain_sommet(L,suivant)
  16.        Enveloppe.empile suivant
  17.    Enveloppe

Télécharger

Laliste nS est celle qui contient les numéros des sommets de l’enveloppe convexe, dans l’ordre donné par l’algorithme de Jarvis.

Voici ce que ça donne sur un nuage de points gaussiens :

Graham-Andrew

14. La fonction en Python sans le tri initial :

  1. def graham_andrew(L):
  2.         EnvSup=[]
  3.         EnvInf=[]
  4.         for i in range(len(L)):
  5.                 while len(EnvSup)>=2 and orientation(L[i],L[EnvSup[-1]],L[EnvSup[-2]]) <= 0 :
  6.                         EnvSup.pop()
  7.                 EnvSup.append(i)
  8.                 while len(EnvInf)>=2 and orientation(L[EnvInf[-2]],L[EnvInf[-1]],L[i]) <= 0 :
  9.                         EnvInf.pop()
  10.                 EnvInf.append(i)
  11.         return EnvInf[:-1]+EnvSup[::-1]

Télécharger

En effet le tri est fait en place avec

nuage.sort(key=lambda p: p[0])

Voici l’effet de cette fonction sur un nuage gaussien :

a. Comme il y a 8 points, i prend successivement les valeurs 0 à 7.

i EnvSup orientation négative
0 0 -
1 0,7 oui
2 0,1 oui
3 0,4 oui
4 0,6 non
5 0,6,5 oui
6 0,6,3 non
7 0,6,3,8 -

b. Les instructions append sont effectuées chacune une seule fois dans la boucle, et prennent donc un temps fini ; quant aux instructions pop, elles n’enlèvent que des points qui avaient été placés auparavant et ce n’est jamais un de ces points qui est ajouté après. Il n’y a donc pas de boucle sans fin dans ce programme.

c. La boucle sur i est effectuée n fois. Dans cette boucle il y a un nombre indéterminé de réductions de la liste EnvSup, mais le nombre total de ces réductions ne peut être supérieur à n parce qu’on ne peut pas vider une liste vide. Par conséquent le nombre d’opérations dans la boucle est majoré par 2n (en fait, 2n-2 parce que les réductions ne se font pas sur une liste de taille inférieure à 2). Il en est de même pour la boucle sur EnvInf : Après le tri du nuage de points, la suite est en O(n). Mais comme le tri est lui-même en O(n log(n)), c’est l’opération de tri qui est la plus longue dans cet algorithme, qui est donc aussi en O(n log(n)).

CoffeeScript

Voici la version alcoffeethmique de l’algorithme :

  1. graham_andrew = (L) ->
  2.     EnvSup = []
  3.     EnvInf = []
  4.     pour i dans [0...L.length]
  5.         tant que EnvSup.length >= 2 et orientation(L[i],L[EnvSup.slice(-1)],L[EnvSup.slice(-2)[0]])<=0
  6.             EnvSup.pop()
  7.         EnvSup.empile i
  8.         tant que EnvInf.length >= 2 et orientation(L[EnvInf.slice(-2)[0]],L[EnvInf.slice(-1)],L[i])<=0
  9.             EnvInf.pop()
  10.         EnvInf.empile i
  11.     EnvInf.pop()
  12.     EnvSup.reverse()
  13.     EnvInf.empile i pour i dans EnvSup
  14.     EnvInf

Télécharger

Le tri de la liste de points a été fait en place :

nuage.sort (p,q)->p[0]-q[0]

Ce qui a donné en moins d’une seconde ce dessin :


[1source : académie d’Angers.

[2Python aussi a des ensembles, mais il faut croire que la programmation objet de matplotlib est plus importante, en maths, que les ensembles...


Commentaires

Logo de Passant
lundi 2 avril 2018 à 07h45 - par  Passant

Une véritable perle ce corrigé dans l’océan du net.
Pour information, Problème 2, Partie B, Question 14a, 9 vecteurs au total