notes-weeks-3-4-5.html

CSci 41

Introduction to Computer Science

Fall 2000
Main Lecturer: Michael Feldman, Professor, Dept. of Comp. Sci.
Office: Academic Center, Room T-715
Office Hours: T-Th 2 - 3:30 PM, W 2 - 5:30 PM,
Phone: 994-5919 (e-mail is better, though!)

E-mail: mfeldman@seas.gwu.edu
Lecturer website: http://www.seas.gwu.edu/~mfeldman
Course website: http://www.seas.gwu.edu/~csci41/fall00

Notes for weeks 3-4-5

Watch this space for additional notes to be added

Artificial Intelligence (AI): Can Computers Think?

Turing test

"AI" term first used in 1956 by John McCarthy (MIT): the use of computers for studying and modeling certain problem-solving tasks that were, prior to the invention of the computer, thought to be uniquely human.

Marvin Minsky (1960s): AI is "the science of making machines do things that would require intelligence if done by man."

Patrick Hayes: "the study of intelligence as computation"

Game playing? Language translation? Pattern recognition?

Humans vs. Computers

Human brain capacity estimated about 50 trillion bits or 5 trillion bytes (5,000 gigabytes)

Largest current computers: about 100 gb

Typical current RAM: about 0.1-0.2 gb (100-200 mb)

Each human neuron estimated to connect to 5,000 others

Game Playing

Checkers (draughts) and chess programs—"Why not just store all possible games, and, given an opponent's move, choose the best response?"

As an undergraduate in 1964, Prof. Feldman asked this question of IBM's checkers-program developer. The answer was that it would take about 2^15 centuries to searech all those games and decide to make a move.

A 1964 computer had a clock rate of (say) 1 MHz; today's computers run at about 1 GHz or 1,000 MHz. So a current computer would run 1,000 times faster, and thus take only 2^12 centuries. This is obviously not the way to play checkers or chess!

Language translation and understanding:
Syntactic and semantic analysis.

Syntax analysis compares statements in a language to the grammar, or set of rules, for writing a well-formed statement in that language.

Semantic analysis analyzes well-formed statements of a language to determine whether they are meaningful.

Examples:

Monkey ate banana.
The monkey ate the banana.
George ate the banana.
The banana ate the monkey.
The banana ate George.
Time flies like an arrow; fruit flies like a banana.

Pattern Recognition

Satellite imagery data

X-ray processing

Potato sorting

Optical character recognition (OCR) —

matrix matching, pattern analysis
scanners can resolve to ~1/300 - 1/600 inch
good OCR is about 96-99% accurate

1,000-word paper: roughly 5,000 characters

Analytical Engine measurements:

~350 pages
~45 lines/page
~1 line = ~5 inches
~18 characters/inch or 1/18 inch/char

If today's typical OCR were used to scan the whole book, about how many characters would have to be manually corrected?