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

\title{TD 4 d'Algorithmique}
\date{Mercredi 20 octobre 2004}

\begin{document}
\maketitle

\section{Tri tas}

\subsection{Un arbre dans un tableau}

\begin{enumerate}

\item Écrivez la numérotation d'un arbre binaire dans l'ordre du
parcours en largeur sur un exemple: la racine est numérotée $0$, son
fils gauche $1$, son fils droit $1$ et ainsi de suite.

\item Écrivez les fonctions \verb+fgauche+ et \verb+fdroit+ qui prennent en
argument l'indice d'un noeud et retournent l'indice de son fils gauche et
droit, respectivement. Écrivez de même la fonction \verb+papa+.

\item Cette numérotation des noeuds permet de stocker un arbre dans un
tableau. Peut-on stocker tous les arbres dans un tableau de cette
manière? Quelle propriété doivent avoir les arbres à stocker si l'on ne
s'autorise pas de case vide dans le tableau?

\end{enumerate}

\subsection{Un tas}

Un tas est un arbre binaire où la valeur stockée dans un noeud est
plus grande que celles stockées dans ses fils, et cette propriété est
vérifiée à chaque noeud.

\begin{enumerate}

\item On suppose que notre tas est stocké dans un tableau comme vu
précédemment occupant les indices $0$ à $i$ inclus. Comment insérer un
élément supplémentaire dans l'arbre en conservant la propriété de tas,
et en occupant maintenant les indices $0$ à $i+1$? Écrivez
l'algorithme correspondant.

\item On retire l'élément situé à la racine du tas, et on veut y
insérer un nouvel élément en conservant la propriété de tas. Écrivez
l'algorithme pour ce faire.

\end{enumerate}

\subsection{Un tri tas}

\begin{enumerate}

\item Recollez les morceaux écrits jusqu'à maintenant pour obtenir une
fonction de tri dont on analysera le coût en nombre de comparaisons
ansi que la place mémoire nécessaire.

\end{enumerate}

\section{Arbres équilibrés}

On définit la hauteur d'un noeud notée $h$ de façon inductive:

\begin{itemize}

\item La hauteur d'une feuille\footnote{un noeud sans fils.} comme
valant $0$;

\item La hauteur d'un noeud ayant pour fils $(g,d)$ est $1 +
\max(h(g), h(d))$.

\end{itemize}

On dit qu'un arbre est équilibré si pour chaque noeud, l'écart de
hauteur entre ses fils gauche et droit est au plus $1$.

Quelle structure de données est adaptée pour manipuler des arbres
équilibrés?

\begin{enumerate}

\item On suppose que l'arbre est déséquilibré à un noeud. Faites un
dessin et écrivez la fonction de rééquilibrage.

\item On suppose qu'on a un arbre binaire de recherche. Écrivez une
fonction d'insertion qui conserve la propriété d'équilibre.

\end{enumerate}

\section{Expressions arithmétiques}

On considère les expressions arithmétiques formées à partir des
éléments et opérations suivantes:

\begin{itemize}

\item les constantes réelles (\verb+double+ dans notre implémentation
en \verb+C+),

\item les opérations élémentaires binaires \verb-+-, \verb+-+,
\verb+*+, \verb+/+.

\item la négation unaire que l'on écrira \verb+_+.

\end{itemize}

\begin{enumerate}

\item Représentez l'arbre de l'expression arithmétique $(6 * 7) - (125
/ (3 + 2))$.

\item Réécrivez cette expression en notation
préfixe\footnote{l'opérateur précède ses opérandes.}, puis en notation
postfixe\footnote{l'opérateur suit ses opérandes.}.

\item Écrivez les structures de données permettant de manipuler des
arbres d'expressions tels celui de la question 1.

\item Écrivez une fonction calculant la valeur d'une expression
arithmétique donnée par sa représentation en arbre.

\item Écrivez une fonction qui crée l'arbre d'une expression
arithmétique donnée en notation préfixe.

\item Écrivez une fonction qui crée l'arbre d'une expression
arithmétique donnée en notation postfixe.

\end{enumerate}

\end{document}