partiels/130311S3_tp/main.tex

   1 \documentclass[11pt,a4paper,french]{article}
   2 \usepackage[francais]{babel}
   3 \usepackage[utf8]{inputenc}
   4 \usepackage{a4}
   5 \usepackage{amsmath}
   6 \usepackage{amsfonts}
   7 \usepackage{amssymb}
   8 \usepackage{framed}
   9 \usepackage{dsfont}
  10 \usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
  11 \usepackage[dvips]{graphics}
  12 \usepackage{epsfig}
  13 \usepackage{calc}
  14 \usepackage{tabls}
  15 %\usepackage{slashbox}
  16 \usepackage{times}
  17 \usepackage{multicol}
  18 \usepackage{skak,chessboard}
  19 \usepackage{textcomp}
  20 \usepackage{pst-all}
  21 \usepackage[a4paper]{geometry}
  22
  23 \geometry{hmargin=1cm, tmargin=1cm,bmargin=1.5cm}
  24 \title{Département d'informatique, partiel de Mathématiques discrètes.\\
  25 Semestre 3, mars 2013, durée 30 min, J.-F. Couchot.}
  26
  27 \date{}
  28
  29 \begin{document}
  30 \maketitle
  31 \vspace{-5em}
  32 \begin{tabular}{ll}
  33 Nom:& ........................................\\
  34 Prénom:& ........................................\\
  35 \end{tabular}
  36
  37 Seuls les codes développés en TP sont autorisés.
  38 Vos réponses seront données directement ci-dessous en python.
  39
  40
  41 \section*{Échange de cavaliers au jeu d'échec}
  42
  43 Sur un échiquier 3x3, les deux cavaliers noirs sont placés sur les cases a1 et c1, les deux cavaliers blancs occupant les cases a3 et c3, comme représenté
  44 ci-dessous.
  45 \begin{center}
  46   \def\mylist{Na3,Nc3,na1,nc1}
  47   \setchessboard{
  48   maxfield=c3,
  49   setpieces=\mylist
  50 }
  51 \chessboard
  52 \end{center}
  53
  54 L'objectif est de déterminer les mouvements qui autoriseront les
  55 cavaliers blancs à prendre les places des cavaliers noirs, et vice versa.
  56
  57 Pour rappel, un cavalier se déplace en ``L'': par exemple le cavalier noir,
  58 en a1, peut se rendre soit en c2, soit en b3.
  59
  60 Comme il y a neuf cases sur le plateau, l'état du
  61 jeu est mémorisé à l'aide d'un 9-uplet
  62 $$
  63 (x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8)
  64 $$
  65 où
  66 $x_0$ mémorise ce qu'il y a sur la case a1,
  67 $x_1$ mémorise ce qu'il y a sur la case a2, \ldots,
  68 $x_8$ mémorise ce qu'il y a sur la case c3.
  69 Un case $x_i$ est soit vide, soit avec un cavalier noir, soit avec un
  70 cavalier blanc. On mémorise ceci en affectant à $x_i$
  71 soit la valeur 'v' (pour vide),
  72 soit la valeur 'n' (pour cavalier noir) ou
  73 soit la valeur 'b' (pour cavalier blanc).
  74
  75
  76
  77 \begin{enumerate}
  78 \item Donner le 9-uplet \verb+initial+
  79   qui représente l'état initial du jeu selon ce codage.
  80   Donner le 9-uplet \verb+final+
  81   qui représente l'état final du jeu selon ce codage.
  82
  83 \vspace{2cm}
  84 \item Donner le code de la fonction \verb+nbre(u,c)+ qui reçoit en paramètres
  85   un $n$-uplet \verb+u+ et un caractère \verb+c+ et qui retourne le nombre
  86   d'occurrences de ce caractère dans \verb+u+. Par exemple
  87   \verb+nbre(initial,'b')+ vaut 2 et  \verb+nbre(initial,'v')+ vaut 5.
  88 \vspace{3cm}
  89
  90 \item Si l'on construisait tous les plateaux de jeu 3x3 sans tenir compte
  91   du nombre de cavaliers, combien en aurait-on? Justifier.
  92  \vspace{3cm}
  93 \item Donner le code qui initialise la liste de plateaux,
  94   nommée \verb+plateaux+,
  95   avec tous les plateaux possibles, mais en tenant compte du fait qu'il
  96   y a toujours deux cavaliers noirs et deux cavaliers blancs sur chaque
  97   plateau.
  98  \vspace{5cm}
  99 \item Commenter le code suivant (à sa droite)
 100   en détaillant la nature des paramètres,
 101   ce qui est retourné, et pourquoi cette valeur?
 102 \begin{scriptsize}
 103 \begin{verbatim}
 104 def deplacement(co,ce):
 105       r=[[5,7],
 106          [6,8],
 107          [3,7],
 108          [2,8],
 109          [],
 110          [0,6],
 111          [1,5],
 112          [0,2],
 113          [1,3]]
 114       return ce in r[co]
 115 \end{verbatim}
 116 \end{scriptsize}
 117 \item Donner le code de la fonction  \verb+deplacement_ok(p1,p2)+
 118   qui retourne vrai si l'on peut passer du plateau
 119 \verb+p1+ au plateau \verb+p2+.
 120 \vspace{6cm}
 121
 122 \item Donner le code manquant
 123   qui permet de résoudre le problème en utilisant
 124   \verb+networkx+.
 125
 126 \end{enumerate}
 127
 128 \end{document}
 129