Transcript Midterm Review

Midterm Review
Dr. Philip Cannata
1
Dr. Philip Cannata
2
Dr. Philip Cannata
3
Python class code for Aristotle example – animal, cat, human, and knowledge classes
class animal() :
num_eyes = 2
num_teeth = 24
def __init__(self, e, t) :
self.num_eyes = e
self.num_teeth = t
class cat(animal) :
def __init__(self, c, l) :
self.fur_color = c
self.len_tail = l
socrates = human(s="Golf")
print socrates.num_eyes, socrates.num_teeth, socrates.IQ, socrates.sports_played
class knowledge() :
grammatical = ''
math = ''
human = []
def __init__(self, g, m) :
self.grammatical = g
self.math = m
a1 = animal(2, 30)
print a1.num_eyes, a1.num_teeth
my_cat = cat("yellow", 4)
print my_cat.num_eyes, my_cat.num_teeth, my_cat.fur_color, my_cat.len_tail
class human(animal) :
IQ = 100
sports_played = "Football"
knowledge = []
def __init__(self, s, i = 100) :
self.IQ = i
self.sports_played = s
Dr. Philip Cannata
socrates_Knowledge = knowledge('Some Greek language knowledge', "Some
math smarts")
socrates.knowledge.append(socrates_Knowledge)
socrates_Knowledge.human.append(socrates)
print socrates.num_eyes, socrates.num_teeth, socrates.IQ, socrates.sports_played,
socrates.knowledge[0].grammatical, socrates.knowledge[0].math
print socrates.knowledge
print socrates_Knowledge.grammatical, socrates_Knowledge.math,
socrates_Knowledge.human[0].sports_played
4
Code from September 17, 2013 Lecture
class Person() :
name = None
parents = []
kids = []
has = None
def __init__(self, name) :
self.name = name
p1 = Person("phil")
p2 = Person("rita")
p3 = Person("chris")
p1.kids.append(p3)
p3.parents.append(p1)
print "My name is ", p1.name, "My first kids name is ",
p1.kids[0].name
class Job():
name = ""
employees = []
def __init__(self, name) :
self.name = name
j1 = Job("professor")
j1.employees = []
# This was added after class.
p1.has = j1
j1.employees.append(p1)
print p1.has.name, j1.employees[0].name
Dr. Philip Cannata
5
Code from September 17, 2013 Lecture
class Person(object):
_registry = [] # _registry starts off as an empty list.
name = ""
amount = 0
def __init__(self, name, amount):
self._registry.append(self) # Each instance of Person is added to _registry.
self.name = name
self.amount = amount
def exchange(self, p, amnt) :
self.amount -= amnt
p.amount += amnt
# Behavior or Method
p1, p2, p3, p4 = Person('tom', 1000), Person('jerry', 2000), Person('phineas', 3000), Person('ferb', 4000)
for p in Person._registry:
print p.name + ", " + str(p.amount) , # The comma at the end of the print statement causes all to print on one line.
def transfer(p1, p2, amnt) :
p1.amount -= amnt # Fill in these 2 lines for Homework 1. Note, the “transfer” function
p2.amount += amnt # requires no return statement.
transfer(p1, p2, 50)
transfer(p3, p4, 50)
print
for p in Person._registry:
print p.name + ", " + str(p.amount) ,
Dr. Philip Cannata
# More on Next Page
6
Code from September 17, 2013 Lecture
p1.exchange(p2, 50)
print
for p in Person._registry:
print p.name + ", " + str(p.amount) ,
p10 = Person("me", "you")
print
print p10._registry
print
print p1._registry
class MeekPerson(Person) :
def __init__(self, name, amount):
self._registry.append(self) # Each instance of Person is added to _registry.
self.name = name
self.amount = amount
def exchange(self, p, amnt) :
self.amount -= 2*amnt
p.amount += 2*amnt
m1 = MeekPerson("snoopy", 10000)
p6 = Person("charlie", 20000)
m1.exchange(p6,50)
print
for p in Person._registry:
print p.name + ", " + str(p.amount) ,
Dr. Philip Cannata
# Dynamic Binding will be done here to choose the right method.
7
class LinkedList() :
head = None
tail = None
size = 0
def cons(self, val) :
n = Node(val)
self.size+=1
if self.head == None :
self.head = n
self.tail = n
else :
n.next = self.head
self.head = n
return self
def car(self) :
return self.head.element
def cdr(self) :
l = self
if self.size > 0 :
l.head = l.head.next
l.size -= 1
else :
l.head, l.tail = None, None
return l
Dr. Philip Cannata
def __str__(self):
result = "'("
current = self.head
for i in range(self.size+1):
if current != None:
result += str(current.element)
if current.next != None :
result += ",
current = current.next
else:
result += ")" # Insert the closing ] in the string
return result
# Return an iterator for a linked list
def __iter__(self): # To be discussed in Section 18.3
return LinkedListIterator(self.head)
# The Node class
class Node:
def __init__(self, element):
self.element = element
self.next = None
class LinkedListIterator: def __init__(self, head):
self.current = head
def next(self):
if self.current == None:
raise StopIteration
else:
element = self.current.element
self.current = self.current.next
return element
8
Notables in LinkedList History
Aristotle
Categories and Syllogism
Object Oriented Concepts and Syllogistic
Logic.
Euclid
5 axioms of Geometry in the
“The Elements”
“The Elements” was responsible for the
notion of Certainty until the discovery of
non-Euclidian Geometry in the 19th
Century.
Gottlob Frege
Modern mathematical logic
Propositional Calculus and Predicate
Calculus
Giuseppe Peano
The principles of arithmetic,
presented by a new method.
First attempt at an axiomatization of
mathematics/arithmetic.
Georg Cantor
Theory of sets, sizes of Infinity,
and paradoxes.
Mathematics can be axiomatized using set
theory.
David Hilbert, Alfred
Whitehead, and
Bertrand Russell
Principia Mathematica
A 30 year attempt to restore Certainty to
mathematics by formalizing it using set
theory and logic and to prove that
mathematics is “consistent”.
Thoralf Skolem
Primitive Recursive Functions:
A reaction to the works of Cantor, Hilbert,
Whitehead and Russell in which the
notion of Infinity is abandoned.
Dr. Philip Cannata
9
Notables in LinkedList History
Kurt Gödel
First Incompleteness
Theorem
In any formal system capable of expressing primitive
recursive functions/arithmetic the statement “I am a
statement for which there is no proof” can be generated.
Second Incompleteness
Theorem
No formal system capable of expressing primitive
recursive functions/arithmetic can prove its own
consistency.
Restored the notion of Certainty but in a manner very different from that envisioned by Hilbert,
Whitehead and Russell.
Alonso
Church
Alan Turing
ChurchTuring Thesis
Haskell
Currie
Dr. Philip
Cannata
Recursive Functions
Functions which are defined for every input. Infinity returns.
Lambda Calculus
A language for defining functions and function application
inspired by Gödel's recursive functions.
Undecidability of
equivalence
There is no algorithm that takes as input two lambda
expressions and determines if they are equivalent.
Turing Machine and
Halting Problem
Created a theoretical model for a machine, (Turing machine),
that could carry out calculations from inputs. There is in
general no way to tell if it will halt (undecidability of
halting.)
Recursive Functions = Effectively Computable = Computational Completeness =
calculable on a Turing machine = Turing-Complete (e.g., Lambda Calculus).
For more information see http://www.cs.utexas.edu/~ear/cs341/automatabook/
Combinator Logic
Developed a Turing-Complete language based solely
upon function application of combinators.
10
Notables in LinkedList History
John McCarthy
The lisp programming language.
1960 paper: “Recursive Functions
of Symbolic Expressions and Their
Computation by Machine”, see
class calendar for a copy.
McCarthy took concepts from Gödel's incompleteness proof (substitution), lambda calculus (function
definition and function application) and combinator logic (car, cdr, and cons as primitive operations on
linked-lists)
(let ((l (cons 'a (cons 'b '())))) (let ((first (lambda (x) (car x)))) (first l)))
Dr. Philip Cannata
11
Aristotle’s syllogistic logic
If it’s raining outside, then the grass is wet.
Its raining outside
Therefore, the grass is wet.
If it’s raining outside, then the grass is wet.
The grass is wet.
Therefore, its raining outside.
Dr. Philip Cannata
Aristotle
Valid argument
Fallacy
12
Euclid’s “The Elements”
Five axioms (postulates)
Dr. Philip Cannata
Euclid
13
Propositional Logic
P
Q
P || Q
P
P
False
False
False
False
False
True
True
False
False
True
True
True
False
True
False
False
True
False
True
True
True
True
True
True
True
P
False
False
True
True
Q
PQ
False True
True True
False False
True True
Q
P<=>Q
P
Q
False
False
False
Dr. Philip Cannata
P && Q
P
False
False
True
False
True
False
True
False
False
True
True
True
Frege
14
Reasoning with Truth Tables
Proposition: ((P  Q)((P)Q))
(P  Q)
(P)
False False
False
True
False
False
False True
True
True
True
True
True
False
True
False
True
True
True
True
True
False
True
True
P
Q
If prop is True when all
variables are True:
P, Q
((PQ)((P)Q))
((P)Q)
((PQ)((P)Q))
Some True: prop is Satisfiable*
If they were all True: Valid / Tautology
A Truth
double turnstile
All False: Contradiction
(not satisfiable*)
*Satisfiability was the first known NP-complete (see next slide) problem
Dr. Philip Cannata
Frege
15
Reasoning with Truth Tables
Dr. Philip Cannata
16
Tautological Proof using Propositional Logic
It’s either summer or winter.
If it’s summer, I’m happy.
If it’s winter, I’m happy.
Is there anything you can uncompress from this?
The above statements can be written like this: ( (s  w) ^ (s -> h) ^ (w -> h) ) -> h
This is a Haskell proof of this Tautology
valid3 :: (Bool -> Bool -> Bool -> Bool) -> Bool
valid3 bf = and [ bf r s t| r <- [True,False],
s <- [True,False],
t <- [True,False]]
LOGIC> valid3 (\ s w h -> ((s || w) && (s ==> h) && (w ==> h)) ==> h)
True
Another form of a un-compression (proof):
Dr. Philip Cannata
( (p  q) ^ (¬p  r) ^ (¬q  r) ) -> r
( (p ^ ¬p)  (r ^ q) ^ (¬q  r) ) -> r
(F  (q ^ ¬q)  r) -> r
r -> r
¬r  r
.: T
Frege
17
Peano's Axioms
1. Zero is a number.
2. If a is a number, the successor of a is a number.
3. zero is not the successor of a number.
4. Two numbers of which the successors are equal are themselves
equal.
5. (induction axiom.) If a set S of numbers contains zero and also
the successor of every number in S, then every number is in S.
Peano's axioms are the basis for the version of number theory
known as Peano arithmetic.
Dr. Philip Cannata
Peano
18
Peano's Arithmetic
Dr. Philip Cannata
Peano
19
Cantor Diagonalization
Create a new number from the diagonal by adding 1 and changing
10 to 0.
The above example would give .960143…
Now try to find a place for this number in the table above, it can’t
be the first line because 8 != 9, it can’t be the second line because
5 != 6, etc. to infinity. So this line isn’t in the table above and
therefore was not counted.  The real numbers are not countable.
Dr. Philip Cannata
Cantor
20
Set Theory Paradoxes
Suppose there is a town with just one barber, who is male. In this town, every man keeps himself
clean-shaven, and he does so by doing exactly one of two things:
shaving himself; or
going to the barber.
Another way to state this is that "The barber is a man in town who shaves all those, and only
those, men in town who do not shave themselves."
From this, asking the question "Who shaves the barber?" results in a paradox because according
to the statement above, he can either shave himself, or go to the barber (which happens to be
himself). However, neither of these possibilities is valid: they both result in the barber shaving
himself, but he cannot do this because he only shaves those men "who do not shave themselves".
Dr. Philip Cannata
Cantor and Russell
21
Primitive Recursive Functions and Arithmetic
(see “A Profile of Mathematical Logic” by Howard Delong – pages 152 – 160)
A Sequence of Functions from definitions on DeLong, page 157:
Book notation
Relation notation
Arithmetic notation
f1(x) = x’
(x (+ x 1))
f1 is the successor
function
f2(x) = x
(x x)
f2 is the identity
function with i = 1
f3(y, z, x) = z
(y z x z)
f3 is the identity
function with i = 2
f4(y, z, x) = f1(f3(y,z,x))
(y z x ((x (+ x 1)) (y z x z)))
f4 is defined by
substitution for f1 and f3
This is how you would do this in lisp
(let ((f1 (lambda (x) (+ x 1))) (f3 (lambda (y z x) z))) (let ((f4 (lambda (y z x) (f1 (f3 y z x))))) (f4 2 4 6)))
f5(0, x) = f2(x)
f5(y’, x) = f4(y, f5(y,x), x)
(0 x ( x x))
(not doable yet)
f5 is defined by recursion
and f2 and f4
f5 is primitive recursive addition
(let ((f1 (lambda (x) (+ x 1))) (f2 (lambda (x) x)) (f3 (lambda (y z x) z))) (let ((f4 (lambda (y z x) (f1 (f3 y z x))))) (letrec ((f5 (lambda (a b) (if
(= a 0) (f2 b) (f4 (- a 1) (f5 (- a 1) b) b))))) (f5 2 3))))
Dr. Philip Cannata
Skolem
22
Gödel Numbering
1
3
5
7
9
11
13
17
19
23
‘0’
‘’’
‘-’
‘=>’
‘V’
‘(‘
‘)
‘x’
‘y’
‘z’
29
31
37
41
43
47
53
…
‘=‘
‘+’
‘.’
‘x1’
‘y1’
‘z1’
‘z2’
…
1 = (0)’ = 211 x 31 x 513 x 73
Dr. Philip Cannata
Gödel
23
Lambda Calculus
Lambda Calculus
x.x
s.(s s)
func.arg.(func arg)
Examples in python:
print (lambda x : x) (lambda s : s)
print (lambda s : (s) (s)) (lambda x : x)
print (lambda func, arg : (func) (arg)) ((lambda x : x + 3), 4)
def identity = x.x
def self_apply = s.(s s)
def apply = func.arg.(func arg)
def select_first = first.second.first
def select_second =first.second.second
def cond= e1.e2.c.((c e1) e2)
def true=select_first
def false=select_second
def not= x.(((cond false) true) x)
Or def not= x.((x false) true)
def and= x.y.(((cond y) false) x)
Or def and= x.y.((x y) false)
def or= x.y.(((cond true) y) x)
Or def or= x.y.((x true) y)
Dr. Philip Cannata
Church
24
Turing Machine
Dr. Philip Cannata
Turing
25
Combinator Logic
A function is called primitive recursive if there is a finite sequence of functions ending with f
such that each function is a successor, constant or identity function or is defined from preceding
functions in the sequence by substitution or recursion.
Combinators
s f g x = f x (g x)
k x y
= x
b f g x = f (g x)
c f g x = f x g
y f
= f (y f)
cond p f g x = if p x then f x else g x
-- Some Primitive Recursive Functions on Natural Numbers
addition x z = y (b (cond ((==) 0) (k z)) (b (s (b (+) (k 1))
) (c b pred))) x
multiplication x z = y (b (cond ((==) 0) (k 0)) (b (s (b (pradd1) (k z)) ) (c b pred))) x
exponentiation x z = y (b (cond ((==) 0) (k 1)) (b (s (b (prmul1) (k x)) ) (c b pred))) z
factorial x
= y (b (cond ((==) 0) (k 1)) (b (s (prmul1)
) (c b pred))) x
No halting problem here but not Turing complete either
Implies recursion or bounded loops, if-then-else constructs and run-time stack.
see the BlooP language in
Dr. Philip Cannata
Haskell Currie
26
John McCarthy’s Takeaways
-- Primitive Recursive Functions on Lists are more interesting than Primitive Recursive Functions on
Numbers
length x = y (b (cond ((==) []) (k 0)) (b (s (b (+) (k 1)) ) (c b cdr))) x
sum x = y (b (cond ((==) []) (k 0)) (b (s (b (+) (car)) ) (c b cdr))) x
product x = y (b (cond ((==) []) (k 1)) (b (s (b (*) (car)) ) (c b cdr))) x
map f x = y (b (cond ((==) []) (k [])) (b (s (b (:) (f) ) ) (c b cdr))) x
-- map (\ x -> (car x) + 2) [1,2,3] or
-- map (\ x -> add (car x) 2) [1,2,3]
-- A programming language should have first-class functions as (b p1 p2 . . . Pn), substitution, lists with car,
cdr and cons operations and recursion.
car (f:r) = f
cdr (f:r) = r
cons is : op
John’s 1960 paper: “Recursive Functions of Symbolic Expressions
and Their Computation by Machine” – see copy on class calendar.
Dr. Philip Cannata
McCarthy
27
Stack and Queue
class Stack(LinkedList):
def push(self, e):
self.addFirst(e)
def pop(self):
return self.removeFirst()
def peek(self):
return self.car()
class Queue(LinkedList):
def enqueue(self, e):
self.cons(e)
def dequeue(self):
return self.removeLast()
print "Stack test"
Dr. Philip Cannata
28
Stack Example
def calc(expr):
s1 =Stack()
for s in expr:
if s == ")":
e = ""
for i in range(s1.getSize()):
v = s1.pop()
if v == "(":
break
else:
e += str(v)
# print e, e[::-1], eval(e[::-1])
e = eval(e[::-1]) # Comment for no extra credit
s1.push(str(e)[::-1]) # Comment for no extra credit
# s1.push(eval(e)) # Uncomment for no extra credit
# print s1
else:
s1.push(s)
# return s1.pop()
# Uncomment for no extra credit
return s1.pop()[::-1] # Comment for no extra credit
print eval("(((12+33.3)*(1.4*701))/(2.2-1.1))")
print calc("(((12+33.3)*(1.4*701))/(2.2-1.1))")
print eval("(((2+3)*(4*7))*2)")
print calc("(((2+3)*(4*7))*2)"
Dr. Philip Cannata
29
Bubble Sort
l = [i for i in range(10, 0, -1)]
# or [i for i in range(10)][::-1]
cnt = len(l) - 1
total = 0
while cnt > 0:
swap = 0
i=0
for e in l:
if i + 1 < len(l) and l[i] > l[i+1]:
l[i], l[i+1] = l[i+1], l[i]
swap += 1
i += 1
total += swap
cnt -= 1
print total
Dr. Philip Cannata
30
Merge Sort
Dr. Philip Cannata
31
Merge Sort
global swaps
swaps = 0
def mergeSort(list):
if len(list) > 1:
# Merge sort the first half
# firstHalf = list[ : len(list) // 2] This is what the book does.
firstHalf = [i for i in list[: len(list) // 2]] # This uses list
comprehension.
mergeSort(firstHalf)
# Merge sort the second half
# secondHalf = list[len(list) // 2 : ]This is what the book does.
secondHalf = [i for i in list[len(list) // 2 :]] # This uses list
comprehension.
mergeSort(secondHalf)
# Merge firstHalf with secondHalf into list
merge(firstHalf, secondHalf, list)
# Merge two sorted lists */
def merge(list1, list2, temp):
global swaps
current1 = 0 # Current index in list1
current2 = 0 # Current index in list2
current3 = 0 # Current index in temp
while current1 < len(list1) and current2 < len(list2):
if list1[current1] < list2[current2]:
temp[current3] = list1[current1]
current1 += 1
current3 += 1
swaps += 1
else:
temp[current3] = list2[current2]
current2 += 1
current3 += 1
swaps += 1
while current1 < len(list1):
temp[current3] = list1[current1]
current1 += 1
current3 += 1
swaps += 1
while current2 < len(list2):
temp[current3] = list2[current2]
current2 += 1
current3 += 1
swaps += 1
Dr. Philip Cannata
32
Bubble and Merge Sort Efficiency
Dr. Philip Cannata
33
List Comprehension and Lambda Expressions for Propositional
Logic
It's Monday.
If it's Monday, the next day is Tuesday.
If the next day is Tuesday, then I will win a thousand dollars.
# m stands for "it's Monday", t stands for "the next day is Tuesday", and d stands for "I will win a thousand dollars"
print [(lambda (m, t, d) : not (m and (not m or t) and (not t or d)) or d) ((i, j, k)) for i in (False, True) for j in (False,
True) for k in (False, True)]
Dr. Philip Cannata
34
List Comprehension and Lambda Expressions and SQL
emp = (('EMPNO', 'ENAME', 'JOB', 'MGR', 'HIREDATE', 'SAL', 'COMM', 'DEPTNO'), (7369, 'SMITH', 'CLERK', 7902, '1980-12-17
00:00:00', 800.0, 0.0, 20), (7499, 'ALLEN', 'SALESMAN', 7698, '1981-02-20 00:00:00', 1600.0, 300.0, 30), (7521, 'WARD', 'SALESMAN',
7698, '1981-02-22 00:00:00', 1250.0, 500.0, 30), (7566, 'JONES', 'MANAGER', 7839, '1981-04-02 00:00:00', 2975.0, 0.0, 20), (7654,
'MARTIN', 'SALESMAN', 7698, '1981-09-28 00:00:00', 1250.0, 1400.0, 30), (7698, 'BLAKE', 'MANAGER', 7839, '1981-05-01 00:00:00',
2850.0, 0.0, 30), (7782, 'CLARK', 'MANAGER', 7839, '1981-06-09 00:00:00', 2450.0, 0.0, 10), (7788, 'SCOTT', 'ANALYST', 7566, '198212-09 00:00:00', 3000.0, 0.0, 20), (7839, 'KING', 'PRESIDENT', 0, '1981-11-17 00:00:00', 5000.0, 0.0, 10), (7844, 'TURNER',
'SALESMAN', 7698, '1981-09-08 00:00:00', 1500.0, 0.0, 30), (7876, 'ADAMS', 'CLERK', 7788, '1983-01-12 00:00:00', 1100.0, 0.0, 20),
(7900, 'JAMES', 'CLERK', 7698, '1981-12-03 00:00:00', 950.0, 0.0, 30), (7902, 'FORD', 'ANALYST', 7566, '1981-12-03 00:00:00', 3000.0,
0.0, 20), (7934, 'MILLER', 'CLERK', 7782, '1982-01-23 00:00:00', 1300.0, 0.0, 10))
dept = (('DEPTNO', 'DNAME', 'LOC'), (10, 'ACCOUNTING', 'NEW YORK'), (20, 'RESEARCH', 'DALLAS'), (30, 'SALES',
'CHICAGO'), (40, 'OPERATIONS', 'BOSTON'))
print[ (i[1], j[1]) for i in emp for j in dept if i[7] == j[0] ]
İs similar to “select
Dr. Philip Cannata
ename, dname from emp join dept on( emp.deptno = dept.deptno)”
in SQL
35