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

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

Правила

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

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

Объявления

Теперь занятия проходят в 102 аудитории. Там есть проектор!

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

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

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

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