%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[american]{amsbook}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setlength\parskip{\smallskipamount}
\setlength\parindent{0pt}
\usepackage{graphicx}
\usepackage{amssymb}
\IfFileExists{url.sty}{\usepackage{url}}
                      {\newcommand{\url}{\texttt}}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \numberwithin{section}{chapter}
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{definition}
  \newtheorem*{example*}{Exemple}
 \theoremstyle{definition}
  \newtheorem{problem}[thm]{Problem}
 \theoremstyle{definition}
 \newtheorem*{defn*}{Définition}
 \newenvironment{lyxcode}
   {\begin{list}{}{
     \setlength{\rightmargin}{\leftmargin}
     \setlength{\listparindent}{0pt}% needed for AMS classes
     \raggedright
     \setlength{\itemsep}{0pt}
     \setlength{\parsep}{0pt}
     \normalfont\ttfamily}%
    \item[]}
   {\end{list}}
 \theoremstyle{remark}    
 \newtheorem{summary}[thm]{Résumé} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\usepackage{hyperref}

\usepackage[francais,american]{babel}
\makeatother
\begin{document}

\chapter{Analysis of Algorithm (Section 2.5)}

\begin{example*}
Finding an element in a list.

Computing the nth Fibonacci number $F(n)$.
\end{example*}
\begin{problem}
How long will my program take to execute ?

How much memory do I need ?

How efficient is my algorithm ?

Is it the best one ?

Which algorithm should I choose ?
\end{problem}
Goal: \char`\"{}measure\char`\"{} the quality of an algorithm:

\begin{itemize}
\item Time
\item Memory
\item Easiness of writing
\end{itemize}

\section{Complexity of an algorithm: Measuring time}

\begin{defn*}
Decide which operations are basic (i.e. multiplications).

\emph{Complexity} of the algorithm: how many basic operations are
needed.
\end{defn*}
\begin{example*}
Sequential search
\begin{lyxcode}
SequentialSearch(x,l)

//~Preconditions:

//~-~l~is~a~list~{[}\char`\"{}bonjour\char`\"{},\char`\"{}car\char`\"{},\char`\"{}hello\char`\"{},\char`\"{}juggler\char`\"{}{]}

//~-~x~is~a~string

//~Postcondition:~return~true~iff~x~is~in~the~list

Begin

~~//~compare~successively~x~with~l{[}1{]},~l{[}2{]},~...,~l{[}n{]}

~~For~i~From~1~To~n~Do

~~~~If~(x=l{[}i{]})~Then~Return~TRUE;~EndIf

~~EndFor;

~~Return~FALSE;

End;
\end{lyxcode}
Basic operations: comparison of two strings\@.

How many operations ?
\begin{itemize}
\item x = \char`\"{}unicycle\char`\"{}:
\item x = \char`\"{}juggler\char`\"{}:
\item x = \char`\"{}hello\char`\"{}:
\item x = \char`\"{}car\char`\"{}:
\end{itemize}
Worst case: $n$ basic operations

Average case: depends on the probability for x to be in the list.
Difficult !

\end{example*}
\begin{summary}
$n$: size of the data (here, the length of the list)

Worst case: maximum number of operations for a data of size $n$.

Average case: average number of operations for a data of size $n$
(difficult)
\end{summary}
\begin{example*}
Binary search

A non sorted dictionary is useless!!!
\begin{lyxcode}
BinarySearch(x,~l)

//~Preconditions:

//~-~l~is~sorted~{[}\char`\"{}bonjour\char`\"{},\char`\"{}car\char`\"{},\char`\"{}hello\char`\"{},\char`\"{}juggler\char`\"{}{]}

//~-~x~is~a~string

//~Postcondition:~return~true~iff~x~is~in~the~list

Begin

~~If~n=1~Then

~~~~Return~x=l{[}1{]};

~~ElseIf~x~<=~l{[}n/2{]}~Then

~~~~Return~BinarySearch(x,~{[}l{[}1{]},~...,~l{[}n/2{]}{]});

~~Else

~~~~Return~BinarySearch(x,~{[}l{[}n/2{]}+1,~...,~l{[}n{]}{]});

~~End~if

End
\end{lyxcode}
Basic operation: comparison of two strings.

How many operations ?

\vspace{0.3cm}
\begin{center}\begin{tabular}{|c|c|}
\hline 
$n$&
operations\tabularnewline
\hline
\hline 
1&
\tabularnewline
\hline 
2&
\tabularnewline
\hline 
4&
\tabularnewline
\hline 
8&
\tabularnewline
\hline 
16&
\tabularnewline
\hline
\end{tabular}\end{center}
\vspace{0.3cm}

