Transcript in PPT - Department of Computer Science

The Role of Theory in
Computer Science
Chapter 1
Overview

Computer Science: study of computers and
programs



Computers made up of simple elements – tasks
performed can be very complex
Great disparity between two “aspects” offer
intellectual challenges
Models and methods of analysis to answer these
challenges – heart of theoretical computer science
Overview (cont.)

Computer scientists have developed models
for machines –



Random-access machines
Turing machines
Computer scientists have developed models
for languages –


Regular languages
Context-free languages
Overview (cont.)

Computer scientists have developed models
for programs –



Straight-line programs
Branching programs
Computer scientists have developed models
for systems of programs –


Compilers
Operating systems
Overview (cont.)

Computer scientists have developed models
for data structures –



Heaps
Binary search trees
Computer scientists have developed models
for databases –


Relational databases
Object-oriented databases
Overview (cont.)

Computer scientists have developed methods
of analysis to study –



Efficiency of algorithms and their data structures
Expressibility of languages and capacity of
computer architectures to recognize them
Classification of problems in terms of time and
space complexity to solve them
Brief History of Theoretical
Computer Science

Early years

Turing and Church: introduced formal
computational models




Turing machine and -calculus
Demonstrated unsolvability of certain problems
Demonstrated existence of universal machines
First computers

Konrad Zuse built the Z3 in 1941

First general-purpose program-controlled computer using
electromagnetic relays
Brief History of Theoretical
Computer Science (cont.)

Eckert and Mauchly built the ENIAC in 1940s


Von Neumann in 1946 codified the model of computer
architecture that now bears his name


First programmable electronic computer using vacuum tubes
“Stored-program” concept formalized
Early language development

High-level programming languages first developed in
the 1950s


FORTRAN, COBOL, LISP
Formal languages and automata theory became “hot”
topics of research in 1950s

Non-deterministic models introduced as a way to classify
languages
Brief History of Theoretical
Computer Science (cont.)

1950s

Finite-state machines



Sequential machine, sequential circuit, pushdown
automaton
Rabin & Scott pioneered use of analytical tools to
study capabilities and limitations of these models
Formal languages

Chomsky language hierarchy developed:
regular, context-free, context-sensitive, recursively
enumerable languages
Brief History of Theoretical
Computer Science (cont.)


Corresponding “models” recognized:
finite-state machine, push-down automaton,
linear-bounded automaton, Turing machine
1960s

Computational complexity




Time and space resource requirements for computing
functions studied by Hartmanis, Lewis & Stearns
Problem hierarchies developed
NP-complete languages/problems discovered by Cook
Importance of NP-complete languages demonstrated
by Karp: PNP issue raised
Brief History of Theoretical
Computer Science (cont.)

1970s

Computation time vis-à-vis circuit complexity




Established in early 70s giving study of circuits new
impetus
Raised hope that PNP issue might be resolved via
that route
P-complete languages identified – hardest languages
in P to recognize on parallel machines
Programming language semantics

Models and denotations developed to formalize field
Brief History of Theoretical
Computer Science (cont.)



Space-time tradeoffs


Formal methods for ensuring program correctness
developed
Emergence of relational database model
Pebble game developed: allowed study of tradeoffs
between space allocated and time devoted to a
program
VLSI model

Developed to analyze hardware-side advances in
semiconductor chip architecture
Brief History of Theoretical
Computer Science (cont.)

Algorithms and data structures


Knuth, Aho, Hopcroft, & Ullman led developments
that introduced new sorting techniques, data storage
strategies, graph algorithms, computational geometry,
etc.
80s & 90s

Parallel computing & I/O complexity



VLSI-based models developed
PRAM introduced
Parallel algorithms and data structures designed
Brief History of Theoretical
Computer Science (cont.)

Distributed computing



Emergence of networks necessitated development of
theory of distributed computing
Issues of reaching consensus in the presence of
malicious adversaries, handling failures in component
processors, efficient coordination when latencies are
significant, etc. were tackled
Cryptography

