Algorithm算法代写代考

Microsoft PowerPoint – CS332-Lec09-ann BU CS 332 – Theory of Computation Lecture 9: • Turing Machines Reading: Sipser Ch 3.1, 3.3 Mark Bun February 22, 2021 Turing Machines – Motivation We’ve seen finite automata as a restricted model of  computation Finite Automata / Regular Expressions • Can do simple pattern matching (e.g., substrings), check parity,  addition • Can’t perform unbounded counting • Can’t recognize palindromes Somewhat more powerful (not in this course): Pushdown Automata / Context‐Free Grammars • Can count and compare, parse math expressions • Can’t recognize  𝑎 𝑏 𝑐 𝑛 0 2/22/2021 CS332 ‐ Theory of Computation 2 Turing Machines – Motivation Goal: Define a model of computation that is 1) General purpose. Captures all algorithms that can be  implemented in any programming language. 2) Mathematically simple. We can hope to prove that  things are not computable in this model. 2/22/2021 […]

PowerPoint Presentation BU CS 332 – Theory of Computation Lecture 17: • Mapping Reductions Reading: Sipser Ch 5.3 Mark Bun March 21, 2021 Reductions A reduction from problem 𝐴 to problem 𝐵 is an algorithm for problem 𝐴 which uses an algorithm for problem 𝐵 as a subroutine If such a reduction exists, we say

b’0f55c2712963686b94d6b6f85888a4c29ae19f’ blob 3827�#pragma once #include #include /// size of an RSA key const int RSA_KEYSIZE = 2048; /// size of an AES key const int AES_KEYSIZE = 32; /// size of an AES initialization vector const int AES_IVSIZE = 16; /// Size of blocks that get encrypted const int AES_BLOCKSIZE = 1024; /// Load an

PowerPoint Presentation BU CS 332 – Theory of Computation Lecture 12: • More on NTMs • Church-Turing Thesis • Decidable Languages Reading: Sipser Ch 3.2, 4.1 Mark Bun March 3, 2021 Nondeterministic TMs At any point in computation, may nondeterministically branch. Accepts iff there exists an accepting branch. Transition function 𝛿𝛿 ∶ 𝑄𝑄 × Γ

Microsoft PowerPoint – CS332-Lec12-ann BU CS 332 – Theory of Computation Lecture 12: • More on NTMs • Church‐Turing Thesis • Decidable Languages Reading: Sipser Ch 3.2, 4.1 Mark Bun March 3, 2021 Nondeterministic TMs At any point in computation, may nondeterministically branch. Accepts iff there exists an accepting branch. Transition function  3/3/2021 CS332 ‐ Theory of Computation 2 Nondeterministic TMs An NTM  accepts input  if when run on  it accepts on  at least one computational branch  An NTM  is a decider if on every input, it halts on every computational branch 3/3/2021 CS332 ‐ Theory of Computation 3 Nondeterministic TMs Ex. NTM decider for  is a binary number representing  the product of two integers  On input  : 1. Nondeterministically guess  2. Accept if  , reject otherwise.

PowerPoint Presentation BU CS 332 – Theory of Computation Lecture 24: • More NP-completeness • Space complexity (?) Reading: Sipser Ch 7.4-7.5, 8.1-8.2 Mark Bun April 26, 2021 Polynomial-time reducibility Definition: A function 𝑓𝑓:Σ∗ → Σ∗ is polynomial-time computable if there is a polynomial-time TM 𝑀𝑀 which, given as input any 𝑤𝑤 ∈ Σ∗, halts

PowerPoint Presentation BU CS 332 – Theory of Computation Lecture 25: • Final review Reading: Sipser Ch 7.1-8.2, 9.1 Mark Bun April 28, 2021 Final Topics 4/28/2021 CS332 – Theory of Computation 2 Everything from Midterms 1 and 2 • Midterm 1 topics: DFAs, NFAs, regular expressions, distinguishing set method (more detail in lecture 8