http://mit.spbau.ru/sewiki/api.php?action=feedcontributions&feedformat=atom&user=Bliznets 2026-04-15T09:12:20Z Вклад участника MediaWiki 1.26.2 http://mit.spbau.ru/sewiki/index.php?title=%D0%9F%D0%B0%D1%80%D0%B0%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15816 2018-06-03T15:32:44Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *16 february. Bounded search trees.<br /> ** FPT. Kernelization. Vertex Cover. Feedback Vertex Set. Closest String.<br /> *2 march. Kernelization.<br /> **Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability.<br /> *16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching.<br /> *23 march. Vertex Cover above Matching. Iterative Compression.<br /> ** Odd Cycle transversal &lt;math&gt;O^*(4^k)&lt;/math&gt;. Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal &lt;math&gt;O^*(3^k)&lt;/math&gt;.<br /> *30 march. Randomized methods.<br /> *6 april. &lt;math&gt;O^*(4^k)&lt;/math&gt; algorithm for k-path. Derandomization.<br /> *13 april. Dynamic programming over subsets. Integer linear programming. Graph minors and Robertson-Seymour theorem.<br /> *20 april. Important cuts. Edge Multiway Cut.<br /> *27 april. Important cuts in Directed graphs. Directed Feedback Vertex Set.<br /> *04 may. W[1] class.<br /> *11 may. Kernel lower bounds.<br /> *18 may. Vertex cover does not admit subquadratic bit size kernel.<br /> <br /> == Практика ==<br /> <br /> *[[Медиа:FPT-home-1.pdf|16 february, &quot;Bounded search trees (HW).&quot;]]<br /> Надо оформить 5 самых сложных задач из Вами решенных.<br /> *[[Медиа:FPT-class-2.pdf|2 march, &quot;Kernelization.&quot;]]<br /> *[[Медиа:FPT-home-2.pdf|2 march, &quot;Kernelization(HW).&quot;]]<br /> *[[Медиа:FPT-home-3.pdf|16 march, &quot;Kernelization II(HW).&quot;]]<br /> *[[Медиа:FPT-class-4.pdf|23 march, &quot;Iterative Compression.&quot;]]<br /> *[[Медиа:FPT-home-4.pdf|23 march, &quot;Iterative Compression(HW).&quot;]]<br /> *[[Медиа:FPT-class-5.pdf|30 march, &quot;Randomized methods.&quot;]]<br /> *[[Медиа:FPT-home-5.pdf|30 march, &quot;Randomized methods(HW).&quot;]]<br /> *[[Медиа:FPT-class-6.pdf|06 april, &quot;Derandomization.&quot;]]<br /> *[[Медиа:FPT-home-6.pdf|06 april, &quot;Randomized methods and derandomization(HW).&quot;]]<br /> *[[Медиа:FPT-home-13.pdf|13 april, &quot;Miscellaneous(HW).&quot;]]<br /> *[[Медиа:FPT-home-8.pdf|20 april, &quot;Important cuts(HW).&quot;]]<br /> *[[Медиа:FPT-class-9.pdf|27 april, &quot;Important cuts II.&quot;]]<br /> *[[Медиа:FPT-home-9.pdf|27 april, &quot;Important cuts II(HW).&quot;]]<br /> *[[Медиа:FPT-class-10.pdf|03 may, &quot;W[1], W[2].&quot;]]<br /> *[[Медиа:FPT-home-10.pdf|03 may, &quot;W[1], W[2](HW).&quot;]]</div>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%9F%D0%B0%D1%80%D0%B0%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15815 2018-06-03T15:31:35Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *16 february. Bounded search trees.<br /> ** FPT. Kernelization. Vertex Cover. Feedback Vertex Set. Closest String.<br /> *2 march. Kernelization.<br /> **Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability.<br /> *16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching.<br /> *23 march. Vertex Cover above Matching. Iterative Compression.<br /> ** Odd Cycle transversal &lt;math&gt;O^*(4^k)&lt;/math&gt;. Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal &lt;math&gt;O^*(3^k)&lt;/math&gt;.<br /> *30 march. Randomized methods.<br /> *6 april. &lt;math&gt;O^*(4^k)&lt;/math&gt; algorithm for k-path. Derandomization.<br /> *13 april. Dynamic programming over subsets. Integer linear programming. Graph minors and Robertson-Seymour theorem.<br /> *20 april. Important cuts. Edge Multiway Cut.<br /> *27 april. Important cuts in Directed graphs. Directed Feedback Vertex Set.<br /> *05 may. W[1] class.<br /> *12 may. Kernel lower bounds.<br /> <br /> == Практика ==<br /> <br /> *[[Медиа:FPT-home-1.pdf|16 february, &quot;Bounded search trees (HW).&quot;]]<br /> Надо оформить 5 самых сложных задач из Вами решенных.<br /> *[[Медиа:FPT-class-2.pdf|2 march, &quot;Kernelization.&quot;]]<br /> *[[Медиа:FPT-home-2.pdf|2 march, &quot;Kernelization(HW).&quot;]]<br /> *[[Медиа:FPT-home-3.pdf|16 march, &quot;Kernelization II(HW).&quot;]]<br /> *[[Медиа:FPT-class-4.pdf|23 march, &quot;Iterative Compression.&quot;]]<br /> *[[Медиа:FPT-home-4.pdf|23 march, &quot;Iterative Compression(HW).&quot;]]<br /> *[[Медиа:FPT-class-5.pdf|30 march, &quot;Randomized methods.&quot;]]<br /> *[[Медиа:FPT-home-5.pdf|30 march, &quot;Randomized methods(HW).&quot;]]<br /> *[[Медиа:FPT-class-6.pdf|06 april, &quot;Derandomization.&quot;]]<br /> *[[Медиа:FPT-home-6.pdf|06 april, &quot;Randomized methods and derandomization(HW).&quot;]]<br /> *[[Медиа:FPT-home-13.pdf|13 april, &quot;Miscellaneous(HW).&quot;]]<br /> *[[Медиа:FPT-home-8.pdf|20 april, &quot;Important cuts(HW).&quot;]]<br /> *[[Медиа:FPT-class-9.pdf|27 april, &quot;Important cuts II.&quot;]]<br /> *[[Медиа:FPT-home-9.pdf|27 april, &quot;Important cuts II(HW).&quot;]]<br /> *[[Медиа:FPT-class-10.pdf|03 may, &quot;W[1], W[2].&quot;]]<br /> *[[Медиа:FPT-home-10.pdf|03 may, &quot;W[1], W[2](HW).&quot;]]</div>