Issues of security in a networked environment thrust
this “old” field into forefront
Brief History of Theoretical
Computer Science (cont.)

Important problems tackled were:




Secret exchange of information without exchanging
private keys between communicating agents
Identification of sender of message with high degree of
assurance
Convincing other agents of possession of a correct problem
solution without transferring the solution
Theoretical computer science is a relevant
field: lays solid formal foundation to an
inherently practical field
Mathematical Preliminaries

Rate of Growth of Functions

Big “Oh”, big Omega and big Theta notation


Definition 1.2.1 (see pp 13-14)
Allows for rough comparison between different
functions: “asymptotic” rates of growth




f(x) = O(g(x))
f(x) = (g(x))
f(x) = (g(x))
Useful in categorizing complexity classes, e.g., P
roughly consists of problems solvable in time O(nk)
for some k finite
Methods of Proof

Proof by induction


Applicable to predicates that are “indexed” by the
natural numbers – P : NB.
Involves three “stages”




Basis step
Induction hypothesis
Inductive step
Proof by contradiction

Demonstrates that the negation of a predicate is
false, thereby proving the predicate’s validity
Computational Models
 Logic Circuits


Direct acyclic graph in which “all vertices except input
and output vertices carry the labels of gates”
Logical gate realizes a Boolean function
Computational Models (cont.)

Execute straight-line programs, programs containing
only assignment statements
N0 := N16  N17
N10 := N0
N9 := N0
N4 := N10  N0
N8 := N4
Computational Models (cont.)




Logic circuits are the basic building blocks of all digital
computers today
Combined with binary memory cells, can construct
machines with memory
Modeled by finite-state machines
Finite-State Machines (FSM)


Machine with memory
Executes series of steps moving from one state in a set of
states Q to another, taking input and producing output
according to a “program” expressed as a logic circuit L
Computational Models (cont.)
Output
Input
L

Memory
The logic circuit L has two “functions:


Determine the next state the FSM enters into
(“next-state” function)
Determine the output (if any) to be produced
(“output” function)
Computational Models (cont.)

FSMs can be represented by “state diagrams”


States are represented by nodes in a directed graph
Edges are labeled by symbols presenting themselves as input
Computational Models (cont.)

Random-Access Machines (RAM)

Modeled by a pair of interconnected finite-state
machines: a central processing unit (CPU) and a
random-access memory
Computational Models (cont.)




Random-access memory holds both data and programs,
which are instructions for the CPU
Central processing unit executes fetch-and-execute
cycle, repeatedly fetching an instruction from the
random-access memory and executing it
Instructions can be logical, arithmetic, comparative, or
controlling (e.g., jumps) in nature
Models typical modern computer although on a much
simpler scale
Computational Models (cont.)

Other Models

Turing machines




Control unit
(an FSM!)
Tape unit
(may be infinite!)
I/O tape head
(controlled by
control unit)
Pushdown automata

Restricted TM where tape access is on a pushdown stack basis
Computational Models (cont.)

Formal Languages


Different models can be characterized by their language
recognition capability
Language recognized by a FSM can be defined in two
ways:



Set of input strings that cause the FSM to produce a particular
letter as its last output; or
Set of input strings that cause the FSM to enter a final state on
its last input
FSM can be thought of as computing some function

Domain is Q* and range is Q*
Computational Models (cont.)





Class of languages recognized by FSMs are the regular
languages
Class of languages recognized by non-deterministic
pushdown automata are the context-free languages
Class of languages recognized by linear bounded
automata are the context-sensitive languages
Class of languages recognized by Turing machines are
the phase-structure languages
These four comprise the Chomsky Hierarchy of
languages
Computational Models (cont.)

Formal Languages and Programming Languages



Programming languages contain character strings and
literals formed from an alphabet
Rules for forming these (essential in forming identifiers
and literal values) can be framed in terms of regular
grammars and can be mechanized using FSMs
These are then tokenized and participate in higher-level
program constructs whose rules can be framed in terms
of context-free grammars and can then be mechanized
using pushdown automata
Computational
Complexity

