http://mit.spbau.ru/sewiki/api.php?action=feedcontributions&feedformat=atom&user=Lglinskih
SEWiki - Вклад участника [ru]
2026-04-11T18:59:01Z
Вклад участника
MediaWiki 1.26.2
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15827
Теория алгоритмов 2MIT весна 2018
2018-06-12T09:58:20Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
*13 февраля. Машина Тьюринга. <br />
*20 февраля. Универсальная машина Тьюринга. Класс NP. <br />
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br />
*06 марта. Машины с оракульным доступом. Построение языка B, такого что <math>P^B \neq NP^B</math>. Сложность по памяти. [[Медиа:AlgTh-lec-4.pdf|pdf.]] <br />
*13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. [[Медиа:AlgTh-lec-5.pdf|pdf.]] <br />
*20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. [[Медиа:AlgTh-lec-6.pdf|pdf.]] <br />
*27 марта. Полиномиальная иерархия. <math>Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]</math>. [[Медиа:AlgTh-lec-7.pdf|pdf.]] <br />
*03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный <math>O^*(4^k)</math> алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]] <br />
*10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за <math>n\ln{n}+cn</math>. [[Медиа:AlgTh-lec-9.pdf|pdf.]] <br />
*17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. [[Медиа:AlgTh-lec-10.pdf|pdf.]] <br />
*24 апреля. Путь с логарифмической памятью. [[Медиа:AlgTh-lec-11.pdf|pdf.]]<br />
*25 апреля. Схемы. [[Медиа:AlgTh-lec-12.pdf|pdf.]]<br />
*08 мая. <math>BPP \subseteq P_{/poly}</math> и <math>BPP \subseteq \Sigma^p_2</math>. Теорема Вэлианта-Вазирани. [[Медиа:AlgTh-lec-13.pdf|pdf.]]<br />
*15 мая Котрольная работа. [[Медиа:AlgTh-KR-I.pdf|part I]], [[Медиа:AlgTh-KR-II.pdf|part II]]<br />
<br />
<br />
'''Вопросы к экзамену'''<br />
<br />
[[Медиа:AlgTh-Questions.pdf|Список вопросов]]<br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
* Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms.<br />
* Michael Sipser, Introduction to the Theory of Computation.<br />
<br />
'''Различные видео материалы(материалы для полезной прокрастинации)'''<br />
* P vs. NP and the Computational Complexity Zoo [https://www.youtube.com/watch?v=YX40hbAHx3s смотреть]<br />
* Crach course in Computer Science(в первых видео рассказывается история возникновения компьютеров, становится более понятно почему же машина Тьюринга или схема имеют что-то общее с компьютером) [https://www.youtube.com/watch?v=tpIctyqH29Q&list=PL8dPuuaLjXtNlUrzyH5r6jN9ulIgZBpdo смотреть]<br />
* Видеолекции похожего курса [http://lectoriy.mipt.ru/course/Maths-ComputationalComplexity-14L#lectures смотреть]<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-2.pdf|20 февраля, "Класс NP."]]<br />
*[[Медиа:AlgTh-home-2.pdf|20 февраля, "Класс NP(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-3.pdf|27 февраля, "Классы NP, coNP, иерархия по времени."]]<br />
*[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-4.pdf|06 марта, "Оракульные машины и PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, "PSPACE."]]<br />
*[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, "PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-6.pdf|20 марта, "Класс NL."]]<br />
*[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, "Класс NL(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, "Класс NL(ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-7.pdf|27 марта, "Полиномиальная иерархия."]]<br />
*[[Медиа:AlgTh-home-7.pdf|27 марта, "Полиномиальная иерархия (ДЗ)."]]<br />
*[[Медиа:AlgTh-home-7-hints.pdf|27 марта, "Полиномиальная иерархия (ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-8.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы."]]<br />
*[[Медиа:AlgTh-home-8-added.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-9.pdf|10 апреля, "Предыдущие задачи(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, "Предыдущие задачи+подсказки(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, "Оценки Чернова."]]<br />
*[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, "Оценки Чернова. Элементы линейного программирования(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-11.pdf|24 апреля, "Путь. Увеличение вероятности."]]<br />
*[[Медиа:AlgTh-class-12.pdf|26 апреля, "Схемы."]]<br />
*[[Медиа:AlgTh-home-12.pdf|26 апреля, "Схемы(ДЗ)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[https://docs.google.com/spreadsheets/d/1oKyKA2hr9u7w_RWiqdbg4-5NodDbc7MHd0L5qA6cFTM/edit?usp=sharing Табличка]<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]<br />
<br />
[http://lglinskih.com/HW3.pdf Домашнее задание к практике 3]<br />
<br />
[http://lglinskih.com/HW4.pdf Домашнее задание к практике 4]<br />
<br />
[http://lglinskih.com/HW5.pdf Домашнее задание к практике 5]<br />
<br />
[http://lglinskih.com/HW6.pdf Домашнее задание к практике 6]<br />
<br />
[http://lglinskih.com/HW7.pdf Домашнее задание к практике 7]<br />
<br />
[http://lglinskih.com/HW8.pdf Домашнее задание к практике 8]<br />
<br />
[http://lglinskih.com/HW910.pdf Домашнее задание к практике 9 и 10]<br />
<br />
[http://lglinskih.com/HW12.pdf Домашнее задание к практике 11 и 12]<br />
<br />
[http://lglinskih.com/HW13.pdf Домашнее задание к практике 13 (последнее/дополнительное домашнее задание)]<br />
<br />
Переписка контрольной работы: [[Медиа:KR.pdf|теория]], [[Медиа:KR2.pdf|практика]]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:KR2.pdf&diff=15826
Файл:KR2.pdf
2018-06-12T09:55:32Z
<p>Lglinskih: Переписка контрольной, практ. часть</p>
<hr />
<div>Переписка контрольной, практ. часть</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:KR.pdf&diff=15825
Файл:KR.pdf
2018-06-12T09:55:08Z
<p>Lglinskih: Переписка контрольной, теор. часть</p>
<hr />
<div>Переписка контрольной, теор. часть</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15776
Теория алгоритмов 2MIT весна 2018
2018-05-22T20:31:19Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
*13 февраля. Машина Тьюринга. <br />
*20 февраля. Универсальная машина Тьюринга. Класс NP. <br />
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br />
*06 марта. Машины с оракульным доступом. Построение языка B, такого что <math>P^B \neq NP^B</math>. Сложность по памяти. [[Медиа:AlgTh-lec-4.pdf|pdf.]] <br />
*13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. [[Медиа:AlgTh-lec-5.pdf|pdf.]] <br />
*20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. [[Медиа:AlgTh-lec-6.pdf|pdf.]] <br />
*27 марта. Полиномиальная иерархия. <math>Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]</math>. [[Медиа:AlgTh-lec-7.pdf|pdf.]] <br />
*03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный <math>O^*(4^k)</math> алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]] <br />
*10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за <math>n\ln{n}+cn</math>. [[Медиа:AlgTh-lec-9.pdf|pdf.]] <br />
*17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. [[Медиа:AlgTh-lec-10.pdf|pdf.]] <br />
*24 апреля. Путь с логарифмической памятью. [[Медиа:AlgTh-lec-11.pdf|pdf.]]<br />
*25 апреля. Схемы. [[Медиа:AlgTh-lec-12.pdf|pdf.]]<br />
*08 мая. <math>BPP \subseteq P_{/poly}</math> и <math>BPP \subseteq \Sigma^p_2</math>. Теорема Вэлианта-Вазирани. [[Медиа:AlgTh-lec-13.pdf|pdf.]]<br />
<br />
<br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
* Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms.<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-2.pdf|20 февраля, "Класс NP."]]<br />
*[[Медиа:AlgTh-home-2.pdf|20 февраля, "Класс NP(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-3.pdf|27 февраля, "Классы NP, coNP, иерархия по времени."]]<br />
*[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-4.pdf|06 марта, "Оракульные машины и PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, "PSPACE."]]<br />
*[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, "PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-6.pdf|20 марта, "Класс NL."]]<br />
*[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, "Класс NL(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, "Класс NL(ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-7.pdf|27 марта, "Полиномиальная иерархия."]]<br />
*[[Медиа:AlgTh-home-7.pdf|27 марта, "Полиномиальная иерархия (ДЗ)."]]<br />
*[[Медиа:AlgTh-home-7-hints.pdf|27 марта, "Полиномиальная иерархия (ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-8.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы."]]<br />
*[[Медиа:AlgTh-home-8-added.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-9.pdf|10 апреля, "Предыдущие задачи(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, "Предыдущие задачи+подсказки(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, "Оценки Чернова."]]<br />
*[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, "Оценки Чернова. Элементы линейного программирования(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-11.pdf|24 апреля, "Путь. Увеличение вероятности."]]<br />
*[[Медиа:AlgTh-class-12.pdf|26 апреля, "Схемы."]]<br />
*[[Медиа:AlgTh-home-12.pdf|26 апреля, "Схемы(ДЗ)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[https://docs.google.com/spreadsheets/d/1oKyKA2hr9u7w_RWiqdbg4-5NodDbc7MHd0L5qA6cFTM/edit?usp=sharing Табличка]<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]<br />
<br />
[http://lglinskih.com/HW3.pdf Домашнее задание к практике 3]<br />
<br />
[http://lglinskih.com/HW4.pdf Домашнее задание к практике 4]<br />
<br />
[http://lglinskih.com/HW5.pdf Домашнее задание к практике 5]<br />
<br />
[http://lglinskih.com/HW6.pdf Домашнее задание к практике 6]<br />
<br />
[http://lglinskih.com/HW7.pdf Домашнее задание к практике 7]<br />
<br />
[http://lglinskih.com/HW8.pdf Домашнее задание к практике 8]<br />
<br />
[http://lglinskih.com/HW910.pdf Домашнее задание к практике 9 и 10]<br />
<br />
[http://lglinskih.com/HW12.pdf Домашнее задание к практике 11 и 12]<br />
<br />
[http://lglinskih.com/HW13.pdf Домашнее задание к практике 13 (последнее/дополнительное домашнее задание)]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15638
Теория алгоритмов 2MIT весна 2018
2018-05-05T11:35:53Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
*13 февраля. Машина Тьюринга. <br />
*20 февраля. Универсальная машина Тьюринга. Класс NP. <br />
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br />
*06 марта. Машины с оракульным доступом. Построение языка B, такого что <math>P^B \neq NP^B</math>. Сложность по памяти.<br />
*13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br />
*20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br />
*27 марта. Полиномиальная иерархия. <math>Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]</math>. <br />
*03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный <math>O^*(4^k)</math> алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br />
*10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за <math>n\ln{n}+cn</math>.<br />
*17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br />
<br />
<br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
* Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms.<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-2.pdf|20 февраля, "Класс NP."]]<br />
*[[Медиа:AlgTh-home-2.pdf|20 февраля, "Класс NP(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-3.pdf|27 февраля, "Классы NP, coNP, иерархия по времени."]]<br />
*[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-4.pdf|06 марта, "Оракульные машины и PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, "PSPACE."]]<br />
*[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, "PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-6.pdf|20 марта, "Класс NL."]]<br />
*[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, "Класс NL(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, "Класс NL(ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-7.pdf|27 марта, "Полиномиальная иерархия."]]<br />
*[[Медиа:AlgTh-home-7.pdf|27 марта, "Полиномиальная иерархия (ДЗ)."]]<br />
*[[Медиа:AlgTh-home-7-hints.pdf|27 марта, "Полиномиальная иерархия (ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-8.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы."]]<br />
*[[Медиа:AlgTh-home-8-added.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-9.pdf|10 апреля, "Предыдущие задачи(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, "Предыдущие задачи+подсказки(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, "Оценки Чернова."]]<br />
*[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, "Оценки Чернова. Элементы линейного программирования(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-11.pdf|24 апреля, "Путь. Увеличение вероятности."]]<br />
*[[Медиа:AlgTh-class-12.pdf|26 апреля, "Схемы."]]<br />
*[[Медиа:AlgTh-home-12.pdf|26 апреля, "Схемы(ДЗ)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[https://docs.google.com/spreadsheets/d/1oKyKA2hr9u7w_RWiqdbg4-5NodDbc7MHd0L5qA6cFTM/edit?usp=sharing Табличка]<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]<br />
<br />
[http://lglinskih.com/HW3.pdf Домашнее задание к практике 3]<br />
<br />
[http://lglinskih.com/HW4.pdf Домашнее задание к практике 4]<br />
<br />
[http://lglinskih.com/HW5.pdf Домашнее задание к практике 5]<br />
<br />
[http://lglinskih.com/HW6.pdf Домашнее задание к практике 6]<br />
<br />
[http://lglinskih.com/HW7.pdf Домашнее задание к практике 7]<br />
<br />
[http://lglinskih.com/HW8.pdf Домашнее задание к практике 8]<br />
<br />
[http://lglinskih.com/HW910.pdf Домашнее задание к практике 9 и 10]<br />
<br />
[http://lglinskih.com/HW12.pdf Домашнее задание к практике 11 и 12]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15563
Теория алгоритмов 2MIT весна 2018
2018-04-28T12:33:09Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
*13 февраля. Машина Тьюринга. <br />
*20 февраля. Универсальная машина Тьюринга. Класс NP. <br />
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br />
*06 марта. Машины с оракульным доступом. Построение языка B, такого что <math>P^B \neq NP^B</math>. Сложность по памяти.<br />
*13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br />
*20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br />
*27 марта. Полиномиальная иерархия. <math>Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]</math>. <br />
*03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный <math>O^*(4^k)</math> алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br />
*10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за <math>n\ln{n}+cn</math>.<br />
*17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br />
<br />
<br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
* Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms.<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-2.pdf|20 февраля, "Класс NP."]]<br />
*[[Медиа:AlgTh-home-2.pdf|20 февраля, "Класс NP(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-3.pdf|27 февраля, "Классы NP, coNP, иерархия по времени."]]<br />
*[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-4.pdf|06 марта, "Оракульные машины и PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, "PSPACE."]]<br />
*[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, "PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-6.pdf|20 марта, "Класс NL."]]<br />
*[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, "Класс NL(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, "Класс NL(ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-7.pdf|27 марта, "Полиномиальная иерархия."]]<br />
*[[Медиа:AlgTh-home-7.pdf|27 марта, "Полиномиальная иерархия (ДЗ)."]]<br />
*[[Медиа:AlgTh-home-7-hints.pdf|27 марта, "Полиномиальная иерархия (ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-8.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы."]]<br />
*[[Медиа:AlgTh-home-8-added.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-9.pdf|10 апреля, "Предыдущие задачи(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, "Предыдущие задачи+подсказки(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, "Оценки Чернова."]]<br />
*[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, "Оценки Чернова. Элементы линейного программирования(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-11.pdf|24 апреля, "Путь. Увеличение вероятности"]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[https://docs.google.com/spreadsheets/d/1oKyKA2hr9u7w_RWiqdbg4-5NodDbc7MHd0L5qA6cFTM/edit?usp=sharing Табличка]<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]<br />
<br />
[http://lglinskih.com/HW3.pdf Домашнее задание к практике 3]<br />
<br />
[http://lglinskih.com/HW4.pdf Домашнее задание к практике 4]<br />
<br />
[http://lglinskih.com/HW5.pdf Домашнее задание к практике 5]<br />
<br />
[http://lglinskih.com/HW6.pdf Домашнее задание к практике 6]<br />
<br />
[http://lglinskih.com/HW7.pdf Домашнее задание к практике 7]<br />
<br />
[http://lglinskih.com/HW8.pdf Домашнее задание к практике 8]<br />
<br />
[http://lglinskih.com/HW910.pdf Домашнее задание к практике 9 и 10 (финальная версия)]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15513
Теория алгоритмов 2MIT весна 2018
2018-04-24T13:47:58Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
*13 февраля. Машина Тьюринга. <br />
*20 февраля. Универсальная машина Тьюринга. Класс NP. <br />
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br />
*06 марта. Машины с оракульным доступом. Построение языка B, такого что <math>P^B \neq NP^B</math>. Сложность по памяти.<br />
*13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br />
*20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br />
*27 марта. Полиномиальная иерархия. <math>Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]</math>. <br />
*03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный <math>O^*(4^k)</math> алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br />
*10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за <math>n\ln{n}+cn</math>.<br />
*17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br />
<br />
<br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
* Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms.<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-2.pdf|20 февраля, "Класс NP."]]<br />
*[[Медиа:AlgTh-home-2.pdf|20 февраля, "Класс NP(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-3.pdf|27 февраля, "Классы NP, coNP, иерархия по времени."]]<br />
*[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-4.pdf|06 марта, "Оракульные машины и PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, "PSPACE."]]<br />
*[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, "PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-6.pdf|20 марта, "Класс NL."]]<br />
*[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, "Класс NL(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, "Класс NL(ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-7.pdf|27 марта, "Полиномиальная иерархия."]]<br />
*[[Медиа:AlgTh-home-7.pdf|27 марта, "Полиномиальная иерархия (ДЗ)."]]<br />
*[[Медиа:AlgTh-home-7-hints.pdf|27 марта, "Полиномиальная иерархия (ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-8.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы."]]<br />
*[[Медиа:AlgTh-home-8-added.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-9.pdf|10 апреля, "Предыдущие задачи(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, "Предыдущие задачи+подсказки(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, "Оценки Чернова."]]<br />
*[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, "Оценки Чернова. Элементы линейного программирования(ДЗ)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[https://docs.google.com/spreadsheets/d/1oKyKA2hr9u7w_RWiqdbg4-5NodDbc7MHd0L5qA6cFTM/edit?usp=sharing Табличка]<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]<br />
<br />
[http://lglinskih.com/HW3.pdf Домашнее задание к практике 3]<br />
<br />
[http://lglinskih.com/HW4.pdf Домашнее задание к практике 4]<br />
<br />
[http://lglinskih.com/HW5.pdf Домашнее задание к практике 5]<br />
<br />
[http://lglinskih.com/HW6.pdf Домашнее задание к практике 6]<br />
<br />
[http://lglinskih.com/HW7.pdf Домашнее задание к практике 7]<br />
<br />
[http://lglinskih.com/HW8.pdf Домашнее задание к практике 8]<br />
<br />
[http://lglinskih.com/HW910.pdf Домашнее задание к практике 9 и 10, которое может быть дополнено ещё одной задачей]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15360
Теория алгоритмов 2MIT весна 2018
2018-04-10T14:26:33Z
<p>Lglinskih: /* Лекции */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
*13 февраля. Машина Тьюринга. <br />
*20 февраля. Универсальная машина Тьюринга. Класс NP. <br />
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br />
*06 марта. Машины с оракульным доступом. Построение языка B, такого что <math>P^B \neq NP^B</math>. Сложность по памяти.<br />
*13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br />
*20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br />
*27 марта. Полиномиальная иерархия. <math>Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]</math>. <br />
*03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный <math>O^*(4^k)</math> алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br />
*10 апреля. <br />
<br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
* Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms.<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-2.pdf|20 февраля, "Класс NP."]]<br />
*[[Медиа:AlgTh-home-2.pdf|20 февраля, "Класс NP(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-3.pdf|27 февраля, "Классы NP, coNP, иерархия по времени."]]<br />
*[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-4.pdf|06 марта, "Оракульные машины и PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, "PSPACE."]]<br />
*[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, "PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-6.pdf|20 марта, "Класс NL."]]<br />
*[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, "Класс NL(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, "Класс NL(ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-7.pdf|27 марта, "Полиномиальная иерархия."]]<br />
*[[Медиа:AlgTh-home-7.pdf|27 марта, "Полиномиальная иерархия (ДЗ)."]]<br />
*[[Медиа:AlgTh-home-7-hints.pdf|27 марта, "Полиномиальная иерархия (ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-8.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы."]]<br />
*[[Медиа:AlgTh-home-8-added.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы(ДЗ)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[https://docs.google.com/spreadsheets/d/1oKyKA2hr9u7w_RWiqdbg4-5NodDbc7MHd0L5qA6cFTM/edit?usp=sharing Табличка]<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]<br />
<br />
[http://lglinskih.com/HW3.pdf Домашнее задание к практике 3]<br />
<br />
[http://lglinskih.com/HW4.pdf Домашнее задание к практике 4]<br />
<br />
[http://lglinskih.com/HW5.pdf Домашнее задание к практике 5]<br />
<br />
[http://lglinskih.com/HW6.pdf Домашнее задание к практике 6]<br />
<br />
[http://lglinskih.com/HW7.pdf Домашнее задание к практике 7]<br />
<br />
[http://lglinskih.com/HW8.pdf Домашнее задание к практике 8]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15328
Теория алгоритмов 2MIT весна 2018
2018-04-07T11:05:45Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
*13 февраля. Машина Тьюринга. <br />
*20 февраля. Универсальная машина Тьюринга. Класс NP. <br />
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br />
*06 марта. Машины с оракульным доступом. Построение языка B, такого что <math>P^B \neq NP^B</math>. Сложность по памяти.<br />
*13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br />
*20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br />
*27 марта. Полиномиальная иерархия. <math>Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]</math>. <br />
<br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-2.pdf|20 февраля, "Класс NP."]]<br />
*[[Медиа:AlgTh-home-2.pdf|20 февраля, "Класс NP(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-3.pdf|27 февраля, "Классы NP, coNP, иерархия по времени."]]<br />
*[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-4.pdf|06 марта, "Оракульные машины и PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, "PSPACE."]]<br />
*[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, "PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-6.pdf|20 марта, "Класс NL."]]<br />
*[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, "Класс NL(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, "Класс NL(ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-7.pdf|27 марта, "Полиномиальная иерархия."]]<br />
*[[Медиа:AlgTh-home-7.pdf|27 марта, "Полиномиальная иерархия (ДЗ)."]]<br />
*[[Медиа:AlgTh-home-7-hints.pdf|27 марта, "Полиномиальная иерархия (ДЗ+подсказки)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[https://docs.google.com/spreadsheets/d/1oKyKA2hr9u7w_RWiqdbg4-5NodDbc7MHd0L5qA6cFTM/edit?usp=sharing Табличка]<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]<br />
<br />
[http://lglinskih.com/HW3.pdf Домашнее задание к практике 3]<br />
<br />
[http://lglinskih.com/HW4.pdf Домашнее задание к практике 4]<br />
<br />
[http://lglinskih.com/HW5.pdf Домашнее задание к практике 5]<br />
<br />
[http://lglinskih.com/HW6.pdf Домашнее задание к практике 6]<br />
<br />
[http://lglinskih.com/HW7.pdf Домашнее задание к практике 7]<br />
<br />
[http://lglinskih.com/HW8.pdf Домашнее задание к практике 8]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15288
Теория алгоритмов 2MIT весна 2018
2018-04-02T09:31:55Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
*13 февраля. Машина Тьюринга. <br />
*20 февраля. Универсальная машина Тьюринга. Класс NP. <br />
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br />
*06 марта. Машины с оракульным доступом. Построение языка B, такого что <math>P^B \neq NP^B</math>. Сложность по памяти.<br />
*13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br />
*20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br />
*27 марта. Полиномиальная иерархия. <math>Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]</math>. <br />
<br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-2.pdf|20 февраля, "Класс NP."]]<br />
*[[Медиа:AlgTh-home-2.pdf|20 февраля, "Класс NP(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-3.pdf|27 февраля, "Классы NP, coNP, иерархия по времени."]]<br />
*[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-4.pdf|06 марта, "Оракульные машины и PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, "PSPACE."]]<br />
*[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, "PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-6.pdf|20 марта, "Класс NL."]]<br />
*[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, "Класс NL(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, "Класс NL(ДЗ+подсказки)."]]<br />
*[[Медиа:AlgTh-class-7.pdf|27 марта, "Полиномиальная иерархия."]]<br />
*[[Медиа:AlgTh-home-7.pdf|27 марта, "Полиномиальная иерархия (ДЗ)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[https://docs.google.com/spreadsheets/d/1oKyKA2hr9u7w_RWiqdbg4-5NodDbc7MHd0L5qA6cFTM/edit?usp=sharing Табличка]<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]<br />
<br />
[http://lglinskih.com/HW3.pdf Домашнее задание к практике 3]<br />
<br />
[http://lglinskih.com/HW4.pdf Домашнее задание к практике 4]<br />
<br />
[http://lglinskih.com/HW5.pdf Домашнее задание к практике 5]<br />
<br />
[http://lglinskih.com/HW6.pdf Домашнее задание к практике 6]<br />
<br />
[http://lglinskih.com/HW7.pdf Домашнее задание к практике 7]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15148
Теория алгоритмов 2MIT весна 2018
2018-03-24T09:11:53Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
*13 февраля. Машина Тьюринга. <br />
*20 февраля. Универсальная машина Тьюринга. Класс NP. <br />
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br />
*06 марта. Машины с оракульным доступом. Построение языка B, такого что <math>P^B \neq NP^B</math>. Сложность по памяти.<br />
*13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br />
*20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br />
<br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-2.pdf|20 февраля, "Класс NP."]]<br />
*[[Медиа:AlgTh-home-2.pdf|20 февраля, "Класс NP(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-3.pdf|27 февраля, "Классы NP, coNP, иерархия по времени."]]<br />
*[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-4.pdf|06 марта, "Оракульные машины и PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, "PSPACE."]]<br />
*[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, "PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-6.pdf|20 марта, "Класс NL."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[https://docs.google.com/spreadsheets/d/1oKyKA2hr9u7w_RWiqdbg4-5NodDbc7MHd0L5qA6cFTM/edit?usp=sharing Табличка]<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]<br />
<br />
[http://lglinskih.com/HW3.pdf Домашнее задание к практике 3]<br />
<br />
[http://lglinskih.com/HW4.pdf Домашнее задание к практике 4]<br />
<br />
[http://lglinskih.com/HW5.pdf Домашнее задание к практике 5]<br />
<br />
[http://lglinskih.com/HW6.pdf Домашнее задание к практике 6]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15077
Теория алгоритмов 2MIT весна 2018
2018-03-17T00:49:36Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
*13 февраля. Машина Тьюринга. <br />
*20 февраля. Универсальная машина Тьюринга. Класс NP. <br />
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-2.pdf|20 февраля, "Класс NP."]]<br />
*[[Медиа:AlgTh-home-2.pdf|20 февраля, "Класс NP(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-3.pdf|27 февраля, "Классы NP, coNP, иерархия по времени."]]<br />
*[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-4.pdf|06 марта, "Оракульные машины и PSPACE(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, "PSPACE."]]<br />
*[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, "PSPACE(ДЗ)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[https://docs.google.com/spreadsheets/d/1oKyKA2hr9u7w_RWiqdbg4-5NodDbc7MHd0L5qA6cFTM/edit?usp=sharing Табличка]<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]<br />
<br />
[http://lglinskih.com/HW3.pdf Домашнее задание к практике 3]<br />
<br />
[http://lglinskih.com/HW4.pdf Домашнее задание к практике 4]<br />
<br />
[http://lglinskih.com/HW5.pdf Домашнее задание к практике 5]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15015
Теория алгоритмов 2MIT весна 2018
2018-03-10T00:09:15Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
*13 февраля. Машина Тьюринга. <br />
*20 февраля. Универсальная машина Тьюринга. Класс NP. <br />
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-2.pdf|20 февраля, "Класс NP."]]<br />
*[[Медиа:AlgTh-home-2.pdf|20 февраля, "Класс NP(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-3.pdf|27 февраля, "Классы NP, coNP, иерархия по времени."]]<br />
*[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."]]<br />
*[[Медиа:AlgTh-home-4.pdf|06 марта, "Оракульные машины и PSPACE(ДЗ)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[https://docs.google.com/spreadsheets/d/1oKyKA2hr9u7w_RWiqdbg4-5NodDbc7MHd0L5qA6cFTM/edit?usp=sharing Табличка]<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]<br />
<br />
[http://lglinskih.com/HW3.pdf Домашнее задание к практике 3]<br />
<br />
[http://lglinskih.com/HW4.pdf Домашнее задание к практике 4]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=14936
Теория алгоритмов 2MIT весна 2018
2018-03-03T02:11:06Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
*13 февраля. Машина Тьюринга. <br />
*20 февраля. Универсальная машина Тьюринга. Класс NP. <br />
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
*[[Медиа:AlgTh-class-2.pdf|20 февраля, "Класс NP."]]<br />
*[[Медиа:AlgTh-home-2.pdf|20 февраля, "Класс NP(ДЗ)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]<br />
<br />
[http://lglinskih.com/HW3.pdf Домашнее задание к практике 3]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=14773
Теория алгоритмов 2MIT весна 2018
2018-02-22T23:35:11Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
13 февраля. Машина Тьюринга. <br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=14772
Теория алгоритмов 2MIT весна 2018
2018-02-22T23:34:56Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
13 февраля. Машина Тьюринга. <br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=14771
Теория алгоритмов 2MIT весна 2018
2018-02-22T23:34:46Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
13 февраля. Машина Тьюринга. <br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1] <br />
<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=14770
Теория алгоритмов 2MIT весна 2018
2018-02-22T23:34:29Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
13 февраля. Машина Тьюринга. <br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]<br />
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1]<br />
[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=14613
Теория алгоритмов 2MIT весна 2018
2018-02-15T21:37:46Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
13 февраля. Машина Тьюринга. <br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1]</div>
Lglinskih
http://mit.spbau.ru/sewiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2_2MIT_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=14612
Теория алгоритмов 2MIT весна 2018
2018-02-15T21:36:33Z
<p>Lglinskih: /* Практика Глинских */</p>
<hr />
<div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br />
<br />
== Лекции ==<br />
<br />
13 февраля. Машина Тьюринга. <br />
<br />
'''Литература'''<br />
<br />
* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]<br />
http://theory.cs.princeton.edu/complexity/<br />
<br />
== Практика Близнец ==<br />
Преподаватель: Близнец Иван Анатольевич<br />
<br />
<br />
<br />
== Практика Глинских ==<br />
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)<br />
<br />
[http://www.lglinskih.com/HW1 Домашнее задание к практике 1]</div>
Lglinskih