xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

图灵机代写-COMP4141

时间：2021-04-30

COMP4141 Theory of Computation

Course recap

Paul Hunter

CSE, UNSW

April 21, 2021

Final exam

Final exam:

Wednesday, May 12

Available 10am AEST

Due: Thursday, May 13, 10am AEST

Submission via give: multiple submissions ok - last one before

due date counts

Lateness: 25% per 15 minutes or part thereof.

Worth 50% of overall grade. Must achieve 40% to pass

course.

Final exam

10 questions:

6 questions on Week 1-5 content;

4 questions on Week 7-10 content

Proof-based questions (as with Assignments 1,2, 3b, 4)

Assessment based on understanding and ability

Any passive (i.e. existing) material acceptable – properly

referenced

Any material taken from active sources is in breach of Student

Conduct and will be subject to plagiarism review

Week 1 recap

Formal languages

Alphabets, Strings/words, Languages

Recursive definitions

Deterministic Finite Automata (DFA)

(Q,Σ, δ, q0,F )

L(A)

Non-deterministic Finite Automata (NFA)

Non-determinism

-transitions

Equivalence of DFAs and NFAs

Subset construction

Week 2 recap

Regular expressions

Definition, L(R)

Equivalence to DFAs

Pumping Lemma

Myhill-Nerode theorem

Need to know

Regular expressions

Definition, L(R)

How to do proofs with them

Finding R or L such that L = L(R)

Pumping Lemma - how to use it, limitations

Myhill-Nerode theorem - how to use it, limitations

Week 3 recap

Context-free languages

Context-free grammars

Derivations, parse trees, ambiguity

Pushdown automata

Pumping lemma for CFLs

Closure properties of CFLs

Chomsky normal form

Non-emptiness and word acceptance algorithms

CKY algorithm

Chomsky hierarchy

Need to know

CFGs and PDAs: Definitions, how to use

Pumping lemma: How to use

Algorithms for CFLs

Grammars for

Type 3: Regular languages,

Type 2: CFLs, and

Type 0: Recursively enumerable languages.

Weeks 4 and 5 recap

Turing Machines, Recursive and Recursively Enumerable languages

Turing Machines

Definitions, accept vs decide

Variants: stay-put, semi-infinite tape, multi-tape,

non-determinism

Enumerators

Universal Turing Machine

Rec, RE, coRE

Rec = RE ∩ coRE

Encodings

Reductions: many-one vs Turing

Undecidable problems: ATM = {〈M,w〉 : M accepts w}

Rice’s theorem

Need to know

TMs: Definitions, how they work

Many-one reductions: Definitions, how to use

Oracles

Rice’s theorem: When it applies

Week 7 recap

Resource-bounded computation:

TIMEt(n)

NTIMEt(n)

SPACEt(n)

NSPACEt(n)

Time and Space-hierarchy theorems

P and NP

Need to know

How to use the Space/Time-hierarchy theorems

Class definitions and relation to other classes

How to do NP-completeness proofs

Week 8 recap

NP-completeness proofs

SAT (Cook’s theorem)

3SAT, 4SAT

Vertex Cover

Clique

Hamiltonian Path, Hamiltonian Cycle

Travelling Salesman

Subset Sum

Integer Linear Programming, 0-1 ILP

3COL

Need to know

Reduction strategies for NP-completeness proofs

Generalization

Problem restatement

Gadget construction

Week 9 recap

Complexity classes:

coNP, Validity

EXPTIME, Bounded Halt

PSPACE, QBF (QSAT)

L, NL, ≤L, Path

Complexity classes

P

NP

NP-c

coNP

PSPACE = NPSPACE

EXPTIME

NL = coNL

L

Complexity summary

Class Characterization Problem Notes

P

⋃

k∈NTIME(n

k) Horn-SAT

NP

⋃

k∈NNTIME(n

k) SAT, 3SAT Poly. verifiable

PSPACE

⋃

k∈N SPACE(n

k) QBF = NPSPACE

coNP Languages L such

that L ∈ NP

Validity Poly. refutable

EXPTIME

⋃

k∈NTIME(2

nk ) Bounded-halt 6= P

L SPACE(log n) Und. Path

NL NSPACE(log n) Path, 2SAT = coNL

Need to know

Class definitions and relation to other classes

Consequences of Savitch’s theorem

PSPACE-completeness proofs

How to do logspace reductions

Week 10 recap

Oracle machines

Alternation

Polynomial-time hierarchy

Probabilistic computation

Probabilistic Turing Machines

Probabilistic complexity classes: PP, BPP, RP, ZPP.

PΣ1P = NP Π1P = coNP

∆2P = P

NP = PcoNP

Σ2P = NP

NP Π2P = coNP

NP

P∆3P = P

Σ2P

Σ3P Π3P

...

PSPACE

Need to know

Oracle machines: Definition, how to use

Alternation: Definition, how to use

Probabilistic computation: Definition, how to use

Relation between Alternation complexity classes and classical

complexity classes