A Computational Inequality



Important notion used throughout text
Makes use of simulation, another important notion used
throughout the text
Involves the simulation of a FSM by a logic circuit


Assume a FSM computes the Boolean function
f : Bn  Bm
in T steps
Simulate this computation with a logic circuit involving T
copies of the logic circuit of the FSM
Computational
Complexity (cont.)
Output
Input
L
y1
x1
s
L
Memory
y2
x2
q1
L
y3
x3
q2
L
…
q3
yT
xT
qT1
L
qT
Computational
Complexity (cont.)

A Computational Inequality (cont.)





Simulation has TC(L) gates
C(L) is the number of gates used to realize the logic circuitry of
the FSM that computes f
Let C(f) be the smallest number of gates one can employ to
realize the function f
We have
C(f)  TC(L)
Has two important implications:


A claim that a circuit realizes f with TC(L) too small, e.g, less
than C(f), cannot be taken seriously
A complex function, for which C(f) would be elevated, will need
more cycles (T) or more gates (C(L)) or both
Computational
Complexity (cont.)

A Computational Inequality (cont.)




For bounded-memory RAMs, the size S of the memory may be
large and can be taken to be proportional to C(L),
i.e.,
C(L)  S
for some constant 
Substituting, we have
C(f)  TC(L)
C(f)  ST
This inequality expresses the central role of circuit complexity
in theoretical computer science
Also expresses the space-time product as a measure of problem
complexity: functions with large circuit size (must be difficult
to compute!) can be computed by a RAM only if it either has a
large storage capacity or executes many time steps or both
Computational
Complexity (cont.)

A Computational Inequality (cont.)





Simulation has TC(L) gates
C(L) is the number of gates used to realize the logic circuitry of
the FSM that computes f
Let C(f) be the smallest number of gates one can employ to
realize the function f
We have
C(f)  TC(L)
Has two important implications:


A claim that a circuit realizes f with TC(L) too small, e.g, less
than C(f), cannot be taken seriously
A complex function, for which C(f) would be elevated, will need
more cycles (T) or more gates (C(L)) or both
Computational
Complexity (cont.)

Complexity Classes





Provide a way to group languages of similar computational
complexity
For example, NP or the nondeterministic polynomial-time
languages are solvable in time that is polynomial in the input size
using a nondeterministic Turing machine (TM)
A language L is in NP if there exists a TM such that, given an
arbitrary string in L, there is a sequence of states from the initial
state that would bring the TM to an accepting state in a number of
moves that is polynomial in the length of the input string
An NP-complete language is a language L that is in NP and for
which any other language in NP can be “transformed” to L
Hence, if L is ever shown to be in P, then all other languages in NP
would have to also be in P by “transitivity”
Computational
Complexity (cont.)

Complexity Classes
Computational
Complexity (cont.)



However, the best algorithms extant for NP-complete languages are
intractable (i.e., have exponential running time)
Most solutions are approximate solutions that settle for a provably
“good enough” solution in exchange for a more modest running
time
Circuit Complexity


A difficult topic – despite years of research, have not found methods
to demonstrate that individual functions have super-polynomial
circuit size or more than poly-logarithmic depth
Nevertheless, interesting to study and yield important lower bound
results
Parallel Computation

VLSI machine and PRAM are examples of parallel
machines


VLSI machine models constraints on FSMs realized
through very large-scale integration of components on
semiconductor chips
Several economical and very regular FSM designs have
been proposed for VLSI chips


Systolic array – a one- or two-dimensional array of identical
FSAs operating synchronously and communicating only with
direct neighboring processors
Not an accurate model of current parallel processors for which
the communication topology is less restricted
Parallel Computation (cont.)
 Systolic array examples
Parallel Computation

Processors in a PRAM operate synchronously as well,
alternating between global memory and local access

Global common memory simulate a network where
communication path lengths are the same for any pair of
processors