For $n$, there is at most $k$ operations, where $k$ is the smallest
integer such that $2^{k-1}\geq n$.

$\textrm{log}(n)$: logarithm of n other base 2

Number of operations: $\textrm{log}(n)$
\end{example*}

\subsection{How precise ?}

The estimate above does not give a precise measure of the time needed.

It depends in particular on:

\begin{itemize}
\item What computer you are using
\item How long are the strings
\item The computer language:

\begin{itemize}
\item How fast are strings
\item How fast are for loops
\item How fast are function calls
\end{itemize}
\end{itemize}
A precise measure of the time is often hard to obtain.

Most of the time, to decide between to algorithms, a rough order of
magnitude is enough.

Draw the graphs to get an idea if there are big differences

\begin{itemize}
\item $4n$ operations / $7n$ operations?
\item $4n$ operations / $7n$ operations ?
\item $n$ operations / $n+3$ operations ?
\item $log(n)$ operations / $n$ operations ?
\item $n$ operations / $n^{2}$ operations ?
\item $n$ operations / $\textrm{exp}(n)$ operations ?
\end{itemize}
\begin{defn*}
An algorithm is of complexity $O(n^{5})$ if it needs less than $Cn^{5}+K$
operations to execute, where $C$ and $K$ are some constant.
\begin{itemize}
\item $O(1)$: constant (random access to an element of an array)
\item $O(\textrm{log}(n))$ : logarithmic (random access in a sorted list
by binary search)
\item $O(n)$: linear (random access in a linked list; sequential search)
\item $O(n\textrm{log}(n))$: (sorting a list by a good algorithm)
\item $O(n^{2})$: quadratic (sorting a list by bubble sort)
\item $O(n^{k})$: polynomial
\item $O(\textrm{exp}(n))$: exponential
\end{itemize}
\end{defn*}
Worst case analysis is usually easier. It is important if your need
a warranty on the time needed for each data (e.g.: real time data
acquisition).

Average case analysis is more difficult. It is important when running
over a large sample of data.


\subsection{Case study: the Fibonacci sequence}

Here is a program written in MuPAD \url{www.mupad.de} (free Computer
Algebra system).

It present different implementations of the computation of the Fibonacci
sequence.

\begin{lyxcode}
/{*}

fibonacci\_rec~~~~~~~~~~~(n:~Dom::Integer);

fibonacci\_rec\_remember~~(n:~Dom::Integer);

fibonacci\_loop\_array~~~~(n:~Dom::Integer);

fibonacci\_loop~~~~~~~~~~(n:~Dom::Integer);



Precondition:~n~non~negative~integer

Postcondition:~returns~the~nth~fibonacci~number



Also~increments~the~global~variable~operations.

{*}/



fibonacci\_rec:=

proc(n:~Dom::Integer)

begin

~~if~n=0~then~return(1);~end\_if;

~~if~n=1~then~return(1);~end\_if;

~~operations:=operations+1;~//~Count~operations

~~return(fibonacci\_rec(n-1)+fibonacci\_rec(n-2));

end\_proc:

~

fibonacci\_array:=

proc(n:Dom::Integer)

~~local~i,~F;

begin

~~if~n=0~then~return(0);~end\_if;

~~if~n=1~then~return(1);~end\_if;

~~F{[}0{]}:=0;

~~F{[}1{]}:=1;

~~for~i~from~2~to~n~do

~~~~operations~:=~operations+1;~//~Count~operations

~~~~F{[}i{]}~:=~F{[}i-1{]}~+~F{[}i-2{]};

~~end\_for;

~~return(tableau(n));

end\_proc:

~

fibonacci\_loop:=

proc(n:Dom::Integer)

~~option~remember;

~~local~i,~value,~previous,~previousprevious;

begin

~~if~n=0~then~return(0);~end\_if;

~~if~n=1~then~return(1);~end\_if;

~~previous:=0;

~~value:=1;

~~for~i~from~2~to~n~do

~~~~operations~:=~operations+1;~~~//~Count~operations

~~~~previousprevious:=~previous;

~~~~previous~~~~~~~~:=~value;

~~~~value~~~~~~~~~~~:=~previousprevious+previous;

~~end\_for;

~~return(value);

end\_proc:

~

fibonacci\_rec\_remember:=

proc(n:~Dom::Integer)

~~option~remember;

begin

~~if~n=0~then~return(0);~end\_if;

~~if~n=1~then~return(1);~end\_if;

