#LyX 1.3 created this file. For more info see http://www.lyx.org/
\lyxformat 221
\textclass amsbook
\begin_preamble
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\usepackage{hyperref}
\end_preamble
\language american
\inputencoding latin1
\fontscheme default
\graphics default
\paperfontsize default
\spacing single
\papersize Default
\paperpackage a4
\use_geometry 0
\use_amsmath 1
\use_natbib 0
\use_numerical_citations 0
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation skip
\defskip smallskip
\quotes_language english
\quotes_times 2
\papercolumns 1
\papersides 2
\paperpagestyle default
\layout Chapter
Introduction
\layout Section
Course Objectives
\layout Standard
Mathematical tools for solving problems arising from computer science.
\layout Standard
Using a computer to solve problems.
\layout Section
Pólya's hints for solving a problem
\layout Standard
There are two main kinds of problems:
\layout Enumerate
Problems to solve
\layout Enumerate
Problems to prove
\layout Standard
Here is a list of general questions that will guide you when you try to
solve a problem.
\layout Standard
Most of them are borrowed from
\begin_inset Quotes eld
\end_inset
How to solve it
\begin_inset Quotes erd
\end_inset
by Pólya
\begin_inset LatexCommand \cite[p.~XVI]{Polya.HSI}
\end_inset
.
\layout Standard
(*subliminal hint* you definitely should read this book!)
\layout Standard
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.
\layout Subsection
Phase 1: Understanding the problem
\layout Standard
You have to understand the problem.
\layout Enumerate
What is the goal ?
\begin_deeper
\layout Itemize
What is the unknown?
\layout Itemize
What are the data ?
\layout Itemize
Do you need all data ? Can you simplify the data ?
\end_deeper
\layout Enumerate
What is the condition ?
\begin_deeper
\layout Itemize
Is it possible to satisfy the condition?
\layout Itemize
Is the condition sufficient to determine the unknown?
\layout Itemize
Or is it insufficient? or redundant? or contradictory?
\layout Itemize
Separate the various parts of the condition.
Can you write them down?
\end_deeper
\layout Enumerate
Look at examples.
Draw a figure.
Introduce suitable notations.
\layout Enumerate
How would you store the data on a computer ?
\layout Subsection
Phase 2: Devising a plan
\layout Standard
Find the connection between the data and the unknown.
\layout Standard
You may be obliged to consider auxiliary problems if an immediate connection
cannot be found.
\layout Standard
You should obtain eventually a
\emph on
plan
\emph default
of the solution.
\layout Enumerate
Have you seen it before?
\begin_deeper
\layout Itemize
Have you seen the same problem in a slightly different form?
\layout Itemize
Do you know a related problem? Do you know a theorem that could be useful?
\layout Itemize
Look at the unknown! Try to think of a familiar problem having the same
or similar unknown.
\end_deeper
\layout Enumerate
Here is a problem related to yours and solved before.
Could you use it?
\begin_deeper
\layout Itemize
Could you use its result? Could you use its method?
\layout Itemize
Should you introduce some auxiliary element in order to make its use possible?
\end_deeper
\layout Enumerate
Could you restate the problem? Could you restate it still differently?
\layout Enumerate
Go back to definitions.
\layout Enumerate
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_deeper
\layout Itemize
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?
\layout Itemize
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_deeper
\layout Enumerate
Did you use all the data? Did you use the whole condition? Have you taken
into account all essential notions involved in the problems?
\layout Subsection
Phase 3: Carrying out the plan
\layout Standard
Carry out your plan.
\layout Enumerate
Carrying out your plan of the solution,
\emph on
check each step
\emph default
.
Can you see clearly that the step is correct? Can you prove it is correct?
\layout Subsection
Phase 4: Looking back
\layout Standard
Examine the solution obtained.
\layout Enumerate
Can you check the result? Can you check the argument?
\layout Enumerate
Can you derive the result differently? Can you see it at a glance?
\layout Enumerate
What's the structure behind?
\layout Enumerate
Can you use the result, or the method for some other problem?
\layout Enumerate
Can you make it an algorithm ?
\begin_deeper
\layout Itemize
Is your algorithm correct ?
\layout Itemize
Can you prove it is correct ?
\end_deeper
\layout Section
Some
\begin_inset Quotes eld
\end_inset
research
\begin_inset Quotes erd
\end_inset
about Mazes
\layout Standard
\align center
\begin_inset Graphics
filename maze1.eps
display color
width 50text%
\end_inset
\begin_inset Graphics
filename maze2.eps
display color
width 50text%
\end_inset
\layout Standard
\align center
\begin_inset Graphics
filename maze-big.eps
display color
width 100text%
\end_inset
\layout Standard
\align center
\begin_inset Graphics
filename maze3.eps
display color
width 50text%
\end_inset
\begin_inset Graphics
filename maze4.eps
display color
width 50text%
\end_inset
\layout Section
Conclusion
\layout Standard
The purpose of this exercise was to browse quickly through what we are going
to do this semester:
\layout Subsection
General problem solving techniques:
\layout Standard
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.
\layout Subsection
Proofs
\layout Standard
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.
\layout Standard
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.
\layout Standard
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 "I agree".
To achieve this goal, our primary tool will be Formal Logic.
\layout Standard
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.
\layout Subsection
Discrete structures:
\layout Standard
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.
\layout Standard
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).
\layout Subsection
Counting objects of a certain kind (Combinatorics)
\layout Standard
How many mazes? how many ordered trees ?
\layout Subsection
Algebraic structures
\layout Standard
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.
\layout Subsection
Making a solution into an algorithm, and implementing it
\the_end