\documentclass{tpcaml}

\tp{10}{Dérnière Minute}

\begin{document}

  \maketitle

\section{Algorithmes sur des suites}

\begin{question}
  Calculer la taille d'une liste. Complexité?
\end{question}
\begin{question}
  Trouver la valeur maximale d'une liste. Complexité?
\end{question}
\begin{question}
  Trouver la valeur maximale d'un tableau. Complexité?
\end{question}
\begin{question}
  Trouver si une valeur est présente dans un tableau trié. Complexité?
\end{question}
\begin{question}
  Trouver une sous-chaîne dans une chaîne de caractères. Complexité?
\end{question}

\section{Algorithmes de tri}

\begin{question}
  \'Ecrire le tri à bulles sur les tableaux. Complexité?
\end{question}
\begin{question}
  \'Ecrire le tri par insertion sur les listes. Complexité?
\end{question}
\begin{question}
  \'Ecrire le tri par sélection sur les tableaux. Complexité?
\end{question}
\begin{question}
  \'Ecrire le tri fusion sur les listes. Complexité?
\end{question}
\begin{question}
  \'Ecrire le tri rapide sur les tableaux. Complexité? 
\end{question}

\section{Algorithmes divers}

\begin{question}
  Déterminer si deux chaînes sont des anagrammes l'une de l'autre.
\end{question}
\begin{question}
  Compter les nombres premiers plus petits que 1000.
\end{question}
\begin{question}
  Déterminer si un automate est déterministe et complet sur un alphabet.
\end{question}
\begin{question}
  Déterminer si un arbre binaire de recherche contient des doublons.
\end{question}
\begin{question}
  Déterminer si un tableau représente un tas. Complexité?
\end{question}
\begin{question}
  Déterminer si un texte est un palindrome. 
\end{question}
\begin{question}
  Trouver le plus long préfixe de Dyck d'un mot. 
\end{question}
\begin{question}
  Construire un arbre binaire de recherche à partir d'un tableau trié.
\end{question}
\begin{question}
  Renvoyer la liste des suffixes d'un mot qui en sont également des préfixes.
\end{question}
\begin{question}
  Définir une fonction de type \texttt{'a option -> ('b * 'c) list -> 'd}
\end{question}

\section{Problèmes divers}

\begin{question}
  Prouver formellement la correction du tri par insertion des tableaux.
\end{question}
\begin{question}
  Prouver la correction et la complexité du tri fusion.
\end{question}
\begin{question}
  Construire un automate déterministe qui reconnaît $c\big(a|b|(c^*)\big)^*a(b^*)$.
\end{question}
\begin{question}
  Comment trouver les composantes fortement connexes d'un graphe orienté?
\end{question}
\begin{question}
  Comment choisir une racine qui minimise la profondeur de toutes les branches?
\end{question}
\begin{question}
  Comment trouver le chemin le plus court dans un graphe d'un noeud à un autre?
\end{question}
\begin{question}
  \'Eliminer les états inaccessibles d'un automate quelconque. 
\end{question}
\begin{question}
  Le langage des palindromes sur un alphabet est-il rationnel?
\end{question}
\begin{question}
  Le langage des anagrammes d'un langage rationnel est-il rationnel?
\end{question}
\begin{question}
  Quelle est la probabilité, au poker, de battre un full aux dames par les rois?
\end{question}

 
\end{document}