Sujet zéro capes option informatique 2017

Le début est du Scratch tout scratché...(ou la Tortue Logo des années 80 sur MO5)

Merci bisam.

As-tu donné une partie de l'épreuve à tes étudiants ?

En relisant les textes officiels, il me semble qu'il n'y a nulle part dans le concours de partie pratique de programmation qui soit impose : ecrit theorique (sujet 0 sans calculatrices!), oral 1 de type lecon. Autrement dit l'aspect verification et mise au point semble etre le grand oublie.

Bonjour,

Je me prépare pour le CAPES 2017 et je fais les choses un peu dans le désordre. Je travaille sur le programme des collèges et je fais des annales de temps en temps.
J'ai donc voulu regarder ce fameux sujet 0 (ayant une base informatique, ça ne peut pas me faire de mal).
Je ne connais pas Python, mais ce n'est pas le problème. Juste que je me suis levée à 4h00 ce matin alors niveau concentration c'est moyen, et du coup j'ai du mal à m'imprégner du sujet.
bisam j'ai ton corrigé sous les yeux, j'en suis qu'au début et c'est super. J'accroche totalement.
Merci pour ce travail.

Est-ce que c'est un niveau demandé au niveau lycée?

Globalement, le sujet me semble tout de même « facile mais pas trop ». La difficulté principale c'est d'avoir un niveau de brainpower constant qui te permette de terminer l'épreuve dans de bonnes conditions.

Bonjour,
je sais que le capes est dans 3 jours mais ton code pour la question A.15(version pyplot) ne fonctionne pas.
Essayez ceci.

L=10
A=20
N=5

def dessiner(unite, angle, motif, azimut=0):
    x, y, d= 0, 0, azimut
    lx, ly = [x], [y]
    pile=[]
    for step in motif:
        if step=="F":
            x+=unite*cos(d*pi/180)
            y+=unite*sin(d*pi/180)
            lx.append(x)
            ly.append(y)
        elif step=="+":
            d += angle
        elif step == "-":
            d -= angle
        elif step == "[":
            pile.append((x, y, d))        
        elif step == "]":
            (x, y, d)=pile.pop()
            lx.append(x)
            ly.append(y)
        else: 
            return 1
        #i+=1

    plot(lx, ly, "k-")
    show()
    return None
           
dessiner(L,A,evolution("F","F[+F]F[-F]F",N),90)

