Tài liệu miễn phí Toán học

Toán học Môi trường Vật lý Sinh học Địa Lý Hoá học Nông - Lâm - Ngư Cơ khí - Chế tạo máy Tiếng Anh phổ thông Khoa học ứng dụng Nông - Lâm Kiến thức tổng hợp Giáo dục học Xã hội học

Tài liệu miễn phí Toán học

Download Tài liệu học tập miễn phí Toán học

Theory of Computation: Lecture 45

Theory of Computation: Lecture 45. The main topics covered in this lesson include: space complexity; computability; non-trivial semantic properties; post correspondence problem; Presburger arithmetic; the Gödel’s theorem; the Clay mathematical society;...

4/8/2023 4:26:12 PM +00:00

Theory of Computation: Lecture 44

Theory of Computation: Lecture 44. The main topics covered in this lesson include: space complexity; non-deterministic algorithm; non-deterministic LOGSPACE; highly non-deterministic program; the space requirements;...

4/8/2023 4:26:05 PM +00:00

Theory of Computation: Lecture 43

Theory of Computation: Lecture 43. The main topics covered in this lesson include: space complexity; Savatich’s theorem; non-deterministic algorithm; the initial configuration; the contents of the work tape and the machine is currently reading the i-th symbol on the work tape and the j-th symbol of the input;...

4/8/2023 4:25:57 PM +00:00

Theory of Computation: Lecture 42

Theory of Computation: Lecture 42. The main topics covered in this lesson include: space complexity; new complexity classes; interesting space complexity classes; non-deterministic analogue; Savatich’s theorem; polynomial time reducibility;...

4/8/2023 4:25:49 PM +00:00

Theory of Computation: Lecture 41

Theory of Computation: Lecture 41. The main topics covered in this lesson include: space complexity; generalized geography; polynomial time algorithm; algorithm requires polynomial space; the existentially quantified variables; the universally quantified variables;...

4/8/2023 4:25:42 PM +00:00

Theory of Computation: Lecture 40

Theory of Computation: Lecture 40. The main topics covered in this lesson include: true fully quantified boolean formula (TQBF); FORMULA-GAME; generalized geography; alternating quantified formula; combinatorial games;...

4/8/2023 4:25:35 PM +00:00

Theory of Computation: Lecture 39

Theory of Computation: Lecture 39. The main topics covered in this lesson include: space complexity; true fully quantified boolean formula (TQBF); prove that TQBF is PSPACE-complete; other PSPACE-complete problems; polynomial space;...

4/8/2023 4:25:29 PM +00:00

Theory of Computation: Lecture 38

Theory of Computation: Lecture 38. The main topics covered in this lesson include: relationship between space and time complexity; PSPACE; PSPACE-completeness and PSPACE-complete language; TQBF; non-trivial relationships; favorite complexity classes;...

4/8/2023 4:25:22 PM +00:00

Theory of Computation: Lecture 36

Theory of Computation: Lecture 36. The main topics covered in this lesson include: space complexity; deterministic space complexity; non-deterministic space complexity; examples of space efficient TMs; reachability problem; Savitch’s theorem;...

4/8/2023 4:25:09 PM +00:00

Theory of Computation: Lecture 35

Theory of Computation: Lecture 35. The main topics covered in this lesson include: Traveling Salesman Problem (TSP); the metric TSP; approximation algorithm and an approximation algorithm for the TSP problem; space complexity; the PCP theorem and hardness of approximation;...

4/8/2023 4:25:02 PM +00:00

Theory of Computation: Lecture 34

Theory of Computation: Lecture 34. The main topics covered in this lesson include: three versions of the TSP problem; an approximation algorithm for the TSP problem; space complexity; polynomial time algorithm; the euclidean TSP;...

4/8/2023 4:24:56 PM +00:00

Theory of Computation: Lecture 33

Theory of Computation: Lecture 33. The main topics covered in this lesson include: TSP problem; polynomial time algorithm; the subset sum problem; NP-completeness; multi-set of positive integers;...

4/8/2023 4:24:49 PM +00:00

Theory of Computation: Lecture 32

Theory of Computation: Lecture 32. The main topics covered in this lesson include: NP-completeness; review of NP-completeness results; hamiltonian path problem; the diamond shape structure; the satisfying assignments; vertex vover;...

4/8/2023 4:24:43 PM +00:00

Theory of Computation: Lecture 29-30

Theory of Computation: Lecture 29-30. The main topics covered in this lesson include: NP-completeness; Cook-Levin theorem; polynomial time reducible; conjunctive normal form (CNF); verification algorithm; independent sets;...

4/8/2023 4:24:36 PM +00:00

Theory of Computation: Lecture 28

Theory of Computation: Lecture 28. The main topics covered in this lesson include: the Cook-Levin theorem; polynomial time; propositional logic; algorithm computes a function in polynomial time; polynomial time reducibility;...

4/8/2023 4:24:28 PM +00:00

Theory of Computation: Lecture 27

Theory of Computation: Lecture 27. The main topics covered in this lesson include: satisfiability; verification algorithm; Cook-Levin theorem; non-deterministic Turing machine; non-deterministic polynomial time; schematic diagram;...

4/8/2023 4:24:19 PM +00:00

Theory of Computation: Lecture 26

Theory of Computation: Lecture 26. The main topics covered in this lesson include: NP-completness; satisfiability; Cook-Levin theorem; 3-colorable; translation algorithm; polynomial-time reducibility; non-deterministic turing machines;...

4/8/2023 4:24:12 PM +00:00

Theory of Computation: Lecture 25

Theory of Computation: Lecture 25. The main topics covered in this lesson include: verification algorithms; subsetsum problem; alternate characterization of NP; the P versus NP question; polynomial time reducibility; NP completeness; satisfiability; Cook-Levin theorem;...

4/8/2023 4:24:06 PM +00:00

Theory of Computation: Lecture 23

Theory of Computation: Lecture 23. The main topics covered in this lesson include: the class NP; polynomial time verifiers; examples of problems in NP; non-deterministic TM; non-deterministic polynomial time algorithm; polynomial time non-deterministic turing machies;...

4/8/2023 4:23:59 PM +00:00

Theory of Computation: Lecture 22

Theory of Computation: Lecture 22. The main topics covered in this lesson include: non-deterministic time; the class P; the class NP; time complexity classes; time deterministic single tape TM; polynomial time algorithm; adjacency matrix; adjacency list; non-deterministic analog;...

4/8/2023 4:23:48 PM +00:00

Theory of Computation: Lecture 21

Theory of Computation: Lecture 21. The main topics covered in this lesson include: big-Oh notation; little-o notation; time complexity classes; non-deterministic TMs; the class P; resource bounded computations; non-deterministic finite automata; non-deterministic pushdown automata;...

4/8/2023 4:23:37 PM +00:00

Theory of Computation: Lecture 20

Theory of Computation: Lecture 20. The main topics covered in this lesson include: incompressible strings; minimal length descriptions; descriptive complexity; complexity theory; big O notation and small o notation;...

4/8/2023 4:23:30 PM +00:00

Theory of Computation: Lecture 19

Theory of Computation: Lecture 19. The main topics covered in this lesson include: a definition of information; minimal length descriptions; descriptive complexity; Kolmogorov complexity and 2 Kolmogorov-Chaitin complexity; optimality of definition;...

4/8/2023 4:23:23 PM +00:00