This repository has been archived by the owner on Feb 10, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
algo.tex
164 lines (115 loc) · 5.8 KB
/
algo.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
\documentclass[10pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[left=2.5cm,right=2.5cm,top=2.5cm,bottom=2.5cm]{geometry}
\author{Antoine Gennart \& Marie-Pierre van Oldeneel}
\title{Explication de l'algorithme}
\begin{document}
\maketitle
Ce document est destiné à décrire tout l'algoritme du code du fichier code.oz. Il n'est pas destiné à un quelconque proffesseur, mais juste à éclaircir la compréhension du code et des environnements contextuels des différentes fonctions et sous fonctions.
Pour rappel, l'objectif du code est de gérer un jeu de "Qui-est ce ?" dans le très répandu language informatique OZ
\tableofcontents
\newpage
\section{BuildDecisionTreeWithQ}
\paragraph{Description :} Crée un arbre de décision à partir de du base de donnée de personnes et d'une liste de personnes.
\begin{itemize}
\item Gardener
\item BestQuestion
\end{itemize}
\subsection{MakeListOfNames L}
\paragraph{Description :} A partir d'une liste de person(NOM Q:true ..... false), crée une liste contenant uniquement les NOM.
\begin{itemize}
\item MakeListAcc
\end{itemize}
Complexité temporelle : $O(n)$ avec n la taille de liste L.
\subsection{Gardener DB ListT ListF ActualQuestion ListOfQuestions}
\paragraph{Description :} C'est réellement le jardinier du programme, c'est lui qui s'occupe de créer l'arbre de manière récursive.
\begin{itemize}
\item BestQuestion
\item MakeListOfNames
\end{itemize}
A chaque itération, Gardener se sépare en deux dimiuant toujours la taille de la DB.
Complexité temporelle : La fonction se rappelle a chaque itération deux fois (typiquement $\Theta(n^2)$, avec n la taille de la liste de questions), en changeant ses argument avec l'aide de la fonction BestQuestion ($O(n_1 \dot n_2)$).
On peut donc définir la complexité temporelle de cette fonction comme $\Theta(n_1 \cdot n_2^2)$ ou $n_2$ est la taille de la liste de question, $n_1$ la taille de la DB.
\section{BestQuestion DB ListOfQuestions}
\paragraph{Description :} Choisis dans une liste de questions laquelle conviendra le mieux pour éliminer le plus de personnes possible d'une certaine base de donnée.
\begin{itemize}
\item DiffTrueFalseList
\item MinList
\item RemoveList
\end{itemize}
Connaissant la complexitées temporelles des sous fonction, on peut calculer la complexité temporelle de BestQuestion qui appelle chacune des fonctions séparément.
Complexité Temporelle : $O(n_1 \cdot n_2) + O(n_2) + O(n_2)$ ou $n_1$ est la taille de DB et $n_2$ la taille de ListOfQuestions
\subsection{RemoveList L Nth}
\paragraph{Description :} Retire le Nième élément d'une liste
\begin{itemize}
\item RemoveListAcc
\end{itemize}
Complexité temporelle : $O(n)$ ou n est la longueur de la liste
\subsection{MinList L}
\paragraph{Description :} Retourne l'indice de l'emplacement du plus petit élément de la liste
\begin{itemize}
\item MinListACc
\end{itemize}
Complexité temporelle : $O(n)$ ou n est la longueur de la liste L
\subsection{DiffTrueFalseList DB ListOfQuestions}
\paragraph{Description :} Crée une liste dont chaque élément est la valeur absolue de la différence des réponses true et false par les personnes à laquelle on soustrait le nombre de personne qui ont répondu a la question.
\begin{itemize}
\item DiffTrueFalseListAcc
\end{itemize}
Complexité temporelle : $O(n1 \cdot n2)$ ou n1 est la taille de la DB et n2 la taille de ListOfQuestions
\section{BuildDecisionTree}
\paragraph{Description :} Crée un arbre de décision juste à partir de la base de donnée. C'est cette fonction que l'on doit donner au player pour lancer l'interface graphique.
\begin{itemize}
\item MakeListOfQuestions
\item BuildDecisionTreeWithQ
\end{itemize}
\section{MakeListOfQuestions DB}
\paragraph{Description :} Fait une liste des questions a partir de toutes celle qui apparaisent dans une base de donnée.
\begin{itemize}
\item MakeListOfQuestionsAcc
\item RemoveDouble
\end{itemize}
Complexité temporelle : $\Theta(n_1 \cdot n_2)$ avec $n_1$ la taille de la base de donnee et $n_2$ le nombre total de questions (de tous les joueurs).
\subsection{RemoveDouble List}
\paragraph{Description :} Retire toutes les valeurs qui apparaissent deux fois dans une liste.
\begin{itemize}
\item RemoveDoubleAcc
\item IsIn
\end{itemize}
Complexité temporelle : $O(n)$ ou n est la taille de la List
\subsection{IsIn X L}
\paragraph{Description :} Fonction Boolean qui regarde si un élément appartient à une liste
Complexité temporelle : $\Theta(n)$, $\Omega(1)$ ou n est la taille de la liste L
\section{GameDriver}
\paragraph{Description :} Pilote du jeux qui va se ballader dans l'arbre pour poser les bonnes questions à l'utilisateur. Si l'utilisateur est con et qu'il ne sait pas, il doit recreer un arbre.
\begin{itemize}
\item GameDriverAcc
\end{itemize}
\subsection{NewDataBase DB}
\paragraph{Description :} Met à jour la base de donnée en retirant les personnes qui n'ont pas la même réponses que celle décidée par l'utilisateur.
\begin{itemize}
\item NewDBAcc
\end{itemize}
Complexité temporelle : $O(n)$ ou $n$ est la taille de la DB
\subsection{NewListOfQuestions ActualQ LQ}
\paragraph{Description :} Retire la dernière questions posée de la liste des questions.
\begin{itemize}
\item RemoveList
\end{itemize}
Complexité temporelle : $O(n)$ ou $n$ est la taille de la liste de questions
\subsection{GameDriverAcc}
\paragraph{Description :} Fonction récursive du GameDriver.
\begin{itemize}
\item NewListOfQuestions
\item NewDataBase
\item BuildDecisionTreeWithQ
\item GameDriverAcc
\end{itemize}
Complexité temporelle : $\Theta(n_1 * O(BuildDecisoinTree))$
Le pire cas est lorque l'utilisateur ne connait pas la réponse, il faut donc faire appel n fois à la fonction BuildDecisionTreeWithQ
\end{document}