[Du python sans indentation, ce n'est pas top ! AD]

Oui étrange, pourtant avec ton code je me suis retrouvé avec tout sauf une plante. Ça ressemblait plutôt à une courbe de la bourse.
Si ça t'intéresse, j'ai passé le capes ce matin (maths option info). Ce soir je n'ai pas le temps de scanner les 13 pages, mais je le fais bientôt. J'ai séché sur une fonction de récurrence. Je suis sûr que tu pourras m'éclairer.
Le problème 1 portait sur la résolution d'un jeu de sudoku. 2 méthodes de résolutions abordées dont une en backtracking (celle sur laquelle je sèche).

""" question 13
objectif: compléter la grille de sudoku en testantv les combinaisons en commencant par la première case et jusqu'à la dernière. si on obtient un conflit avec les règles, on est obligé de revenir en arrière.
ordre lexicographique: (0,0), (0,1)... '0,8),(1,0),...(8,0), ...(8,8),(9,0) [END]

def case_suivante(pos):
    i,j = pos[0], pos[1]
    if j<8:
        return [i,j+1]
    elif j==8:
        if i<8:
            return [i+1,0]
        else: return [9,0]

#backtracking
#renvoie true s'il est possible de compéter la grille à partir des hypothèses faites sur les cases qui précèdent la case pos, et false dans le cas contraire.
# si pos=[9,0] => true
# si la case est déjà remplie, on passe à la case suivante via recursivité
#sinon on affecte un des chiffres possibles à la case, et on passe à la suivante

""" voilà mon code qui ne fonctionne pas
je ne sais même pas vraiment si je peux ou dois utiliser les fonctions faites avant, ce n'est pas clair dans l'énoncé

def backtracking(L, pos):
    if pos==[9,0]:
        return True
    i,j = pos[0], pos[1]
    if L[ i][j] != 0:
        return backtracking(L,case_suivante(pos))
    for k in range(1,10):
        L[ i][j] = k
        if L[ i][j] not in conflit(L,i,j):
            #print(L)
            return backtracking(L,case_suivante(pos))
        #print(L)
    L[ i][j] = 0 #débile!!
    return False

def solution_sudoku(L):
    return backtracking(L,[0,0])

[À quoi sert d'écrire du python sans indentation :-S ! AD]

Le probleme c'est qu'il est difficile de reellement tester cet algorithme, sauf a lui fournir une grille quasi-complete pour laquelle l'algorithme naif de remplissage est sans doute bien plus pertinent!

Un algorithme de resolution moins naif va initialiser dans chaque case non remplie les possibilites, puis les barrer en fonction des cases remplies, s'il ne reste qu'une possibilite sur une case on la remplit et on continue. Lorsqu'on ne peut plus rien remplir, on fait une hypothese sur la case qui a le moins de possibilites et on appelle recursivement l'algorithme de resolution, si ca marche c'est fini, sinon on continue dans les hypotheses.
Pour stocker les possibilites d'une case de maniere efficace, on peut utiliser la decomposition en base 2 d'un entier.
Voila un exemple de grille

0 0 0 0 0 6 0 0 0
0 5 9 0 0 0 0 0 8
2 0 0 0 0 8 0 0 0
0 4 5 0 0 0 0 0 0
0 0 3 0 0 0 0 0 0
0 0 6 0 0 3 0 5 4
0 0 0 3 2 5 0 0 6
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 

et une implementation en C++ relativement efficace:

// -*- mode:c++; compile-command:"/usr/bin/g++ -g sudoku.cc" -*-
// pour profiler option -pg puis ./a.out hard1 puis gprof ./a.out gmon.out > log
#include <iostream>
#include <fstream>
#include <stdlib.h> // pour exit

using namespace std;

struct val;
ostream & operator << (ostream & os,const val &); // predeclaration
struct grille;
ostream & operator << (ostream & os,const grille &); // predeclaration

struct val {
  unsigned short possibilites:8;
  unsigned short valeur:8; // 0 si inconnu, sinon valeur
  unsigned short x; // champ de 9 bits (bits 1 a 9) indiquant valeur possible
  val(){ // constructeur de case inconnue
    x=(1<<1)|(1<<2)|(1<<3)|(1<<4)|(1<<5)|(1<<6)|(1<<7)|(1<<8)|(1<<9);
    valeur=0;
    possibilites=9;
  }
  val(unsigned i){ // constructeur de case connue
    x=1<<i;
    valeur=i;
    possibilites=1;
  }
  // efface i, renvoie -1 si erreur, 0 si deja enleve,
  // sinon le nombre de possibilites restante
  int remove(unsigned i){
    unsigned bitmask=(1<<i);
    if (!(x&bitmask))
      return 0;
    if (valeur) return -1; // incompatible
    x ^= bitmask;
    --possibilites;
    if (possibilites!=1) return possibilites?possibilites:-1;
    switch(x){
    case 1<<1: valeur=1; return 1;
    case 4: valeur=2; return 1;
    case 8: valeur=3; return 1;
    case 16: valeur=4; return 1;
    case 32: valeur=5; return 1;
    case 64: valeur=6; return 1;
    case 128: valeur=7; return 1;
    case 256: valeur=8; return 1;
    case 512: valeur=9; return 1;
    }
    return -1;
  }
  void dbgprint() const { cout << *this << endl; } // pour pouvoir debugguer
};

ostream & operator << (ostream & os,const val & v){
  for (int i=1;i<=9;++i){
    if (v.x & (1<<i)) os << i; else os << "-";
  }
  return os;
}

struct grille {
  val tab[81];
  int status; // 0 initial, 1 en cours, 2 solved
  inline val & operator () (int i,int j)  {
    return tab[i*9+j];
  }
  inline val operator () (int i,int j) const {
    return tab[i*9+j];
  }
  bool update(int i,int j); // met a jour la grille en tenant compte de (i,j)
  // remplissage initial de la grille depuis un fichier
  grille(const char * filename){
    status=0;
    ifstream i(filename);
    if (!i) exit(1);
    for (int pos=0;pos<81;++pos){
      unsigned tmp;
      i>>tmp;
      if (tmp)
	tab[pos]=val(tmp);
      else
	tab[pos]=val();
    }
  }
  bool solve(bool updatefirst); 
  void dbgprint() const { cout << *this << endl; }
};

ostream & operator << (ostream & os,const grille & v){
  for (int i=0;i<9;++i){
    for (int j=0;j<9;++j){
      if (v.status!=1)
	os << v(i,j).valeur << " " ;
      else
	os << v(i,j) << " ";
    }
    os << endl;
  }
  return os;
}

bool grille::update(int i,int j){
  int t=(*this)(i,j).valeur;
  if (!t) return true; // valeur inconnue
  // efface t des valeurs possibles de la ligne/colonne/sous-matrice
  for (int J=0;J<9;++J){
    if (J==j) continue;
    int status=(*this)(i,J).remove(t);
    if (status==-1) 
      return false; // incompatibilite
    if (status==1){ // la case i,J vient d'etre trouvee on met a jour recursivement
      if (!update(i,J)) 
	return false;
    }
  }
  for (int I=0;I<9;++I){
    if (I==i) continue;
    int status=(*this)(I,j).remove(t);
    if (status==-1) 
      return false;
    if (status==1){
      if (!update(I,j)) 
	return false;
    }
  }
  int r=(i/3)*3,c=(j/3)*3;
  for (int a=0;a<3;a++){
    int I=r+a;
    if (I==i) continue;
    for (int b=0;b<3;b++){
      int J=c+b;
      if (J==j) continue;
      int status=(*this)(I,J).remove(t);
      if (status==-1) 
	return false;
      if (status==1){
	if (!update(I,J)) 
	  return false;
      }
    }
  }
  return true;
}

// compte le produit des nombres de possibilites sur une case
double liens(const grille & g,int i,int j){
  double l=1;
  for (int I=0;I<9;++I){
    l*=g(I,j).possibilites;
  }
  for (int J=0;J<9;++J){
    //if (j!=J)
      l*=g(i,J).possibilites;
  }
  int r=(i/3)*3, c=(j/3)*3;
  for (int I=0;I<3;++I){
    //if (r+I==i) continue;
    for (int J=0;J<3;++J){
      //if (c+J!=j)
	l*=g(I,J).possibilites;
    }
  }
  return l;
}

bool grille::solve(bool updatefirst){
  if (updatefirst){
    for (int i=0;i<9;++i){
      for (int j=0;j<9;++j)
	if (!update(i,j)) return false;
    }
    status=1;
  }
  while (1){
    // fini?
    int i,j;
    for (i=0;i<9;i++){
      for (j=0;j<9;j++){
	if ((*this)(i,j).valeur==0)
	  break;
      }
      if (j!=9)
	break;
    }
    if (i==9){ status=2; return true; }
    // methode "naive"
    // recherche d'une case inconnue avec le moins de possibites
    int npos=(*this)(i,j).possibilites,ipos=i,jpos=j; double nlink=liens(*this,i,j);
    for (i=ipos;i<9;i++){
      for (j=0;j<9;j++){
	int curpos=(*this)(i,j).possibilites;
	if (curpos<=1 || curpos>npos) continue;
	double curlink=liens(*this,ipos,jpos);
	if (curpos<npos){
	  ipos=i; jpos=j; npos=curpos; nlink=curlink; continue;
	}
	if (curlink<nlink) {
	  ipos=i; jpos=j; npos=curpos; nlink=curlink; continue;	  
	}
      }
    }
    // creation d'une copie de la grille ou on affecte une des valeurs possibles
    // puis si la resolution marche on a fini
    int x=(*this)(ipos,jpos).x;
    for (int k=1;k<=9;++k){
      if (x & (1<<k)){
	grille copie=*this;
	copie(ipos,jpos)=val(k);
	if (!copie.update(ipos,jpos)) continue;
	if (copie.solve(false)){ *this=copie; return true; }
      }
    }
    return false;
  }
  return false; // jamais atteint
}

int main(int argc,const char ** argv){
  if (argc==1){
    cerr << "Syntaxe: " << argv[0] << " nom_de_fichier_sudoku" << endl;
    return 1;
  }
  grille g(argv[1]);
  if (argc>2){ g.dbgprint(); g(0,0).dbgprint();} // instanciation pour debug
  cout << "Grille initiale"<<endl<<g;
  if (!g.solve(true))
    cout << "Pas de solution!" << endl;
  else
    cout << "Solution trouvee" << endl << g;
  // cout << sizeof(val) << " " << sizeof(grille) << endl;
  return 0;
}

@Couciaci :

python est de plus en plus utilisé dans le supérieur (notamment aux Etats-Unis).
Le fait que ce soit un langage interprété est bien pratique pour débuter ou implémenter rapidement, débuguer, etc.
Pas mal de librairies disponibles aussi ...
et puis syntaxe agréable (dernier argument totalement subjectif).

@parisse :
Il ne faut pas oublier que le cours d'informatique commune des prépas comporte tout de même beaucoup de choses en plus de la programmation en Python.
En particulier, on parle de :
- typage : on fait la distinction entre entiers, réels (flottants), booléens, chaînes de caractères... et types complexes. On parle même du codage machine de certains de ces types (entiers et réels). On est même obligé de parler un peu de programmation objet pour tirer partie de l'écriture dans des fichiers... et par là-même, on doit aussi parler d'encodage des caractères.
- architecture machine : plus exactement, des différents groupes de composants d'un ordinateur, et où on peut en trouver. Les élèves sont souvent étonnés d'apprendre que leur frigo est tout aussi capable de calculer que leur micro-onde ou leur téléphone portable).
- algorithmes de base
- preuves de terminaison
- preuves d'exactitude
- complexité algorithmique temporelle et spatiale. Dans ce cadre, et dans celui des tris en particulier, on peut parler de l'implémentation des listes et des tableaux et faire la distinction entre les deux.
- langages (langage machine, langage interprété, langage compilé)

Bref, la partie programmation n'est pas la plus importante, même si les élèves sont plus souvent interrogés sur cette partie (en fait, plutôt sur l'algorithmie... mais à travers le langage Python qu'ils connaissent).

Par ailleurs, Python n'est PAS le seul langage qu'ils apprennent !
Ils apprennent également quelques bases de Scilab, pour le calcul scientifique, et un peu de SQL également.

Tout cela, en seulement 2h par semaine (TP inclus), pendant 45 semaines.
A titre de comparaison, les programmes d'informatique de 1ère année d'école d'ingénieurs, qui abordaient les mêmes thèmes, duraient entre 100 et 120h.

Certes, les programmes ne sont pas parfaits, mais je ne crois pas que ce soit une raison pour cracher sur Python, qui, somme toute, apporte le confort de la simplicité syntaxique et suffisamment de puissance (et de bibliothèques) pour faire beaucoup de choses.
Ce n'est pas un langage compilé... et alors ? Dans quel cadre des élèves auront-ils besoin du facteur 10 ou 100 qui va être gagné sur la vitesse d'exécution grâce à la compilation ?