Theoretical Computer Science 2022 - История изменений

Bbauwens в 18:11, 9 февраля 2023

2023-02-09T18:11:38Z

← Предыдущая версия		Версия от 18:11, 9 февраля 2023
Строка 44:		Строка 44:
	\|\| 27.04 \|\| Projects \|\|		\|\| 27.04 \|\| Projects \|\|
	\|}		\|}



			= Homeworks =

			[https://www.dropbox.com/s/uhi35jl4ofm1ws1/1_HW.pdf?dl=0 HW1 automata]

			[https://www.dropbox.com/s/j4o5bqz0o1r171o/2_HW.pdf?dl=0 HW2 computability]

			[https://www.dropbox.com/s/4mgniv56j9qg2c8/3_HW.pdf?dl=0 HW3 P, NP, hierarchy theorems, circuits]

			[https://www.dropbox.com/s/w3d6hetx65se8hx/4_HW.pdf?dl=0 HW4 NP and PSPACE completeness]

			[https://www.dropbox.com/s/q9afprj9wwgj7qy/5_HW.pdf?dl=0 HW5 parameterized complexity]

Bbauwens в 18:07, 9 февраля 2023

2023-02-09T18:07:50Z

← Предыдущая версия		Версия от 18:07, 9 февраля 2023
Строка 16:		Строка 16:
	{\| class="wikitable"		{\| class="wikitable"
	\|-		\|-
	! Video !! Summary !! Notes !!		! Video !! Summary !! Notes !
	\|-		\|-
	\|\| [https://youtu.be/BHm2eHFnC6U 19.01] \|\| Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties \|\| [https://www.dropbox.com/s/uz1gyurwjvfwe77/automata.pdf?dl=0 lecture 1]		\|\| [https://youtu.be/BHm2eHFnC6U 19.01] \|\| Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties \|\| [https://www.dropbox.com/s/uz1gyurwjvfwe77/automata.pdf?dl=0 lecture 1]

Bbauwens в 18:07, 9 февраля 2023

2023-02-09T18:07:36Z

← Предыдущая версия		Версия от 18:07, 9 февраля 2023
Строка 18:		Строка 18:
	! Video !! Summary !! Notes !!		! Video !! Summary !! Notes !!
	\|-		\|-
	\|\| [https://youtu.be/BHm2eHFnC6U 19.01] \|\| Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties \|\| [https://www.dropbox.com/s/uz1gyurwjvfwe77/automata.pdf?dl=0 lecture 1] \|\|		\|\| [https://youtu.be/BHm2eHFnC6U 19.01] \|\| Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties \|\| [https://www.dropbox.com/s/uz1gyurwjvfwe77/automata.pdf?dl=0 lecture 1]
	\|-		\|-
	\|\| 25.01 \|\| Turing machines and register machines \|\| [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2]		\|\| 25.01 \|\| Turing machines and register machines \|\| [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2]
Строка 28:		Строка 28:
	\|\| <span style="color:gray">23.02</span> \|\| <span style="color:gray">Holliday</span> \|\|		\|\| <span style="color:gray">23.02</span> \|\| <span style="color:gray">Holliday</span> \|\|
	\|-		\|-
	\|\| 02.03 \|\| The class NP and NP-completeness \|\| [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] \|\|		\|\| 02.03 \|\| The class NP and NP-completeness \|\| [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes]
	\|-		\|-
	\|\| 02.03 \|\| Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions \|\| [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits]		\|\| 02.03 \|\| Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions \|\| [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits]

Bbauwens в 18:06, 9 февраля 2023

2023-02-09T18:06:53Z

← Предыдущая версия		Версия от 18:06, 9 февраля 2023
Строка 16:		Строка 16:
	{\| class="wikitable"		{\| class="wikitable"
	\|-		\|-
	! Video !! Summary !! Notes !! ~~Homework~~		! Video !! Summary !! Notes !!
	\|-		\|-
	\|\| [https://youtu.be/BHm2eHFnC6U 19.01] \|\| Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties \|\| [https://www.dropbox.com/s/uz1gyurwjvfwe77/automata.pdf?dl=0 lecture 1] \|\|		\|\| [https://youtu.be/BHm2eHFnC6U 19.01] \|\| Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties \|\| [https://www.dropbox.com/s/uz1gyurwjvfwe77/automata.pdf?dl=0 lecture 1] \|\|
	\|-		\|-
	\|\| 25.01 \|\| Turing machines and register machines \|\| [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2] \|\|		\|\| 25.01 \|\| Turing machines and register machines \|\| [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2]
	\|-		\|-
	\|\| 09.02 \|\| undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems \|\| [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3.A] [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] \|\|		\|\| 09.02 \|\| undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems \|\| [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3.A] [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B]
	\|-		\|-
	\|\| 16.02 \|\| The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems. \|\| [https://www.dropbox.com/s/5amd18ey45qs4x3/cc_seminar.pdf?dl=0 seminar] \|\|		\|\| 16.02 \|\| The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems. \|\| [https://www.dropbox.com/s/5amd18ey45qs4x3/cc_seminar.pdf?dl=0 seminar]
	\|-		\|-
	\|\| <span style="color:gray">23.02</span> \|\| <span style="color:gray">Holliday</span> \|\| \|\|		\|\| <span style="color:gray">23.02</span> \|\| <span style="color:gray">Holliday</span> \|\|
	\|-		\|-
	\|\| 02.03 \|\| The class NP and NP-completeness \|\| [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] \|\| \|\|		\|\| 02.03 \|\| The class NP and NP-completeness \|\| [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] \|\|
	\|-		\|-
	\|\| 02.03 \|\| Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions \|\| [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits]		\|\| 02.03 \|\| Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions \|\| [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits]
	\|-		\|-
	\|\| 16.03 \|\| More NP-complete problems \|\| [https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] \|\|		\|\| 16.03 \|\| More NP-complete problems \|\| [https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions]
	\|-		\|-
	\|\| 23.03 \|\| Games, PSPACE, Savich theorem, completeness of TQBF \|\| [https://www.dropbox.com/s/77sr5nhne411ahz/classPSPACE.pdf?dl=0 pspace]		\|\| 23.03 \|\| Games, PSPACE, Savich theorem, completeness of TQBF \|\| [https://www.dropbox.com/s/77sr5nhne411ahz/classPSPACE.pdf?dl=0 pspace]

Bbauwens в 18:04, 9 февраля 2023

2023-02-09T18:04:43Z

← Предыдущая версия		Версия от 18:04, 9 февраля 2023
Строка 16:		Строка 16:
	{\| class="wikitable"		{\| class="wikitable"
	\|-		\|-
	! Video !! Summary !! Notes		! Video !! Summary !! Notes !! Homework
	\|-		\|-
	\|\| [https://youtu.be/BHm2eHFnC6U 19.01] \|\| Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties \|\| [https://www.dropbox.com/s/uz1gyurwjvfwe77/automata.pdf?dl=0 lecture 1]		\|\| [https://youtu.be/BHm2eHFnC6U 19.01] \|\| Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties \|\| [https://www.dropbox.com/s/uz1gyurwjvfwe77/automata.pdf?dl=0 lecture 1] \|\|
	\|-		\|-
	\|\| 25.01 \|\| Turing machines and register machines \|\| [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2]		\|\| 25.01 \|\| Turing machines and register machines \|\| [https://www.dropbox.com/s/jslijos3lp03m83/turingDef.pdf?dl=0 lecture 2] \|\|
	\|-		\|-
	\|\| 09.02 \|\| undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems \|\| [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3.A] [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B]		\|\| 09.02 \|\| undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems \|\| [https://www.dropbox.com/s/nj7hw8udpbaha37/undecidable.pdf?dl=0 lecture 3.A] [https://www.dropbox.com/s/ykbkpjm4as46nay/incompleteness.pdf?dl=0 3.B] \|\|
	\|-		\|-
	\|\| 16.02 \|\| The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems. \|\| [https://www.dropbox.com/s/5amd18ey45qs4x3/cc_seminar.pdf?dl=0 seminar]		\|\| 16.02 \|\| The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems. \|\| [https://www.dropbox.com/s/5amd18ey45qs4x3/cc_seminar.pdf?dl=0 seminar] \|\|
	\|-		\|-
	\|\| <span style="color:gray">23.02</span> \|\| <span style="color:gray">Holliday</span> \|\|		\|\| <span style="color:gray">23.02</span> \|\| <span style="color:gray">Holliday</span> \|\| \|\|
	\|-		\|-
	\|\| 02.03 \|\| The class NP and NP-completeness \|\| [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes]		\|\| 02.03 \|\| The class NP and NP-completeness \|\| [https://www.dropbox.com/s/90m0yxt62f02mmm/classNP.pdf?dl=0 notes] \|\| \|\|
	\|-		\|-
	\|\| 02.03 \|\| Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions \|\| [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits]		\|\| 02.03 \|\| Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions \|\| [https://www.dropbox.com/s/nen161dakmq3646/circuits.pdf?dl=0 circuits]
	\|-		\|-
	\|\| 16.03 \|\| More NP-complete problems \|\| [https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions]		\|\| 16.03 \|\| More NP-complete problems \|\| [https://www.dropbox.com/s/wlrssw0q1tfx49p/moreReductions.pdf?dl=0 reductions] \|\|
	\|-		\|-
	\|\| 23.03 \|\| Games, PSPACE, Savich theorem, completeness of TQBF \|\| [https://www.dropbox.com/s/77sr5nhne411ahz/classPSPACE.pdf?dl=0 pspace]		\|\| 23.03 \|\| Games, PSPACE, Savich theorem, completeness of TQBF \|\| [https://www.dropbox.com/s/77sr5nhne411ahz/classPSPACE.pdf?dl=0 pspace]
Строка 44:		Строка 44:
	\|\| 27.04 \|\| Projects \|\|		\|\| 27.04 \|\| Projects \|\|
	\|}		\|}


	~~= Homeworks =~~

	~~[https://www.dropbox.com/s/uhi35jl4ofm1ws1/1_HW.pdf?dl=0 HW1 automata]~~

	~~[https://www.dropbox.com/s/j4o5bqz0o1r171o/2_HW.pdf?dl=0 HW2 computability]~~

	~~[https://www.dropbox.com/s/4mgniv56j9qg2c8/3_HW.pdf?dl=0 HW3 P, NP, hierarchy theorems, circuits]~~

	~~[https://www.dropbox.com/s/w3d6hetx65se8hx/4_HW.pdf?dl=0 HW4 NP and PSPACE completeness]~~

	~~[https://www.dropbox.com/s/q9afprj9wwgj7qy/5_HW.pdf?dl=0 HW5 parameterized complexity]~~

Mednik: Откат правок Seosky (обсуждение) к версии Bbauwens

2022-08-26T06:36:20Z

Откат правок Seosky (обсуждение) к версии Bbauwens

Внесённые изменения

Seosky в 23:28, 17 августа 2022

2022-08-17T23:28:09Z

Внесённые изменения

Bbauwens в 08:10, 11 июня 2022

2022-06-11T08:10:58Z

← Предыдущая версия		Версия от 08:10, 11 июня 2022
Строка 56:		Строка 56:
	[https://www.dropbox.com/s/w3d6hetx65se8hx/4_HW.pdf?dl=0 HW4 NP and PSPACE completeness]		[https://www.dropbox.com/s/w3d6hetx65se8hx/4_HW.pdf?dl=0 HW4 NP and PSPACE completeness]

	[https://www.dropbox.com/s/q9afprj9wwgj7qy/5_HW.pdf?dl=0 HW5 parameterized complexity] ~~(more will be added)~~		[https://www.dropbox.com/s/q9afprj9wwgj7qy/5_HW.pdf?dl=0 HW5 parameterized complexity]

Bbauwens в 13:02, 16 апреля 2022

2022-04-16T13:02:33Z

← Предыдущая версия		Версия от 13:02, 16 апреля 2022
Строка 42:		Строка 42:
	\|\| <span style="color:gray">20.04</span> \|\| <span style="color:gray">No lecture</span>		\|\| <span style="color:gray">20.04</span> \|\| <span style="color:gray">No lecture</span>
	\|-		\|-
	\|\| 20.04 \|\| Projects \|\|		\|\| 27.04 \|\| Projects \|\|
	\|}		\|}

Bbauwens в 13:01, 16 апреля 2022

2022-04-16T13:01:36Z

← Предыдущая версия		Версия от 13:01, 16 апреля 2022
Строка 39:		Строка 39:
	\|-		\|-
	\|\| 13.04 \|\| Parameterized complexity II: the W-hierarchy \|\| [https://www.mpi-inf.mpg.de/fileadmin/inf/d1/teaching/summer20/paraalg/Lectures/lecture_3.pdf slides] (by Daniel Max) [https://www.dropbox.com/s/caigywrx80v08g3/exercises.pdf?dl=0 exercises]		\|\| 13.04 \|\| Parameterized complexity II: the W-hierarchy \|\| [https://www.mpi-inf.mpg.de/fileadmin/inf/d1/teaching/summer20/paraalg/Lectures/lecture_3.pdf slides] (by Daniel Max) [https://www.dropbox.com/s/caigywrx80v08g3/exercises.pdf?dl=0 exercises]
			\|-
			\|\| <span style="color:gray">20.04</span> \|\| <span style="color:gray">No lecture</span>
	\|-		\|-
	\|\| 20.04 \|\| Projects \|\|		\|\| 20.04 \|\| Projects \|\|