Probabilistic complexity classes: PP, BPP, RP, ZPP

学霸联盟

Course recap

Paul Hunter

CSE, UNSW

April 21, 2021

Final exam

Final exam:

Wednesday, May 12

Available 10am AEST

Due: Thursday, May 13, 10am AEST

Submission via give: multiple submissions ok - last one before

due date counts

Lateness: 25% per 15 minutes or part thereof.

Worth 50% of overall grade. Must achieve 40% to pass

course.

Final exam

10 questions:

6 questions on Week 1-5 content;

4 questions on Week 7-10 content

Proof-based questions (as with Assignments 1,2, 3b, 4)

Assessment based on understanding and ability

Any passive (i.e. existing) material acceptable – properly

referenced

Any material taken from active sources is in breach of Student

Conduct and will be subject to plagiarism review

Week 1 recap

Formal languages

Alphabets, Strings/words, Languages

Recursive definitions

Deterministic Finite Automata (DFA)

(Q,Σ, δ, q0,F )

L(A)

Non-deterministic Finite Automata (NFA)

Non-determinism

-transitions

Equivalence of DFAs and NFAs

Subset construction

Week 2 recap

Regular expressions

Definition, L(R)

Equivalence to DFAs

Pumping Lemma

Myhill-Nerode theorem

Need to know

Regular expressions

Definition, L(R)

How to do proofs with them

Finding R or L such that L = L(R)

Pumping Lemma - how to use it, limitations

Myhill-Nerode theorem - how to use it, limitations

Week 3 recap

Context-free languages

Context-free grammars

Derivations, parse trees, ambiguity

Pushdown automata

Pumping lemma for CFLs

Closure properties of CFLs

Chomsky normal form

Non-emptiness and word acceptance algorithms

CKY algorithm

Chomsky hierarchy

Need to know

CFGs and PDAs: Definitions, how to use

Pumping lemma: How to use

Algorithms for CFLs

Grammars for

Type 3: Regular languages,

Type 2: CFLs, and

Type 0: Recursively enumerable languages.

Weeks 4 and 5 recap

Turing Machines, Recursive and Recursively Enumerable languages

Turing Machines

Definitions, accept vs decide

Variants: stay-put, semi-infinite tape, multi-tape,

non-determinism

Enumerators

Universal Turing Machine

Rec, RE, coRE

Rec = RE ∩ coRE

Encodings

Reductions: many-one vs Turing

Undecidable problems: ATM = {〈M,w〉 : M accepts w}

Rice’s theorem

Need to know

TMs: Definitions, how they work

Many-one reductions: Definitions, how to use

Oracles

Rice’s theorem: When it applies

Week 7 recap

Resource-bounded computation:

TIMEt(n)

NTIMEt(n)

SPACEt(n)

NSPACEt(n)

Time and Space-hierarchy theorems

P and NP

Need to know

How to use the Space/Time-hierarchy theorems

Class definitions and relation to other classes

How to do NP-completeness proofs

Week 8 recap

NP-completeness proofs

SAT (Cook’s theorem)

3SAT, 4SAT

Vertex Cover

Clique

Hamiltonian Path, Hamiltonian Cycle

Travelling Salesman

Subset Sum

Integer Linear Programming, 0-1 ILP

3COL

Need to know

Reduction strategies for NP-completeness proofs

Generalization

Problem restatement

Gadget construction

Week 9 recap

Complexity classes:

coNP, Validity

EXPTIME, Bounded Halt

PSPACE, QBF (QSAT)

L, NL, ≤L, Path

Complexity classes

P

NP

NP-c

coNP

PSPACE = NPSPACE

EXPTIME

NL = coNL

L

Complexity summary

Class Characterization Problem Notes

P

⋃

k∈NTIME(n

k) Horn-SAT

NP

⋃

k∈NNTIME(n

k) SAT, 3SAT Poly. verifiable

PSPACE

⋃

k∈N SPACE(n

k) QBF = NPSPACE

coNP Languages L such

that L ∈ NP

Validity Poly. refutable

EXPTIME

⋃

k∈NTIME(2

nk ) Bounded-halt 6= P

L SPACE(log n) Und. Path

NL NSPACE(log n) Path, 2SAT = coNL

Need to know

Class definitions and relation to other classes

Consequences of Savitch’s theorem

PSPACE-completeness proofs

How to do logspace reductions

Week 10 recap

Oracle machines

Alternation

Polynomial-time hierarchy

Probabilistic computation

Probabilistic Turing Machines

Probabilistic complexity classes: PP, BPP, RP, ZPP.

PΣ1P = NP Π1P = coNP

∆2P = P

NP = PcoNP

Σ2P = NP

NP Π2P = coNP

NP

P∆3P = P

Σ2P

Σ3P Π3P

...

PSPACE

Need to know

Oracle machines: Definition, how to use

Alternation: Definition, how to use

Probabilistic computation: Definition, how to use

Relation between Alternation complexity classes and classical

complexity classes

Probabilistic complexity classes: PP, BPP, RP, ZPP

学霸联盟