Спецсеминар Модели вычислений

Спецсеминар проводится осенью 2018 для студентов Бакалавриата "Математика" в СПбГУ каждую среду в 9:30. Руководитель семинара Елена Храмцова.

Правила

По итогам спецсеминара студенты получают (или не получают) зачет. Обязательное требование для получения зачета: сделать хотя бы один доклад на семинаре. Для получения зачета автоматом, достаточно, вдобавок к обязательному требованию, выполнить следующие два:1 (i) посетить почти все занятия (максимум три пропуска) и (ii) получить хотя бы один бонус. Бонус дается за активное оппонирование докладчику,2 за подготовку и использование слайдов при докладе, или за второй доклад на семинаре. Если достаточные условия получения зачета автоматом не выполнены, то на зачете могут задаваться вопросы по любым из пройденных тем, в том числе - и особенно - по темам пропущенных занятий, если такие имеются.

В рамках содействия участникам семинара, поощряется создание и распространение кратких содержаний (summary) докладов. Сделанные summary будут (также) появляться на этой странице.

Содержание занятий

  1. 5 сентября: Модель Сложи-и-Разрежь. B. An et al. "Computing 3SAT on a Fold-and-Cut Machine" (докладчик Борис Золотов)
  2. 12 сентября: Замощения плоскости и автоматы Мили. J. Kari "A small aperiodic set of Wang tiles" (докладчик Денис Воронин)
  3. 19 cентября: Остановка машин Тьюринга с ограниченной памятью. M. Sipser ''Halting space-bounded computations.'' (докладчик Никита Гаевой)
  4. 26 сентября: Модели вычислений и игры. PSPACE-полнота паззла ''Выезд с парковки'' (sliding-block puzzle). R. Hearn, E. Demaine "PSPACE-completeness of sliding-block puzzles and other problems through the non-deterministic constraint logic model of computation." (докладчик Анастасия Софронова)
  5. 3 октября: NP-полнота евклидовой задачи о коммивояжёре C. Papadimitrou "The Euclidean travelling salesman problem is NP-complete" (докладчик Владислав Макаров)
  6. 10 октября: Вычислительная сложность "песчаных куч" (sandpiles). C. Moore, M. Nilsson "The computational complexity of sandpiles" (докладчик Дмитрий Крачун)
  7. 17 октября: Модели вычислений и игры. Логика ограничений. E. Demaine, R. Hearn "Constraint Logic: A Uniform Framework for Modeling Computation as Games" (докладчик Семен Петров)
  8. 24 октября: Геометрические алгоритмы в модели с логарифмической памятью.T. Asano, W. Mulzer, G. Rote, and Y. Wang "Constant-Work-space algorithms for geometric problems" (докладчик Александр Мораховский)
  9. 31 октября: Модели вычислений и игры. Логика ограничений. Часть 2. E. Demaine, R. Hearn "Constraint Logic: A Uniform Framework for Modeling Computation as Games" (докладчик Семен Петров)
  10. 7 ноября: Пересечение автоматов и поиск треугольников в графе. M. de Oliveira Oliveira, M. Wehar "Intersection non-emptiness and hardness within polynomial time" (докладчик Татьяна Белова)
  11. 14 ноября: Клеточные автоматы: правило 110. Вычислительная универсальность. M. Cook ''Universality in elementary cellular automata'' (докладчик Борис Золотов)
  12. 21 ноября: Клеточные автоматы: правило 110. P-полнотa в случае ограниченного времени. T. Neary, D. Woods ''P-completeness of cellular automaton rule 110'' (докладчик Валентин Андреев)
  13. 28 ноября: Иерархия многоголовочных конечных автоматов A. Yao, R. Rivest ''k+1 heads are better than k'' (докладчик Михаил Мрыхин)
  14. 5 декабря: Неоднозначные автоматы H. Leung ''Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata'' и H. Leung ''Descriptional Complexity of NFA of Different Ambiguity'' (докладчик Александр Мораховский)
  15. 12 декабря: Graph-walking automata. (докладчик Денис Воронин)

Список тем докладов

  1. (Взята) Модель Сложи-и-Разрежь. B. An et al. "Computing 3SAT on a Fold-and-Cut Machine" (рекомендуется как тема первого доклада).
  2. (Взята) Замощения плоскости и автоматы Мили. J. Kari "A small aperiodic set of Wang tiles" слайды автора
  3. (Взята) Клеточные автоматы: правило 110. Вычислительная универсальность. M. Cook ``Universality in elementary cellular automata''
  4. (Взята) Клеточные автоматы: правило 110. P-полнотa в случае ограниченного времени. T. Neary, D. Woods ``P-completeness of cellular automaton rule 110''
  5. (Взята) Модели вычислений и игры. PSPACE-полнота паззла ''Выезд с парковки'' (sliding-block puzzle). R. Hearn, E. Demaine "PSPACE-completeness of sliding-block puzzles and other problems through the non-deterministic constraint logic model of computation."
  6. (Взята) Модели вычислений и игры. Логика ограничений. E. Demaine, R. Hearn "Constraint Logic: A Uniform Framework for Modeling Computation as Games"
  7. (Взята) Остановка машин Тьюринга с ограниченной памятью. M. Sipser ``Halting space-bounded computations.''
  8. (Взята) NP-трудные и NP-полные геометрические задачи.
  9. (Взята) Пересечение автоматов и поиск треугольников в графе. M. de Oliveira Oliveira, M. Wehar "Intersection non-emptiness and hardness within polynomial time"
  10. Какие функции лучше не добавлять в RAM.A.Bertoni, G.Mauri, N.Sabadini "Simulations Among Classes of Random Access Machines and Equivalence Among Numbers Succinctly Represented" Также см. дискуссию здесь.

Предварительные результаты по выполненным условиям получения зачета

Обязательное условие к получению зачета.

Хотя бы один доклад сделали: Семен Петров, Никита Гаевой, Михаил Мрыхин, Владислав Макаров, Анастасия Софронова, Александр Мораховский, Татьяна Белова, Борис Золотов, Валентин Андреев, Денис Воронин, Дмитрий Крачун.

Зачет автоматом получают:

Семен Петров, Никита Гаевой, Михаил Мрыхин, Владислав Макаров, Анастасия Софронова, Борис Золотов, Денис Воронин, Александр Мораховский, Татьяна Белова, Валентин Андреев.

1. В исключительных случаях, по предвaрительному согласованию с руководителем семинара, можно обменять экстра-бонус на отсутствие на паре по уважительной причине.

2. Бонус за оппонирование можно получить, если задавать содержательные (по мнению проводящего семинар преподавателя) вопросы во время доклада. Для этого рекомендуется ознакомиться с материалами, по которым делается доклад, заранее.