%% 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}
\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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{Introduction}
\section{Course Objectives}
Mathematical tools for solving problems arising from computer science.
Using a computer to solve problems.
\section{Pólya's hints for solving a problem}
There are two main kinds of problems:
\begin{enumerate}
\item Problems to solve
\item Problems to prove
\end{enumerate}
Here is a list of general questions that will guide you when you try
to solve a problem.
Most of them are borrowed from {}``How to solve it'' by Pólya\cite[p.~XVI]{Polya.HSI}.
({*}subliminal hint{*} you definitely should read this book!)
Whenever you get stuck and don't know what to do, browse through them,
and most likely one of them will give you something to try out.
\subsection{Phase 1: Understanding the problem}
You have to understand the problem.
\begin{enumerate}
\item What is the goal ?
\begin{itemize}
\item What is the unknown?
\item What are the data ?
\item Do you need all data ? Can you simplify the data ?
\end{itemize}
\item What is the condition ?
\begin{itemize}
\item Is it possible to satisfy the condition?
\item Is the condition sufficient to determine the unknown?
\item Or is it insufficient? or redundant? or contradictory?
\item Separate the various parts of the condition. Can you write them down?
\end{itemize}
\item Look at examples. Draw a figure. Introduce suitable notations.
\item How would you store the data on a computer ?
\end{enumerate}
\subsection{Phase 2: Devising a plan}
Find the connection between the data and the unknown.
You may be obliged to consider auxiliary problems if an immediate
connection cannot be found.
You should obtain eventually a \emph{plan} of the solution.
\begin{enumerate}
\item Have you seen it before?
\begin{itemize}
\item Have you seen the same problem in a slightly different form?
\item Do you know a related problem? Do you know a theorem that could be
useful?
\item Look at the unknown! Try to think of a familiar problem having the
same or similar unknown.
\end{itemize}
\item Here is a problem related to yours and solved before. Could you use
it?
\begin{itemize}
\item Could you use its result? Could you use its method?
\item Should you introduce some auxiliary element in order to make its use
possible?
\end{itemize}
\item Could you restate the problem? Could you restate it still differently?
\item Go back to definitions.
\item If you cannot solve the proposed problem, try to solve first some
related problem. Could you imagine a more accessible related problem?
A more general problem? A more special problem? An analogous problem?
\begin{itemize}
\item Could you solve a part of the problem? Keep only a part of the condition,
drop the other part. How far is the unknown then determined, how can
it vary?
\item Could you derive something useful from the data? Could you think of
other data appropriate to determine the unknown? Could you change
the unknown or the data, or both if necessary, so that the new unknown
and the new data are nearer to each other?
\end{itemize}
\item Did you use all the data? Did you use the whole condition? Have you
taken into account all essential notions involved in the problems?
\end{enumerate}
\subsection{Phase 3: Carrying out the plan}
Carry out your plan.
\begin{enumerate}
\item Carrying out your plan of the solution, \emph{check each step}. Can
you see clearly that the step is correct? Can you prove it is correct?
\end{enumerate}
\subsection{Phase 4: Looking back}
Examine the solution obtained.
\begin{enumerate}
\item Can you check the result? Can you check the argument?
\item Can you derive the result differently? Can you see it at a glance?
\item What's the structure behind?
\item Can you use the result, or the method for some other problem?
\item Can you make it an algorithm ?
\begin{itemize}
\item Is your algorithm correct ?
\item Can you prove it is correct ?
\end{itemize}
\end{enumerate}
\section{Some {}``research'' about Mazes}
\begin{center}\includegraphics[%
width=0.5\textwidth]{maze1} \includegraphics[%
width=0.5\textwidth]{maze2}\end{center}
\begin{center}\includegraphics[%
width=1\textwidth]{maze-big}\end{center}
\begin{center}\includegraphics[%
width=0.5\textwidth]{maze3} \includegraphics[%
width=0.5\textwidth]{maze4}\end{center}
\section{Conclusion}
The purpose of this exercise was to browse quickly through what we
are going to do this semester:
\subsection{General problem solving techniques:}
We have used Pólya's list of questions as a guide to solve our problems.
We will do this over and over. Usually the main difficulty with a
problem is to get started. Whenever you get stuck on a problem, and
don't know what to do, you should refer to this list, and see if some
of the questions could give you something to try out.
\subsection{Proofs}
At some time, we had a solution for exiting from a maze. However,
we were not sure if it worked all the time or not. Well, the only
way to be sure that something is correct is to PROVE it.
We will need to learn how to prove things before anything else. In
particular we will want to prove that certain algorithms are correct.
That will be the core of our first month of class.
So what's a proof ? Basically, it's a message written by a human A
to convince another human B that some fact is true (possibly A and
B are the same person). When B reads through the message, he should
not have any choice at the end but to say \char`\"{}I agree\char`\"{}.
To achieve this goal, our primary tool will be Formal Logic.
It's not easy to write good proofs. For example, a proof should be
short enough that you don't get lost in the details, and detailed
enough that you are sure not to have left a hole somewhere. Learning
to write proofs is like learning to write. The only way is to write
a lot of proofs yourself, and to take model on other's proofs. We
will learn this progressively.
\subsection{Discrete structures:}
We have seen that the very structure of a maze (once we have removed
all extraneous information like color, shape and so on) can be formalized
with a graph, that is a set of nodes which are connected or not by
edges.
A graph is a good example of discrete object, or structure (in opposition
to a continuous object like a curve). We are going to see other discrete
structures, and learn to recognize them when the arise at the very
heart of problems. We are also going to see how to deal with such
structures (algorithms and such).
\subsection{Counting objects of a certain kind (Combinatorics) }
How many mazes? how many ordered trees ?
\subsection{Algebraic structures}
That's another kind of structure that can arise in our problems. Addition,
multiplication and other algebraic operations are very powerful tools.
We will see that such operations can often be defined for other objects
that the usual integers or real number.
\subsection{Making a solution into an algorithm, and implementing it}
\end{document}