software hardware
==============
algorithmics
We didn't yet define what is algorithm. We begin with equating "program" with "algorithm" and ask "how to predict how long it take a program to run?". This question is the essence of analysis in algorithmics.
problem size vs effort to get a solution
Now we will define algorithms informally "algorithms": step-by-step procedure for solving a problem. According to Oxford dictionary "algorithm": a process or set of rules used for calculation or problem-solving, esp. with a computer.
Plan:
1 build abstract model (model talks about problem, decide different
soln)
2 design algorithm within model
3 analyse
algorithm for -> upper bound
problem for -> lower bound
upper bound: the work sufficient to solve problem within model
lower bound: the work necessary to solve problem within model
4 compare upper/lower bound
4.1 change algorithm
4.2 find better lower bound
4.3 change model
4.4 change problem
2) characterization of desired outputs as a function of inputs
1 + 2 is Problem
any legal input
|
v
algorithm A
|
v
desired output
is solution
analysis needs mathematics
mathematics needs critical thinking
Mathematics forces us to identify our assumptions and so deal with the unusual. As a collorary, we shouldn't be surprised if we derive counter intuitive results using mathematics; in a way, that's what it's for.
Obviousness is always the enemy of correctness, B. Russell
1 search problem: find X in an input satisfying P
2 structuring problem : transform input to satisfy P
3 construction problem: build X satisfying P
4 optimization problem: find the best X satisfying P
5 decision problem: decide whether the input satisfies P
6 adaptive problem: maintain P over time (OS, control, server...)
Problem categorizes by difficulty
1 conceptually hard
2 analytically hard
3 computationally hard
4 computationally unsolvable
Artificial Intelligence studies 1,2
the field of complexity studies 2,3
the field of computability studies 3,4
Algorithm for algorithm design :-)
if the upper bound and lower bounds match
then stop
else if they are close enough of the problem is not that important
then stop
else if the model focuses on the wrong thing
then restate it
else if the algorithm is too fat
then generate a slimmer algorithm
else if the lower bound is too weak
then generate a stronger lower bound
repeat to perfection or exhaustion
Good judgment comes from experience,
and experience comes from bad judgment.
Barry LePatner
9th century Persian, Mohammed al-Khowarizmi, rules for + - * /
written in latin becomes "Algorismus" -> Algorithm
1801 Josep Jacquard, machines
1833 Charles Babbage, difference engine, analytical engine
1890 Herman Hollerith, tabulating machine for US national cencus
1940 general purpose computer
1920 IBM
1940 Association of Computing Machinery ACM
1968 ACM curriculum on computer science
PUZZLE(x)
while x != 1J.C. Lagarias, “The 3x + 1 problem and its generalizations”, American mathematical monthly, 92, 3-23, 1985.
if x is even
then x = x / 2
else x = 3x + 1
Sample run: 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
2) Four-color problem
formulate 1852 solved in 1976 by
K.I. Appel and W. Haken, "Every planar map is four colorable", Bull.
Amer. Math. Soc. 82(1976) pp.711-712.
Two parts of the proof:
1) use mathematical reasoning to reduce the general problem into a
finite set of special cases (approx. 1700 cases)
2) write computer program to find 4-color for all of those special
cases.
QED (quod erat demonstrandum)
Philosophical question: Can mathematical truth be relied on the correctness of software?
A detailed story of solving four-color problem can be found in :
T. Saaty and P. Kainen, "the four color problem: Assualts and conquest",
Dover pub. NY, 1986.
(I remember there is one in the library of our department of mathematics)
last update 5 June 2002