\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{fullpage}
\usepackage{amsfonts}

\title{TD 1 d'Algorithmique}
\date{Lundi 27 septembre 2004}

\begin{document}
\maketitle

\section{Listes en C}

On définit une structure de liste d'entiers en \verb+C+ de la façon
suivante:

\begin{verbatim}
struct noeud {
    int elem;
    struct noeud *suiv;
};

typedef struct noeud *liste;
\end{verbatim}

\textbf{Fonctions de base: constructeurs, accesseurs}

Écrivez les fonctions suivantes:
%\begin{verbatim}
%liste new_list(void);
%liste cons (int, liste); 
%\end{verbatim}
\begin{itemize}
\item \verb+new_list+ (créer une nouvelle liste),
\item \verb+is_empty+ (tester si une liste est vide),
\item \verb+cons+ (ajouter un élément en tête d'une liste),
\item \verb+first+ (récupérer l'élément de tête d'une liste),
\item \verb+tail+ (récupérer la liste privée de son élément de tête),
\item \verb+concat+ (concaténer deux listes).
\end{itemize}

\textbf{Fonctions évoluées}

\begin{itemize}

\item Quel serait le type d'une liste de listes d'entiers? Écrivez une
fonction \verb+merge+ qui met bout à bout les éléments d'une liste de
listes.

\item Au niveau des performances, que pensez-vous de notre type de
liste? Une suggestion d'amélioration?

\item Écrivez la fonction \verb+map+ qui prend une liste d'entiers,
une fonction \verb+f+ des entiers vers les entiers et renvoie la liste
des images par \verb+f+ des entrées.

\item Écrivez la fonction \verb+miroir+ qui renverse une liste.

\item Écrivez la fonction \verb+reduce+ qui applique une fonction
\verb+f+ à deux arguments de façon cumulée sur une liste. Par exemple,
si \verb+f+ est l'addition \verb+reduce+ devra faire la somme de toute
la liste.

\end{itemize}

\textbf{Tri insertion}

\begin{itemize}

\item Écrire une fonction \verb+insertion+ qui insère un élément à la
bonne place dans une liste triée. Quelle est la complexité de
l'opération d'insertion?

\item En déduire une fonction de tri, \verb+tri_insertion+. Quelle est
sa complexité? Quel est le pire cas?

\end{itemize}

\textbf{Tri fusion}

\begin{itemize}
\item Écrivez la fonction \verb+coupe+ qui coupe une liste en deux
listes de taille égale (à un près quand la liste d'entrée contient un
nombre impair d'éléments).

\item Écrivez la fonction \verb+fusion+ qui prend deux listes triées
et renvoit la liste triée contenant les éléments des deux listes
d'entiers.

\item En déduire une fonction de tri. Quelle est sa complexité? Y
a-t-il un pire cas?

\end{itemize}

\section{Tableaux en C}

\textbf{Quelques algos de base}

\begin{itemize}

\item Écrivez un algorithme pour retrouver l'indice d'un élément d'un
tableau trié.

\item Écrivez un algorithme pour trouver l'indice de l'élément le plus
grand d'un tableau. Et si on veut le deuxième plus grand aussi?

\item On suppose que les éléments $i$ à $j$ du tableau sont triés, de
même que les éléments $j+1$ à $k$. Écrivez une procédure de fusion
pour que les éléments $i$ à $k$ du tableau soient trié. On pourra
écrire la sortie dans un tableau annexe.

\item En déduire une procédure qui trie un tableau d'entiers donné en
entrée.

\end{itemize}

\textbf{Arithmétique}

On stocke des polynômes de $\mathbb{Z}[X]$ dans un tableau d'entiers.

\begin{itemize}

\item Écrivez une fonction réalisant la somme de deux polynômes.

\item Écrivez une fonction pour multiplier deux polynômes (de façon
naïve). Quel est la complexité de cette fonction?

\item Multiplication de Karatsuba. On rappelle le principe de la
multiplication Karatsuba de deux polynômes $P(X)$ et $Q(X)$ de degré
$2^{n}-1$ chacun:

$$ P(X) = P_0(X) + X^{2^{n-1}} P_1(X) $$
$$ Q(X) = Q_0(X) + X^{2^{n-1}} Q_1(X) $$
$$ P \cdot Q = P_0 \cdot Q_0 + X^{2^{n-1}}(P_0 \cdot Q_1 + P_1 \cdot
Q_0) + X^{2^n} P_1 \cdot Q_1$$ 
semble coûter $4$ multiplications de degré $2^{n-1}-1$, mais en
calculant:
$$ R = P_0 + P_1$$
$$ S = Q_0 + Q_1$$
on obtient
$$ P_0\cdot Q_1 + P_1\cdot Q_0 = R \cdot S - P_0\cdot Q_0 - P_1\cdot
Q_1$$
et il n'est plus nécessaire de calculer que $3$ multiplications.

Écrire une multiplication de Karatsuba. Quel est sa complexité?

\end{itemize}

\section{Induction vs itération: Fibonacci}

On rappelle la suite de Fibonacci définie par
$$ F(n) = \left\{
\begin{array}{ll}
0 & \mathrm{si}~n = 0\\
1 & \mathrm{si}~n = 1\\
F(n-1) + F(n-2) & \mathrm{sinon}
\end{array}
\right. $$

\begin{itemize}

\item Écrivez une fonction récursive \verb+fibo_rec+ calculant le
terme d'indice $n$ de la suite de Fibonacci. Prouvez sa terminaison,
sa correction, et calculez sa complexité.

\item Écrivez une fonction itérative \verb+fibo_iter+ calculant le
terme d'indice $n$ de la suite de Fibonacci. Prouvez sa terminaison,
sa correction, et calculez sa complexité.

\end{itemize}

\end{document}