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

Спецсеминар проводится осенью 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" (докладчик Александр Мораховский)
Продолжение следует ...

Список тем докладов (будет дополняться)

  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" Также см. дискуссию здесь.

Бонусы

    За оппонирование3 (1 бонус, по итогам первых двух занятий): Семен Петров, Никита Гаевой, Михаил Мрыхин, Владислав Макаров.
1. В исключительных случаях, по предвaрительному согласованию с руководителем семинара, можно обменять экстра-бонус на отсутствие на паре по уважительной причине.

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

3. Возможны ошибки, потому что я (Е. А.) еще не всех запомнила. В случае обнаружения - пишите email. И задавайте/продолжайте задавать вопросы докладчикам!