CS21 Decidability and Tractability
Lecture 1 January 3, 2024
January 3, 2024 CS21 Lecture 1 1
• administrative stuff
Copyright By PowCoder代写 加微信 powcoder
• motivation and overview of the course
• problems and languages
• Finite Automata
January 3, 2024 CS21 Lecture 1 2
Administrative Stuff
• Text: Introduction to the Theory of Computation – 3rd Edition by
• Lectures self-contained
• Weekly homework
– collaboration in small groups encouraged
– separate write-ups (clarity counts)
• Midterm and final
– indistinguishable from homework except cumulative, no collaboration allowed
January 3, 2024 CS21 Lecture 1 3
Administrative Stuff • No programming in this course
• Things I assume you are familiar with:
– programming and basic algorithms – asymptotic notation “big-oh”
– sets, graphs
– proofs, especially induction proofs
January 3, 2024 CS21 Lecture 1 4
Motivation/Overview • This course: introduction to
Theory of Computation
– what does it mean? – why do we care?
– what will this course cover?
January 3, 2024 CS21 Lecture 1 5
Motivation/Overview
Computability and Complexity
January 3, 2024
Algorithms
Systems and Software Design and Implementation
CS21 Lecture 1
Motivation/Overview
• At the heart of programs lie algorithms
• To study algorithms we must be able to speak mathematically about:
– computational problems – computers
– algorithms
January 3, 2024 CS21 Lecture 1 7
Motivation/Overview
• You might imagine that in principle
– for each problem we would have an algorithm – the algorithm would be the fastest possible
(requires proof that no others are faster)
January 3, 2024 CS21 Lecture 1 8
Motivation/Overview
• Our world (fortunately) is more interesting: – not all problems have algorithms (we will
prove this)
– for many problems we know embarrassingly little about what the fastest algorithm is
• multiplying two integers
• factoring an integer into primes
• determining shortest tour of given n cities
– for certain problems, fast algorithms would change the world (we will see this)
January 3, 2024 CS21 Lecture 1 9
Motivation/Overview
computational problems, models of computation, characterizations of the
problems they solve, and limits on their power
Finite Automata and Regular Languages and Context Free Grammars
January 3, 2024 CS21 Lecture 1 10
Motivation/Overview
Turing Machines, and limits on their power (undecidability), reductions between
Part Three:
complexity classes P and NP, NP- completeness, limits of efficient
computation
January 3, 2024 CS21 Lecture 1 11
Main Points of Course
(un)-decidability
Some problems have no algorithms!
(in)-tractability
Many problems that we’d like to solve
probably have no efficient algorithms! (no one knows how to prove this yet…) January 3, 2024 CS21 Lecture 1 12
What is a problem?
• Some examples:
– given n integers, produce a sorted list
– given a graph and nodes s and t, find the (first)
shortest path from s to t
– given an integer, find its prime factors
• problem associates each input to an output • input and output are strings over a finite
alphabet Σ
January 3, 2024 CS21 Lecture 1 13
What is a problem?
• A problem is a function:
• Simple. Can we make it simpler?
• Yes. Decision problems:
f:Σ* → {accept, reject}
• Does this still capture our notion of problem, or is it too restrictive?
January 3, 2024 CS21 Lecture 1 14
What is a problem?
• Example: factoring:
– given an integer m, find its prime factors
ffactor: {0,1}* → {0,1}* • Decision version:
– given 2 integers m,k, accept iff m has a prime factor p < k
• Can use one to solve the other and vice versa. True in general (homework).
January 3, 2024 CS21 Lecture 1 15
What is a problem?
• For most of this course, a problem is a decision problem:
f:Σ* → {accept, reject}
• Equivalent notion: language
the set of strings that map to “accept”
• Example: L = set of pairs (m,k) for which m
has a prime factor p < k
January 3, 2024 CS21 Lecture 1 16
What is computation?
input machine • reject
• loop forever
• the set of strings that lead to “accept” is the language recognized by this machine
• if every other string leads to “reject”, then this language is decided by the machine
January 3, 2024 CS21 Lecture 1 17
Terminology
• finite alphabet Σ : a set of symbols
• language L ⊆ Σ∗: subset of strings over Σ
• a machine takes an input string and either
– accepts, rejects, or
– loops forever
• a machine recognizes the set of strings
that lead to accept
• a machine decides a language L if it
accepts 𝑥 ∈ 𝐿 and rejects 𝑥 ∉ 𝐿
January 3, 2024 CS21 Lecture 1 18
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com