Readme, Course Information, Course Description, Dates, Photos Fun, Your Marks (4111,5111) Forum, Class
Topics | Slides | Videos | Steps | Notes | Questions | Solutions | Tests |
Quantifiers (Take up Exam Question.) | |||||||
Turing Machines | |||||||
Models of Computability | |||||||
Complexity Classes | |||||||
Diagitization & Uncomputability | |||||||
Reductions For Uncomputability | |||||||
No Proof System for Number Theory | |||||||
NP-completeness | (sols) | ||||||
Other Possibilities |
Request:
Jeff tends to talk too fast. Please help him go
pole pole slowly.
Texts:
Introduction: (ppt)
Quantifiers:
(Steps,
ppt,
Questions)
(Before a student can understand or prove anything in mathematics, it
is essential to first be able to res present it in first order
logic. Hence, Jeff reviews it in each of his courses.)
Turing Machines:
(ppt,
Questions)
(Historic and mathematical ways of modeling machines for computing.)
Other Models of Computability:
(ppt,
Cook,
Questions)
(More Historic ways of modeling machines for computing.)
Complexity Classes:
(ppt,
Questions)
(We classify computational problems based on the amount of resources
used to compute them.)
Diagonization & Uncomputability:
(ppt,
Cook,
Questions)
(There are more real numbers than fractions and the same number of
fractions as integers.)
(Some computational problems are solved by NO algorithms.)
Reductions For Uncomputability:
(ppt,
Cook,
Questions) (3*1.5hrs)
(Knowing that some computational problems are hard, we prove that
others are.)
No Proof System for Number Theory:
(ppt)
(Godel proved that there is no mechanical way of proving everything in
mathematics.)
NP-completeness:
(ppt,
pdf,
Questions)
(Reductions involve writing an algorithm for one problem from that for
another. NP-Completeness give strong evidence that most search
problems that industry cares about are believed to not have poly-time
algorithms.)
Other Possibilities:
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.