\chapter{Programme Pédagogique National 2005 (PPN)}

Voici le contenu de l'Unité de Formation Mathématiques Discrètes (TC-CCG-MATH1) du PPN actuel :

\begin{description}
\item[Volume horaire :] 70 h
\item[Pré-requis :] aucun.
\item[Objectifs :]
\begin{itemize}
\item Connaître le calcul booléen.
\item Calculer dans Z/nZ.
\item Connaître les notions de base en théorie des graphes, des langages et des automates.
\end{itemize}
\item[Compétences minimales :]
\begin{itemize}
\item Mettre en œuvre des schémas de raisonnement (contraposée, absurde, récurrence, etc.).
\item Mettre en œuvre des algorithmes d'arithmétique (Euclide, Bézout, etc.).
\item Faire le lien entre langage usuel et langage formalisé (propositions et prédicats).
\end{itemize}
\item[Contenu :]
\begin{itemize}
\item Vocabulaire de la théorie des ensembles, relations, ensembles ordonnés.
\item Logique : calcul propositionnel et calcul des prédicats.
\item Arithmétique : nombres premiers, division euclidienne, congruences.
\item Éléments de théorie des graphes : graphes orientés et non orientés.
\item Éléments de langages et d'automates.
\end{itemize}
\item[Indications de mise en œuvre :] Exemples d’algorithmes de plus courts chemins, de parcours et d’arbre couvrant de poids minimum.
\item[Prolongements possibles :]
\begin{itemize}
\item Exemples de raisonnement par récurrence (en liaison avec les enseignements d'algorithmique).
\item Développement des liens avec les enseignements d’informatique, en particulier « Architectures, Systèmes et Réseaux » et « Outils et Modèles du Génie logiciel » (algèbre relationnelle, etc.).
\item Chaînage avant et chaînage arrière.
\item Résolution d'équations en nombres entiers.
\item Cryptographie (RSA, méthode du « sac à dos », etc.).
\item Codes correcteurs et codes détecteurs d'erreurs.
\end{itemize}
\end{description}
