Как стать автором
Обновить
168
Карма
0
Рейтинг
Саша Куликов @alexanderskulikov

Исследователь

  • Подписчики 65
  • Подписки 18

Перевод учебника по алгоритмам

Нелегально в интернете легко найти, да. (Издательство Макгроухилл попросило авторов удалить пдфки с их страниц.)

Перевод учебника по алгоритмам

Специализация по спортивному программированию на Курсере

О, спасибо! Когда-нибудь вычитаем. Нам бы пока доделать оставшиеся курсы.

Специализация по спортивному программированию на Курсере

Да нет, мы правим и такие мелкие замечания.

Специализация по спортивному программированию на Курсере

Можно репортить вот так: yadi.sk/i/hsPcfByz3ZUMCL

Специализация по спортивному программированию на Курсере

А вы там, на Курсере, сообщаете об увиденных неточностях?

Специализация по спортивному программированию на Курсере

Там не ведущие, а преподаватели. С опытом, что важно. Включите субтитры, если так вам тяжело.

Специализация по спортивному программированию на Курсере

есть под словом «записывайтесь» =)

Специализация по спортивному программированию на Курсере

Это, кстати, не первые такие курсы =)

Бакалавриат СПбГУ

Бакалавриат СПбГУ

Все на ВО. Поступающие БВИ селятся по умолчанию на ВО, остальные — в Петергоф, но с возможностью перевестись на ВО.

Бакалавриат СПбГУ

В СПбГУ образовательные программы сейчас не привязаны к факультетам формально. Обучение будет вестись на ВО на трёх перечисленных выше программах.

Магистратура по теоретической информатике в СПбГУ

Но почему бы и не приехать из Беларуси? Вот указанный выше Иван Близнец так и сделал, например, в своё время =)

Две красивые задачи по алгоритмам

В общем, как все уже поняли, факториал тут не особо поможет. Это мне напомнило почему-то теорему Вильсона. Она даёт необходимое и достаточное условие того, что число простое. Но алгоритмически её трудно использовать.

Две красивые задачи по алгоритмам

Бинго! =) Попроще первой, ога.

Две красивые задачи по алгоритмам

Но где же \Omega(n)? Мы же просто ходим по массиву. Если уж быть совсем формальным, то приведённое в посте решение использует O(\log n) доп. памяти, да (на наши два-три указателя). Псевдокод лениво писать, но могу на вопросы ответить, если что-то всё же недосказанным осталось.

Алгоритмы расщепления и числа Ван-дер-Вардена

Ладно, не буду я занудствовать про то, всё или не всё сводится. =)

Но сведение этой задачи к сату есть, например, у Кнута. Весь код состоит из пары методов из четырёх строчек. Строка длины 177 нашлась (солвером Кнута же!) за несколько секунд. Невыполнимость формулы для 178 доказалась на моём самом обычном ноуте за пару минут.

bash-3.2$ ./sat-waerden 5 5 178 | ./sat13 (178 variables, 7744 clauses, 38720 literals successfully read) ~ UNSAT Altogether 96953+18950937986 mems, 341878 bytes, 1000830 nodes, 921919 clauses learned (ave 18.6->11.9), 678634 memcells. (374087 learned clauses were trivial.) (352116 learned clauses were discarded.) (1506 clauses were subsumed on-the-fly.)

Информация

В рейтинге
Не участвует
Откуда
Санкт-Петербург, Санкт-Петербург и область, Россия
Работает в
Дата рождения
Зарегистрирован
Активность