Bliznets 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=15814 2018-06-03T11:33:12Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти. [[Медиа: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 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. [[Медиа:AlgTh-lec-7.pdf|pdf.]] <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]] <br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;. [[Медиа: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 мая. &lt;math&gt;BPP \subseteq P_{/poly}&lt;/math&gt; и &lt;math&gt;BPP \subseteq \Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа: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&amp;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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-Questions.pdf&diff=15813 2018-06-03T11:17:48Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets 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=15812 2018-06-03T11:17:37Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти. [[Медиа: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 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. [[Медиа:AlgTh-lec-7.pdf|pdf.]] <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]] <br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;. [[Медиа: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 мая. &lt;math&gt;BPP \subseteq P_{/poly}&lt;/math&gt; и &lt;math&gt;BPP \subseteq \Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа: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 /> <br /> == Практика Близнец ==<br /> Преподаватель: Близнец Иван Анатольевич<br /> <br /> Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br /> <br /> *[[Медиа:AlgTh-class-1.pdf|15 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets 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=15811 2018-06-03T11:17:20Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти. [[Медиа: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 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. [[Медиа:AlgTh-lec-7.pdf|pdf.]] <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]] <br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;. [[Медиа: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 мая. &lt;math&gt;BPP \subseteq P_{/poly}&lt;/math&gt; и &lt;math&gt;BPP \subseteq \Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа:AlgTh-lec-13.pdf|pdf.]]<br /> *15 мая Котрольная работа. [[Медиа:AlgTh-KR-I.pdf|part I]], [[Медиа:AlgTh-KR-II.pdf|part II]]<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 /> <br /> == Практика Близнец ==<br /> Преподаватель: Близнец Иван Анатольевич<br /> <br /> Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]<br /> <br /> *[[Медиа:AlgTh-class-1.pdf|15 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-KR-II.pdf&diff=15807 2018-05-28T13:34:05Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-KR-I.pdf&diff=15806 2018-05-28T13:33:50Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets 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=15805 2018-05-28T13:33:32Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти. [[Медиа: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 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. [[Медиа:AlgTh-lec-7.pdf|pdf.]] <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]] <br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;. [[Медиа: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 мая. &lt;math&gt;BPP \subseteq P_{/poly}&lt;/math&gt; и &lt;math&gt;BPP \subseteq \Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа:AlgTh-lec-13.pdf|pdf.]]<br /> *15 мая Котрольная работа. [[Медиа:AlgTh-KR-I.pdf|part I]], [[Медиа:AlgTh-KR-II.pdf|part II]]<br /> <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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets 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=15804 2018-05-28T13:32:55Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти. [[Медиа: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 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. [[Медиа:AlgTh-lec-7.pdf|pdf.]] <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]] <br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;. [[Медиа: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 мая. &lt;math&gt;BPP \subseteq P_{/poly}&lt;/math&gt; и &lt;math&gt;BPP \subseteq \Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа:AlgTh-lec-13.pdf|pdf.]]<br /> *15 мая Котрольная работа. [[Медиа:AlgTh-KR.pdf|pdf.]]<br /> <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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-lec-12.pdf&diff=15718 2018-05-10T11:26:05Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-lec-11.pdf&diff=15717 2018-05-10T11:25:02Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-lec-10.pdf&diff=15716 2018-05-10T11:24:31Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets 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=15715 2018-05-10T11:23:42Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти. [[Медиа: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 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. [[Медиа:AlgTh-lec-7.pdf|pdf.]] <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]] <br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;. [[Медиа: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 мая. &lt;math&gt;BPP \subseteq P_{/poly}&lt;/math&gt; и &lt;math&gt;BPP \subseteq \Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа: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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:FPT-home-10.pdf&diff=15712 2018-05-09T13:26:17Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:FPT-class-10.pdf&diff=15711 2018-05-09T13:04:27Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%9F%D0%B0%D1%80%D0%B0%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15710 2018-05-09T13:03:39Z

<p>Bliznets: /* Практика */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *16 february. Bounded search trees.<br /> ** FPT. Kernelization. Vertex Cover. Feedback Vertex Set. Closest String.<br /> *2 march. Kernelization.<br /> **Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability.<br /> *16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching.<br /> *23 march. Vertex Cover above Matching. Iterative Compression.<br /> ** Odd Cycle transversal &lt;math&gt;O^*(4^k)&lt;/math&gt;. Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal &lt;math&gt;O^*(3^k)&lt;/math&gt;.<br /> *30 march. Randomized methods.<br /> *6 april. &lt;math&gt;O^*(4^k)&lt;/math&gt; algorithm for k-path. Derandomization.<br /> *13 april. Dynamic programming over subsets. Integer linear programming. Graph minors and Robertson-Seymour theorem.<br /> *20 april. Important cuts. Edge Multiway Cut.<br /> *27 april. Important cuts in Directed graphs. Directed Feedback Vertex Set.<br /> <br /> == Практика ==<br /> <br /> *[[Медиа:FPT-home-1.pdf|16 february, &quot;Bounded search trees (HW).&quot;]]<br /> Надо оформить 5 самых сложных задач из Вами решенных.<br /> *[[Медиа:FPT-class-2.pdf|2 march, &quot;Kernelization.&quot;]]<br /> *[[Медиа:FPT-home-2.pdf|2 march, &quot;Kernelization(HW).&quot;]]<br /> *[[Медиа:FPT-home-3.pdf|16 march, &quot;Kernelization II(HW).&quot;]]<br /> *[[Медиа:FPT-class-4.pdf|23 march, &quot;Iterative Compression.&quot;]]<br /> *[[Медиа:FPT-home-4.pdf|23 march, &quot;Iterative Compression(HW).&quot;]]<br /> *[[Медиа:FPT-class-5.pdf|30 march, &quot;Randomized methods.&quot;]]<br /> *[[Медиа:FPT-home-5.pdf|30 march, &quot;Randomized methods(HW).&quot;]]<br /> *[[Медиа:FPT-class-6.pdf|06 april, &quot;Derandomization.&quot;]]<br /> *[[Медиа:FPT-home-6.pdf|06 april, &quot;Randomized methods and derandomization(HW).&quot;]]<br /> *[[Медиа:FPT-home-13.pdf|13 april, &quot;Miscellaneous(HW).&quot;]]<br /> *[[Медиа:FPT-home-8.pdf|20 april, &quot;Important cuts(HW).&quot;]]<br /> *[[Медиа:FPT-class-9.pdf|27 april, &quot;Important cuts II.&quot;]]<br /> *[[Медиа:FPT-home-9.pdf|27 april, &quot;Important cuts II(HW).&quot;]]<br /> *[[Медиа:FPT-class-10.pdf|03 may, &quot;W[1], W[2].&quot;]]<br /> *[[Медиа:FPT-home-10.pdf|03 may, &quot;W[1], W[2](HW).&quot;]]</div>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%9F%D0%B0%D1%80%D0%B0%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15709 2018-05-09T13:03:27Z

<p>Bliznets: /* Практика */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *16 february. Bounded search trees.<br /> ** FPT. Kernelization. Vertex Cover. Feedback Vertex Set. Closest String.<br /> *2 march. Kernelization.<br /> **Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability.<br /> *16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching.<br /> *23 march. Vertex Cover above Matching. Iterative Compression.<br /> ** Odd Cycle transversal &lt;math&gt;O^*(4^k)&lt;/math&gt;. Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal &lt;math&gt;O^*(3^k)&lt;/math&gt;.<br /> *30 march. Randomized methods.<br /> *6 april. &lt;math&gt;O^*(4^k)&lt;/math&gt; algorithm for k-path. Derandomization.<br /> *13 april. Dynamic programming over subsets. Integer linear programming. Graph minors and Robertson-Seymour theorem.<br /> *20 april. Important cuts. Edge Multiway Cut.<br /> *27 april. Important cuts in Directed graphs. Directed Feedback Vertex Set.<br /> <br /> == Практика ==<br /> <br /> *[[Медиа:FPT-home-1.pdf|16 february, &quot;Bounded search trees (HW).&quot;]]<br /> Надо оформить 5 самых сложных задач из Вами решенных.<br /> *[[Медиа:FPT-class-2.pdf|2 march, &quot;Kernelization.&quot;]]<br /> *[[Медиа:FPT-home-2.pdf|2 march, &quot;Kernelization(HW).&quot;]]<br /> *[[Медиа:FPT-home-3.pdf|16 march, &quot;Kernelization II(HW).&quot;]]<br /> *[[Медиа:FPT-class-4.pdf|23 march, &quot;Iterative Compression.&quot;]]<br /> *[[Медиа:FPT-home-4.pdf|23 march, &quot;Iterative Compression(HW).&quot;]]<br /> *[[Медиа:FPT-class-5.pdf|30 march, &quot;Randomized methods.&quot;]]<br /> *[[Медиа:FPT-home-5.pdf|30 march, &quot;Randomized methods(HW).&quot;]]<br /> *[[Медиа:FPT-class-6.pdf|06 april, &quot;Derandomization.&quot;]]<br /> *[[Медиа:FPT-home-6.pdf|06 april, &quot;Randomized methods and derandomization(HW).&quot;]]<br /> *[[Медиа:FPT-home-13.pdf|13 april, &quot;Miscellaneous(HW).&quot;]]<br /> *[[Медиа:FPT-home-8.pdf|20 april, &quot;Important cuts(HW).&quot;]]<br /> *[[Медиа:FPT-class-9.pdf|27 april, &quot;Important cuts II.&quot;]]<br /> *[[Медиа:FPT-home-9.pdf|27 april, &quot;Important cuts II(HW).&quot;]]<br /> *[[Медиа:FPT-class-10.pdf|03 may, &quot;W[1], W[2].&quot;]]<br /> *[[Медиа:FPT-class-10.pdf|03 may, &quot;W[1], W[2](HW).&quot;]]</div>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-lec-7.pdf&diff=15707 2018-05-08T15:58:50Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets 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=15706 2018-05-08T15:58:13Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти. [[Медиа: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 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. [[Медиа:AlgTh-lec-7.pdf|pdf.]] <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]] <br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;. [[Медиа:AlgTh-lec-9.pdf|pdf.]] <br /> *17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br /> *24 апреля. Путь с логарифмической памятью. <br /> *25 апреля. Схемы. <br /> *08 мая. &lt;math&gt;BPP \subseteq P_{/poly}&lt;/math&gt; и &lt;math&gt;BPP \subseteq \Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа: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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-lec-4.pdf&diff=15705 2018-05-08T15:57:00Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets 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=15704 2018-05-08T15:56:36Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти. [[Медиа: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 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]] <br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;. [[Медиа:AlgTh-lec-9.pdf|pdf.]] <br /> *17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br /> *24 апреля. Путь с логарифмической памятью. <br /> *25 апреля. Схемы. <br /> *08 мая. &lt;math&gt;BPP \subseteq P_{/poly}&lt;/math&gt; и &lt;math&gt;BPP \subseteq \Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа: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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-lec-5.pdf&diff=15703 2018-05-08T15:55:42Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets 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=15702 2018-05-08T15:55:06Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. [[Медиа:AlgTh-lec-5.pdf|pdf.]] <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. [[Медиа:AlgTh-lec-6.pdf|pdf.]] <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]] <br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;. [[Медиа:AlgTh-lec-9.pdf|pdf.]] <br /> *17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br /> *24 апреля. Путь с логарифмической памятью. <br /> *25 апреля. Схемы. <br /> *08 мая. &lt;math&gt;BPP \subseteq P_{/poly}&lt;/math&gt; и &lt;math&gt;BPP \subseteq \Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа: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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-lec-6.pdf&diff=15701 2018-05-08T15:54:03Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets 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=15700 2018-05-08T15:51:21Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. [[Медиа:AlgTh-lec-6.pdf|pdf.]] <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]] <br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;. [[Медиа:AlgTh-lec-9.pdf|pdf.]] <br /> *17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br /> *24 апреля. Путь с логарифмической памятью. <br /> *25 апреля. Схемы. <br /> *08 мая. &lt;math&gt;BPP \subseteq P_{/poly}&lt;/math&gt; и &lt;math&gt;BPP \subseteq \Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа: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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-lec-8.pdf&diff=15699 2018-05-08T15:48:01Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets 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=15698 2018-05-08T15:47:24Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]] <br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;. [[Медиа:AlgTh-lec-9.pdf|pdf.]] <br /> *17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br /> *24 апреля. Путь с логарифмической памятью. <br /> *25 апреля. Схемы. <br /> *08 мая. &lt;math&gt;BPP \subseteq P_{/poly}&lt;/math&gt; и &lt;math&gt;BPP \subseteq \Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа: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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-lec-9.pdf&diff=15697 2018-05-08T15:46:25Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets 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=15696 2018-05-08T15:45:07Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;. [[Медиа:AlgTh-lec-9.pdf|pdf.]] <br /> *17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br /> *24 апреля. Путь с логарифмической памятью. <br /> *25 апреля. Схемы. <br /> *08 мая. &lt;math&gt;BPP \subseteq P_{/poly}&lt;/math&gt; и &lt;math&gt;BPP \subseteq \Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа: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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets 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=15695 2018-05-08T11:05:12Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;.<br /> *17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br /> *24 апреля. Путь с логарифмической памятью. <br /> *25 апреля. Схемы. <br /> *08 мая. &lt;math&gt;BPP \subseteq P_{/poly}&lt;/math&gt; и &lt;math&gt;BPP \subseteq \Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа: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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets 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=15694 2018-05-08T11:04:37Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;.<br /> *17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br /> *24 апреля. Путь с логарифмической памятью. <br /> *25 апреля. Схемы. <br /> *08 мая. Класс BPP подкласс &lt;math&gt;P_{/poly}&lt;/math&gt; и &lt;math&gt;\Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа: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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets 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=15693 2018-05-08T11:04:26Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;.<br /> *17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br /> *24 апреля. Путь с логарифмической памятью. <br /> *25 апреля. Схемы. <br /> *08 мая. Класс BPP подкласс &lt;math&gt;P_{/poly}&lt;/math&gt; и &lt;math&gt;\Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани [[Медиа: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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets 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=15692 2018-05-08T11:04:11Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;.<br /> *17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br /> *24 апреля. Путь с логарифмической памятью. <br /> *25 апреля. Схемы. <br /> *08 мая. Класс BPP подкласс &lt;math&gt;P_{/poly}&lt;/math&gt; и &lt;math&gt;\Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа: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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-lec-13.pdf&diff=15691 2018-05-08T11:03:50Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets 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=15690 2018-05-08T11:03:30Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;.<br /> *17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br /> *24 апреля. Путь с логарифмической памятью. <br /> *25 апреля. Схемы. <br /> *08 мая. Класс BPP подкласс &lt;math&gt;P_{/poly}&lt;/math&gt; и &lt;math&gt;\Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани. [[Медиа:AlgTh-lec-13.pdf|08 мая, &quot;pdf.&quot;]]<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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets 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=15689 2018-05-08T11:01:51Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;.<br /> *17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br /> *24 апреля. Путь с логарифмической памятью. <br /> *25 апреля. Схемы. <br /> *08 мая. Класс BPP подкласс &lt;math&gt;P_{/poly}&lt;/math&gt; и &lt;math&gt;\Sigma^p_2&lt;/math&gt;. Теорема Вэлианта-Вазирани.<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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets 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=15688 2018-05-07T17:48:58Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;.<br /> *17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. <br /> *24 апреля. Схемы. <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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-home-12.pdf&diff=15590 2018-05-02T15:28:28Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets 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=15589 2018-05-02T15:28:07Z

<p>Bliznets: /* Практика Близнец */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;.<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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<br /> *[[Медиа:AlgTh-home-12.pdf|26 апреля, &quot;Схемы(ДЗ).&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%9F%D0%B0%D1%80%D0%B0%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15586 2018-05-01T20:56:20Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *16 february. Bounded search trees.<br /> ** FPT. Kernelization. Vertex Cover. Feedback Vertex Set. Closest String.<br /> *2 march. Kernelization.<br /> **Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability.<br /> *16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching.<br /> *23 march. Vertex Cover above Matching. Iterative Compression.<br /> ** Odd Cycle transversal &lt;math&gt;O^*(4^k)&lt;/math&gt;. Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal &lt;math&gt;O^*(3^k)&lt;/math&gt;.<br /> *30 march. Randomized methods.<br /> *6 april. &lt;math&gt;O^*(4^k)&lt;/math&gt; algorithm for k-path. Derandomization.<br /> *13 april. Dynamic programming over subsets. Integer linear programming. Graph minors and Robertson-Seymour theorem.<br /> *20 april. Important cuts. Edge Multiway Cut.<br /> *27 april. Important cuts in Directed graphs. Directed Feedback Vertex Set.<br /> <br /> == Практика ==<br /> <br /> *[[Медиа:FPT-home-1.pdf|16 february, &quot;Bounded search trees (HW).&quot;]]<br /> Надо оформить 5 самых сложных задач из Вами решенных.<br /> *[[Медиа:FPT-class-2.pdf|2 march, &quot;Kernelization.&quot;]]<br /> *[[Медиа:FPT-home-2.pdf|2 march, &quot;Kernelization(HW).&quot;]]<br /> *[[Медиа:FPT-home-3.pdf|16 march, &quot;Kernelization II(HW).&quot;]]<br /> *[[Медиа:FPT-class-4.pdf|23 march, &quot;Iterative Compression.&quot;]]<br /> *[[Медиа:FPT-home-4.pdf|23 march, &quot;Iterative Compression(HW).&quot;]]<br /> *[[Медиа:FPT-class-5.pdf|30 march, &quot;Randomized methods.&quot;]]<br /> *[[Медиа:FPT-home-5.pdf|30 march, &quot;Randomized methods(HW).&quot;]]<br /> *[[Медиа:FPT-class-6.pdf|06 april, &quot;Derandomization.&quot;]]<br /> *[[Медиа:FPT-home-6.pdf|06 april, &quot;Randomized methods and derandomization(HW).&quot;]]<br /> *[[Медиа:FPT-home-13.pdf|13 april, &quot;Miscellaneous(HW).&quot;]]<br /> *[[Медиа:FPT-home-8.pdf|20 april, &quot;Important cuts(HW).&quot;]]<br /> *[[Медиа:FPT-class-9.pdf|27 april, &quot;Important cuts II.&quot;]]<br /> *[[Медиа:FPT-home-9.pdf|27 april, &quot;Important cuts II(HW).&quot;]]</div>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%9F%D0%B0%D1%80%D0%B0%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15585 2018-05-01T20:56:09Z

<p>Bliznets: /* Лекции */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *16 february. Bounded search trees.<br /> ** FPT. Kernelization. Vertex Cover. Feedback Vertex Set. Closest String.<br /> *2 march. Kernelization.<br /> **Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability.<br /> *16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching.<br /> *23 march. Vertex Cover above Matching. Iterative Compression.<br /> ** Odd Cycle transversal &lt;math&gt;O^*(4^k)&lt;/math&gt;. Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal &lt;math&gt;O^*(3^k)&lt;/math&gt;.<br /> *30 march. Randomized methods.<br /> *6 april. &lt;math&gt;O^*(4^k)&lt;/math&gt; algorithm for k-path. Derandomization.<br /> *13 april. Dynamic programming over subsets. Integer linear programming. Graph minors and Robertson-Seymour theorem.<br /> *20 april. Important cuts. Edge Multiway Cut.<br /> *20 april. Important cuts in Directed graphs. Directed Feedback Vertex Set.<br /> <br /> == Практика ==<br /> <br /> *[[Медиа:FPT-home-1.pdf|16 february, &quot;Bounded search trees (HW).&quot;]]<br /> Надо оформить 5 самых сложных задач из Вами решенных.<br /> *[[Медиа:FPT-class-2.pdf|2 march, &quot;Kernelization.&quot;]]<br /> *[[Медиа:FPT-home-2.pdf|2 march, &quot;Kernelization(HW).&quot;]]<br /> *[[Медиа:FPT-home-3.pdf|16 march, &quot;Kernelization II(HW).&quot;]]<br /> *[[Медиа:FPT-class-4.pdf|23 march, &quot;Iterative Compression.&quot;]]<br /> *[[Медиа:FPT-home-4.pdf|23 march, &quot;Iterative Compression(HW).&quot;]]<br /> *[[Медиа:FPT-class-5.pdf|30 march, &quot;Randomized methods.&quot;]]<br /> *[[Медиа:FPT-home-5.pdf|30 march, &quot;Randomized methods(HW).&quot;]]<br /> *[[Медиа:FPT-class-6.pdf|06 april, &quot;Derandomization.&quot;]]<br /> *[[Медиа:FPT-home-6.pdf|06 april, &quot;Randomized methods and derandomization(HW).&quot;]]<br /> *[[Медиа:FPT-home-13.pdf|13 april, &quot;Miscellaneous(HW).&quot;]]<br /> *[[Медиа:FPT-home-8.pdf|20 april, &quot;Important cuts(HW).&quot;]]<br /> *[[Медиа:FPT-class-9.pdf|27 april, &quot;Important cuts II.&quot;]]<br /> *[[Медиа:FPT-home-9.pdf|27 april, &quot;Important cuts II(HW).&quot;]]</div>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:FPT-class-9.pdf&diff=15584 2018-05-01T20:54:22Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:FPT-home-9.pdf&diff=15583 2018-05-01T20:54:08Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%9F%D0%B0%D1%80%D0%B0%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%B2%D0%B5%D1%81%D0%BD%D0%B0_2018&diff=15582 2018-05-01T20:53:51Z

<p>Bliznets: /* Практика */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *16 february. Bounded search trees.<br /> ** FPT. Kernelization. Vertex Cover. Feedback Vertex Set. Closest String.<br /> *2 march. Kernelization.<br /> **Feedback Arc Set in Tournaments. Edge Clique Cover. Crown Decomposition. Vertex Cover. Maximum Satisfiability.<br /> *16 march. Sunflower lemma. Kernelization for Vertex Cover using LP. Vertex Cover above LP branching.<br /> *23 march. Vertex Cover above Matching. Iterative Compression.<br /> ** Odd Cycle transversal &lt;math&gt;O^*(4^k)&lt;/math&gt;. Variable Deletion Almost 2-SAT. Feedback Vertex Set in Tournaments. Feedback Vertex Set. Odd Cycle Transversal &lt;math&gt;O^*(3^k)&lt;/math&gt;.<br /> *30 march. Randomized methods.<br /> *6 april. &lt;math&gt;O^*(4^k)&lt;/math&gt; algorithm for k-path. Derandomization.<br /> *13 april. Dynamic programming over subsets. Integer linear programming. Graph minors and Robertson-Seymour theorem.<br /> *20 april. Important cuts.<br /> <br /> == Практика ==<br /> <br /> *[[Медиа:FPT-home-1.pdf|16 february, &quot;Bounded search trees (HW).&quot;]]<br /> Надо оформить 5 самых сложных задач из Вами решенных.<br /> *[[Медиа:FPT-class-2.pdf|2 march, &quot;Kernelization.&quot;]]<br /> *[[Медиа:FPT-home-2.pdf|2 march, &quot;Kernelization(HW).&quot;]]<br /> *[[Медиа:FPT-home-3.pdf|16 march, &quot;Kernelization II(HW).&quot;]]<br /> *[[Медиа:FPT-class-4.pdf|23 march, &quot;Iterative Compression.&quot;]]<br /> *[[Медиа:FPT-home-4.pdf|23 march, &quot;Iterative Compression(HW).&quot;]]<br /> *[[Медиа:FPT-class-5.pdf|30 march, &quot;Randomized methods.&quot;]]<br /> *[[Медиа:FPT-home-5.pdf|30 march, &quot;Randomized methods(HW).&quot;]]<br /> *[[Медиа:FPT-class-6.pdf|06 april, &quot;Derandomization.&quot;]]<br /> *[[Медиа:FPT-home-6.pdf|06 april, &quot;Randomized methods and derandomization(HW).&quot;]]<br /> *[[Медиа:FPT-home-13.pdf|13 april, &quot;Miscellaneous(HW).&quot;]]<br /> *[[Медиа:FPT-home-8.pdf|20 april, &quot;Important cuts(HW).&quot;]]<br /> *[[Медиа:FPT-class-9.pdf|27 april, &quot;Important cuts II.&quot;]]<br /> *[[Медиа:FPT-home-9.pdf|27 april, &quot;Important cuts II(HW).&quot;]]</div>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-class-12.pdf&diff=15565 2018-04-28T19:23:21Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets 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=15564 2018-04-28T19:22:54Z

<p>Bliznets: /* Практика Близнец */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;.<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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности.&quot;]]<br /> *[[Медиа:AlgTh-class-12.pdf|26 апреля, &quot;Схемы.&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:AlgTh-class-11.pdf&diff=15530 2018-04-25T20:53:42Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets 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=15529 2018-04-25T20:53:28Z

<p>Bliznets: /* Практика Близнец */</p> <hr /> <div>Преподаватель: Близнец Иван Анатольевич ('''iabliznets@gmail.com''')<br /> <br /> == Лекции ==<br /> <br /> *13 февраля. Машина Тьюринга. <br /> *20 февраля. Универсальная машина Тьюринга. Класс NP. <br /> *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. <br /> *06 марта. Машины с оракульным доступом. Построение языка B, такого что &lt;math&gt;P^B \neq NP^B&lt;/math&gt;. Сложность по памяти.<br /> *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. <br /> *20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. <br /> *27 марта. Полиномиальная иерархия. &lt;math&gt;Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]&lt;/math&gt;. <br /> *03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный &lt;math&gt;O^*(4^k)&lt;/math&gt; алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.<br /> *10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за &lt;math&gt;n\ln{n}+cn&lt;/math&gt;.<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 февраля, &quot;Машина Тьюринга.&quot;]]<br /> *[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, &quot;Машина Тьюринга(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-2.pdf|20 февраля, &quot;Класс NP.&quot;]]<br /> *[[Медиа:AlgTh-home-2.pdf|20 февраля, &quot;Класс NP(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-3.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени.&quot;]]<br /> *[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, &quot;Классы NP, coNP, иерархия по времени(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-4.pdf|06 марта, &quot;Оракульные машины и PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, &quot;PSPACE.&quot;]]<br /> *[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, &quot;PSPACE(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-6.pdf|20 марта, &quot;Класс NL.&quot;]]<br /> *[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, &quot;Класс NL(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, &quot;Класс NL(ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-7.pdf|27 марта, &quot;Полиномиальная иерархия.&quot;]]<br /> *[[Медиа:AlgTh-home-7.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-7-hints.pdf|27 марта, &quot;Полиномиальная иерархия (ДЗ+подсказки).&quot;]]<br /> *[[Медиа:AlgTh-class-8.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы.&quot;]]<br /> *[[Медиа:AlgTh-home-8-added.pdf|3 апреля, &quot;Вероятностные алгоритмы. Вероятностные классы(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9.pdf|10 апреля, &quot;Предыдущие задачи(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, &quot;Предыдущие задачи+подсказки(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, &quot;Оценки Чернова.&quot;]]<br /> *[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, &quot;Оценки Чернова. Элементы линейного программирования(ДЗ).&quot;]]<br /> *[[Медиа:AlgTh-class-11.pdf|24 апреля, &quot;Путь. Увеличение вероятности&quot;]]<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>

Bliznets http://mit.spbau.ru/sewiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:FPT-home-8.pdf&diff=15520 2018-04-25T07:13:14Z

<p>Bliznets: </p> <hr /> <div></div>

Bliznets