~~operations~~:=~operations+1;~~~//~Count~operations

~~return(fibonacci\_rec\_remember(n-1)+~

~~~~~~~~~fibonacci\_rec\_remember(n-2)~~);

end\_proc:



printentry:=

proc(x)

begin

~~userinfo(0,~NoNL,~x);

~~userinfo(0,~NoNL,~\char`\"{}\textbackslash{}t\char`\"{});

end\_proc:

~

for~n~from~0~to~30~do

~

~~printentry(n);

~~~~

~~operations:=0;

~~printentry(fibonacci\_rec(n));

~~printentry(operations);

~~~~

~~operations:=0;

~~fibonacci\_array(n);

~~printentry(operations);

~~~~

~~operations:=0;

~~fibonacci\_loop(n);

~~printentry(operations);

~~~~

~~operations:=0;

~~fibonacci\_rec\_remember(n);

~~printentry(operations);

~~//~Clear~remember~table;

~~fibonacci\_rec\_remember:=

~~~~subsop(fibonacci\_rec\_remember,5=NIL);

~~~~

~~print();

end\_for:
\end{lyxcode}
\vspace{0.3cm}
\begin{center}%
\begin{figure}
\includegraphics[%
  width=1\textwidth]{fibonacci}


\caption{Measurement of the complexity of the different implementations of
the Fibonacci sequence}
\end{figure}
\end{center}
\vspace{0.3cm}

\begin{problem}
Why is Fibonacci rec so slow ? (Trace its execution)

How to avoid this?

Don't throw away the results !

The \texttt{remember} option.
\end{problem}
Time consumption:

\begin{itemize}
\item Fibonacci rec: exponential
\item Fibonacci rec\_remember: linear
\item Fibonacci array: linear 
\item Fibonacci loop: linear
\end{itemize}
Memory consumption:

\begin{itemize}
\item Fibonacci rec: exponential
\item Fibonacci rec\_remember: linear
\item Fibonacci array: linear
\item Fibonacci loop: constant
\end{itemize}
Easiness to write:

\begin{itemize}
\item Fibonacci rec: straight forward
\item Fibonacci rec\_remember: straight forward
\item Fibonacci array: easy
\item Fibonacci loop: harder
\end{itemize}

\section{The P=NP conjecture}


\subsection{Case study: Satisfying a well formed formula of propositional logic}

We consider a well formed formulas of propositional logic.

\begin{defn*}
A choice of truth values for $A$, $B$, $C$, \ldots{} \emph{satisfies}
$P$ if $P$ evaluates to true.
\end{defn*}
\begin{example*}
$A$ true and $B$ true satisfies $A\wedge B$.

$A$ true and $B$ false do not satisfy $A\wedge B$.
\end{example*}
\begin{problem}
Given the truth values of $A$, $B$, $C$, ... check if they satisfy
$P$.

Algorithm ? 

Complexity ? 
\end{problem}
\begin{defn*}
A wff $P$ is \emph{satisfiable} if at least one choice of truth values
for $A$, $B$, $C$, ... satisfies $P$.

I.e. $P$ is not a contradiction.
\end{defn*}
\begin{example*}
$A\wedge B$ is satisfiable, whereas $A\wedge A'$ is not.
\end{example*}
\begin{problem}
Testing if a wff $P$ is satisfiable.

Algorithm ?

Complexity ?

Is this the best algorithm ?

Does there exist a polynomial algorithm ?
\end{problem}
%

%

%

%

That's an instance of a problem where:

\begin{itemize}
\item checking a solution is easy (polynomial)
\item finding the solution seems to be hard (the best known algorithm is
exponential)
\end{itemize}
\begin{example*}
Checking if the solution of a crossword puzzle is correct is easy.

Solving the crossword puzzle is not !
\end{example*}
%

\begin{example*}
Backpack problem with $size=23$, and $objects=5,7,7,20,17,5,11,5,19,14$.
\end{example*}

\subsection{Polynomial and Non Deterministic Polynomial problems}

\begin{defn*}
Problems as above are called \emph{NP} (\emph{Non-deterministic Polynomial})

\emph{P}:   collection of all polynomial problems

\emph{NP}: collection of all NP problems
\end{defn*}
\begin{problem}
P = NP ?

In other words:

If it's easy to check a potential solution of a problem,

is there necessarily an easy way to find the solution ?
\end{problem}
%

%

%

%%

Intuitively, no. This cannot be true.

Well, despite a lot of research, we still have no proof!

This is the main problem of theoretical computer science since 30
years.

So, this is YOUR job to find the solution !
\end{document}
