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

Спецсеминар проводится весной 2019 для студентов 3 курса Бакалавриата "Математика" в СПбГУ каждую среду в 11:05 в ауд. 102. Руководитель семинара Елена Арсеньева (Храмцова).

Правила

По итогам спецсеминара студенты получают (или не получают) зачет. На каждом занятии один из участников делает доклад, и, может быть, один оппонирует. Так как участников мало, оппонирование - по желанию. Оппонент присылает руководителю, конфидециально, конструктивную рецензию на доклад (очень краткое описание (1-3 абзаца), оценка от -3 до 3, с обоснованием). Обязательное требование для получения зачета: сделать два (зависит от итогового количества участников, и количества гостевых лекций) доклада на семинаре. Хорошо сделанные рецензии и хорошие слайды доклада, присланные руководителю, считаются бонусом на зачете. (куски статьи, положенные в powerpoint или даже в beamer, не являются хорошими слайдами!)

Присланные слайды будут появляться на этой странице.

Пусть У = {Валентин, Алиса, Семен} - множество формальных участников семинара.

Правило: Если на занятии ни одного формального участника из У не присутствует в качестве слушателя, то занятие происходит все равно, а во время зачета материалы такого проигнорированного всеми слушателями из У занятия спрашиваются в деталях в жанре экзамена (в любых деталях статьи нужно будет хорошо ориентироваться для получения зачета). В частности, если пришел докладчик из У, и даже какие-то слушатели не из У, и не пришли никакие слушатели из У, это правило выполняется.

Чтобы не допустить выполнения правила выше, если Вы из У и планируете отсутствовать на занятии, предупреждайте об этом меня и остальных членов У не позднее 18:00 предшествующего дня (вторника перед занятием).

Объявления

Правила относительно посещения изменились. Читайте внимательно.

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

  1. 13 февраля: Вводное занятие.
  2. 20 февраля: Модель Real RAM, и какие функции лучше в нее не добавлять. (докладчик Илья Ольховский)
  3. 27 февраля: Клеточные автоматы: задача о взводе стрелков I. (докладчик Валентин Андреев)
  4. 6 марта: Клеточные автоматы: задача о взводе стрелков II. (докладчик Валентин Андреев)
  5. 13 марта: Двусторонние автоматы I. (доклад Алисы Баркарь)
  6. 20 марта: ГОСТЕВАЯ ЛЕКЦИЯ Анастасии Софроновой по собственным исследованиям. summary.
  7. 27 марта: занятия не было в связи с отсутствием слушателей.
  8. 3 апреля: Двусторонние автоматы II. (доклад Алисы Баркарь)
  9. 10 апреля: Вероятностные автоматы. (доклад Дениса Воронина)
  10. 17 апреля: ГОСТЕВАЯ ЛЕКЦИЯ Елизаветы Сажневой по собственным исследованиям. статья, summary.
  11. 24 апреля: ГОСТЕВАЯ ЛЕКЦИЯ Владислава Макарова по собственным исследованиям. статья, summary.
  12. 8 мая: Доклад Семена Петрова I.
  13. 15 мая: Доклад Семена Петрова II.
  14. 22 мая: зачет.

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

  1. Сложность конечных автоматов над односимвольным алфавитом. M. Chrobak "Finite automata and unary languages" + errata
  2. (Взята Валентином Андреевым) Клеточные автоматы: задача о взводе стрелков. An optimum solution to the firing squad synchronization problem, An 8-State Minimal Time Solution to the Firing Squad Sinchronization Problem , A six-state minimal time solution to the firing squad synchronization problem
  3. (Взята Алисой Баркарь) Двусторонние автоматы. Converting two-way nondeterministic unary automata into simpler automata,OPTIMAL SIMULATIONS BETWEEN UNARY AUTOMATA, Complementing two-way finite automata
  4. Вероятностные автоматы. Probabilistic two-way machines, Bounded error probabilistic finite state automata
  5. Автоматы, управляемые входом (input-driven automata).
  6. «Маленькая память» --- память o(log n). On tape bounds for single letter alphabet language processing, Hierarchies of memory limited computations, Tally versions of the Savitch and Immerman–Szelepcsényi theorems for sublogarithmic space
  7. (Взята) Модель Real RAM, и какие функции лучше в нее не добавлять. A.Bertoni, G.Mauri, N.Sabadini "Simulations Among Classes of Random Access Machines and Equivalence Among Numbers Succinctly Represented" (pdf) Также см. дискуссию здесь