\documentclass[a4paper,landscape]{slides}
\usepackage[latin1]{inputenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{sfbox}
\let\Color\relax%\usepackage{colordvi}
\usepackage{mycolorslides}
\usepackage[francais]{babel}

\usepackage{hevea}
\ifhtml
\newenvironment{sd}[1]
  {\@open{TABLE}{border width="100%"}\@open{TR}{}\@open{TD}{ALIGN=center}}
  {\@close{TD}\@close{TR}\@close{TABLE}}
\def\linewidth{}
\newenvironment{minipage}[2][XXX]
  {\ifthenelse{\equal{#2}{.45}}
   {\begin{rawhtml}</TD><TD width="50%">\end{rawhtml}}
   {\begin{rawhtml}<TT><B>\end{rawhtml}#2\begin{rawhtml}</B></TT>\end{rawhtml}}}
  {}
\def\substitle#1{\@open{H3}{ALIGN=center}#1\@close{H3}}
\def\SECTION#1{}
\renewenvironment{itemize}
  {\@open{UL}{}\renewcommand{\item}[1][!*!]{\@li}}
  {\@close{UL}}
\fi

\begin{document}
  \title{Algorithmique}
  \author{Louis Granboulan}

\begin{sd}{Plan}
  \substitle{Plan}
  Présentation générale du cours d'algorithmique
  \bigskip\par Principes de programmation impérative
  \bigskip\par Syntaxe du langage C
\end{sd}

\SECTION{Enseignements}

\begin{sd}{Cours : Jacques Stern, cf. plaquette}
  \begin{minipage}[t]{.45\linewidth}
  \substitle{Les cours du lundi}
  \bigskip
  À partir du 9 octobre,
  \\ sauf le 4 décembre (partiel)
  \begin{enumerate}
  \item Machines, algorithmes
  \item Flottants
  \item Entiers
  \item Algorithmes de recherche
  \item Graphes
  \item Flots
  \item Algèbre linéaire
  \end{enumerate}
  \end{minipage}
  \begin{minipage}[t]{.45\linewidth}
  \substitle{Prérequis d'algorithmique}
  \bigskip
  Pour rattraper l'option informatique des classes préparatoires.
  \\ Facultatif, mais son contenu doit être su.
  \begin{enumerate}
  \item Structures de données
  \item Méthodologie
  \item Tri
  \item Recherche de motifs
  \end{enumerate}
  2 x 1 heure par semaine pendant 6 semaines
  \end{minipage}
\end{sd}

\begin{sd}{TD et TP : L. Mauborgne et L. Granboulan}
  \substitle{Les TD et TP en demi-groupe}
  TP : programmation en langage C (salle T) \\
  TD : exercices d'algorithmique (salle U ou V)
  \par\bigskip
  début : TP le 13 octobre.
  \par\bigskip
  deux groupes de taille équilibrée (11 stations en salle T)
\end{sd}

\SECTION{Programmation impérative}

\begin{sd}{Séquence d'instructions}
  \substitle{Séquence d'instructions}
  L'exécution d'un programme dans un ordinateur est
  \\ l'exécution d'une séquence d'instructions,
  \\ agissant sur la mémoire de la machine,
  \\ interagissant avec l'extérieur par des entrées/sorties.
  \par\bigskip
  La répétition d'une sous-séquence d'instruction se fait par une boucle,
  \\ Le choix entre plusieurs sous-séquences possibles se fait par un
  aiguillage.
  \par\bigskip
  Les briques de la programmation impérative sont
  \\ les séquences d'instructions, les boucles et les aiguillages.
\end{sd}

\begin{sd}{Variables et types}
  \substitle{Variables et types}
  L'action du programme sur la mémoire se fait par l'intermédiaire
  de variables, chacune ayant un type qui décrit ce qu'elle peut contenir.
  \par\bigskip
  Une variable correspond à un espace mémoire d'une taille adaptée au type.
  \par\bigskip
  Un type \textbf{pointeur} référence un espace mémoire, valide ou non,
  correspondant à une variable ou non.
\end{sd}

\begin{sd}{Types élaborés}
  \substitle{Types élaborés}
  \begin{minipage}[t]{.95\linewidth}
  \textbf{Tableaux :}
  une variable qui contient plusieurs copies numérotées et du même type.
  \par\bigskip
  \textbf{Structures/Enregistrements :}
  une variable qui contient plusieurs champs successifs de types variés.
  \par\bigskip
  \textbf{Unions :}
  une variable qui contient plusieurs champs superposés.
  \par\bigskip
  \textbf{Objets :}
  la structure contient aussi les méthodes pour la manipuler.
  \end{minipage}
\end{sd}

\begin{sd}{Procédures, arguments}
  \substitle{Procédures, arguments}
  \begin{minipage}[t]{.9\linewidth}
  Une \textbf{procédure} (routine) est une séquence d'instructions
  ayant des paramètres, appelés arguments.
  \par\bigskip
  Ces \textbf{arguments} peuvent être transmis de plusieurs façons :
  \\ par nom, par valeur, par référence.
  \par\bigskip
  Une procédure peut manipuler des variables locales,
  \\ invisibles de l'extérieur.
  \par\bigskip
  Une \textbf{fonction} est une procédure ayant une valeur résultat.
  \end{minipage}
\end{sd}

\begin{sd}{Gestion de la mémoire}
  \substitle{Gestion de la mémoire}
  De la mémoire est réservée pour
  \begin{minipage}{.5\linewidth}
  \begin{itemize}
  \item[$\bullet$] une déclaration de variable
  \item[$\bullet$] un passage d'argument par valeur
  \item[$\bullet$] une allocation mémoire manuelle
  \end{itemize}
  \end{minipage}
  \par\bigskip
  La mémoire est libérée
  \begin{minipage}{.65\linewidth}
  \begin{itemize}
  \item[$\bullet$] en fin de zone de visibilité d'une variable
  \item[$\bullet$] par une libération manuelle
  \item[$\bullet$] par une libération automatique
    des zones qui ne serviront plus
    (GC : garbage collecting, glanage de cellules)
  \end{itemize}
  \end{minipage}
\end{sd}

\begin{sd}{Langage compilé, interprété}
  \substitle{Langage compilé, interprété}
  Un interpréteur est un programme qui lit et exécute
  \\ au fur et à mesure les instructions du langage (ex.: maple).
  \par\bigskip
  Un compilateur traduit le fichier des instructions de haut niveau
  \\ en des instructions du microprocesseur.
  \\ Il faut exécuter le programme résultat de la compilation
  (ex.: langage C).
\end{sd}

\SECTION{Langage C}

\begin{sd}{Types, opérations}
  \substitle{Types, opérations}
  \begin{minipage}{.45\linewidth}
  \textbf{entiers signés} : \texttt{short}, \texttt{int}, \texttt{long}
  \\ \textbf{entiers non signés} : \texttt{unsigned ...}
  \\ \textbf{flottants} : \texttt{float}, \texttt{double}
  \\ \textbf{caractères} : \texttt{char}
  \\ \textbf{vide} : \texttt{void}
  \par\bigskip\bigskip
  \textbf{constantes} : \texttt{-3}, \texttt{2.7}, \texttt{'c'}
  \end{minipage}
  \quad
  \begin{minipage}{.5\linewidth}
  \textbf{déclaration de variable} : \texttt{int i}
  \\ \textbf{résultat de fonction} : \texttt{return({\sl expr})}
  \\ \textbf{séquence} : \texttt{\{ {\sl inst}; {\sl inst}; \}}
  \\ \textbf{affectation} : \texttt{i = 3}
  \\ \textbf{comparaison} : \texttt{i == 3}, \texttt{<},
     \texttt{<=}, \texttt{!=}
  \\ \textbf{arithmétique} : \texttt{+}, \texttt{-},
     \texttt{*}, \texttt{/}, \texttt{\%}
  \\ \textbf{in(dé)crémentation} : \texttt{i++}, \texttt{i--}
  \end{minipage}
\end{sd}

\begin{sd}{Tests et boucles}
  \substitle{Contrôle}
  \begin{minipage}[t]{.45\linewidth}
  \textbf{tests}
  \\ \texttt{if ({\sl expr}) {\sl inst};}
  \\ \texttt{if ({\sl expr}) {\sl inst}; else {\sl inst};}
  \\ \texttt{{\sl expr} ? {\sl inst} : {\sl inst}}
  \par\medskip
  \begin{tabbing}\tt
  \hspace*{1em} \= \hspace*{1em} \= \hspace*{1em} \= \kill
  switch ({\sl expr}) \{ \\
  \> case {\sl value}: {\sl expr}; break; \\
  \> default: {\sl expr}; \\
  \}
  \end{tabbing}
  \end{minipage}
  \quad
  \begin{minipage}[t]{.5\linewidth}
  \textbf{boucles}
  \\ \texttt{while ({\sl expr}) {\sl inst};}
  \\ \texttt{for ({\sl start}; {\sl end}; {\sl cont}) {\sl inst};}
  \par\bigskip
  exemple : \texttt{for (i=0; i<10; i++) ...;}
  \end{minipage}
\end{sd}

\begin{sd}{Tableaux et pointeurs}
  \substitle{Tableaux et pointeurs}
  \texttt{int *U} définit un pointeur vers un/des entiers.
  \\ \texttt{U = (int*) malloc(sizeof(int))} alloue un espace mémoire
     pour un entier.
  \\ On accède à cet entier par \texttt{*U}.
  \quad On libère la mémoire par \texttt{free(U)}.
  \par\bigskip
  \texttt{int T[10]} définit un tableau de 10 entiers, numérotés de 0 à 9.
  \\ On accède à l'élément 4 par \texttt{T[4]}.
  \\ \texttt{int m[10][10]} définit un tableau à deux coordonnées.
  \\ Il y a définition implicite de pointeurs.
\end{sd}

\begin{sd}{Fonctions, macros}
  \substitle{Fonctions, macros}
  \begin{minipage}[t]{.4\linewidth}
  \textbf{fonction}
  \begin{tabbing}\tt
  \hspace*{1em} \= \hspace*{1em} \= \hspace*{1em} \= \kill
  int min(int a, int b) \\
  \{ \\
  \> if (a $<$ b) return (a); \\
  \> else return (b); \\
  \}
  \end{tabbing}
  \end{minipage}
  \quad
  \begin{minipage}[t]{.5\linewidth}
  \textbf{macro}
  \begin{tabbing}\tt
  \hspace*{1em} \= \hspace*{1em} \= \hspace*{1em} \= \kill
  \#define min(a,b) ((a)$<$(b)?(a):(b))
  \end{tabbing}
  \bigskip
  Remplacement syntaxique
  \end{minipage}
\end{sd}

\begin{sd}{Préprocesseur}
  \substitle{Préprocesseur}
  \begin{minipage}[t]{.45\linewidth}
  \textbf{Headers dans \texttt{toto.h} :\\ prototypes}
  \begin{tabbing}\tt
  \hspace*{1em} \= \hspace*{1em} \= \hspace*{1em} \= \kill
  \#ifndef H\_TOTO \\
  \#define H\_TOTO \\
  int min(int a, int b); \\
  typedef struct chaine \{ \\
  \> char s[80]; \\
  \> struct chaine * next; \\
  \} chaine; \\
  \#endif
  \end{tabbing}
  \end{minipage}
  \quad
  \begin{minipage}[t]{.45\linewidth}
  \textbf{inclusion}
  \begin{tabbing}\tt
  \hspace*{1em} \= \hspace*{1em} \= \hspace*{1em} \= \kill
  \#include $<$stdlib.h$>$ \\
  \#include $<$stdio.h$>$ \\
  \#include "toto.h"
  \end{tabbing}
  \bigskip
  \textbf{commentaire}
  \begin{tabbing}\tt
  \hspace*{1em} \= \hspace*{1em} \= \hspace*{1em} \= \kill
  /* ceci est un commentaire \\
  \> sur deux lignes */
  \end{tabbing}
  \end{minipage}
\end{sd}

\begin{sd}{Allocation mémoire et portée}
  \substitle{Allocation mémoire et portée}
  \begin{minipage}[t]{.95\linewidth}
  \begin{itemize}
  \item[$\bullet$]
  \textbf{auto} réserve de la place,
  la durée de vie est celle du bloc (allocation dans la pile)
  ou sinon le programme
  \item[$\bullet$]
  \textbf{static} réserve de la place, 
  la durée de vie est le programme,
  \item[$\bullet$]
  \textbf{extern} ne réserve pas de place mais référence un élément extérieur
  \item[$\bullet$]
  \textbf{register} identique à auto,
  c'est un conseil au compilateur pour garder la variable dans un registre.
  \end{itemize}
  \par\bigskip
  la \textbf{portée} est le bloc (la fonction) ou sinon le fichier 
  \end{minipage}
\end{sd}

\begin{sd}{Utiliser gcc}
  \substitle{Utiliser gcc}
  \texttt{toto.c} et \texttt{toto.h} $\longrightarrow$ \texttt{toto.i} \\
  Préprocesseur : expansion des macros (\texttt{cpp} ou \texttt{gcc -E}) \\
  \medskip
  \texttt{toto.i} $\longrightarrow$ \texttt{toto.s} \\
  Compilateur : création du fichier assembleur (\texttt{gcc -S}) \\
  \medskip
  \texttt{toto.s} $\longrightarrow$ \texttt{toto.o} \\
  Assemblage : création du fichier objet (\texttt{as} ou \texttt{gcc -c}) \\
  \medskip
  \texttt{toto.o} $\longrightarrow$ \texttt{toto} \\
  Éditeur de liens : création de l'exécutable (\texttt{ld} ou \texttt{gcc})
  \par\bigskip
  Debug : \texttt{-g} \qquad Optimisation : \texttt{-O}
  \qquad Messages : \texttt{-Wall}
  \par\bigskip
  Tout en une instruction : \texttt{gcc -Wall -g -O toto.c -o toto}
\end{sd}

\end{document}
