?

Log in

No account? Create an account

Категория: наука

Я думаю, у каждого из нас (имеющих какое-то отношение к науке/образованию/...) в каждой предметной области есть своя любимая задача. Сегодня я хочу поделиться моей любимой задачей в теории формальных языков и конечных автоматов.

Немного терминологии для тех, кто позабыл ее с младших курсов.

Пусть w — слово (строка из символов над заданным алфавитом, возможно пустая).
Обозначение   есть количество вхождений символа a в строку w (целое неотрицательное число).

Пусть W — множество слов. Множество слов еще называют языком.
Тогда W* — так называемая «звездочка Клини», или «замыкание Клини». Это множество всех слов, которые могут получиться из данных путем разнообразных приписываний их друг к другу множество раз (возможно 0 раз, тогда получится пустая строка). Например,
{"foo", "bar"}* = {"", "foo", "bar", "foobar", "barfoo", "foofoo", "barbar", "foofoofoo", "foofoobar", "foobarfoo", "foobarbar", "barfoofoo", ... }
Как видно, в этом случае множество получилось бесконечное.

Что такое конечный автомат, воспринимающий заданный язык, я здесь объяснять не буду, долго. Предположим, что читатели это уже знают :)

Так вот, задача: над алфавитом из двух символов a, b построить конечный автомат, воспринимающий следующий язык:



Другими словами: замыкание Клини такого множества, которое содержит все такие строки, в которых количество вхождений символа a не равно количеству вхождений символа b.

Смело приглашаю пробовать и делиться решениями в комментариях ;) Правильные ответы скринятся.
Простой онлайновый редактор, который упростит вам рисование автоматов и вставку картинок — yEd.

UPD: Уже много правильных ответов, открываю. Да, это действительно все строки, даже пустая (ибо пустая строка по определению входит в замыкание Клини любого множества). Тысячу и одно доказательство найдете в комментариях.

Цели курса


  • Продемонстрировать непривычный подход к решению задач разработки программных систем, отличный от традиционно преподаваемого в учебных заведениях, однако набирающий популярность в индустрии Software Development.

  • Привить умение анализировать поставленную задачу, выделять в ней абстракцию, производить разбивку на подзадачи. Дать понять преимущества манипулированиями абстракциями предметной области в коде, в отличие от низкоуровневых команд языка программирования.

  • Научить использовать полезные идиомы, свойственные функциональному подходу, вне зависимости от используемого языка и решаемой задачи.

  • Показать практическое насущное применение ФП. В числе примеров:
    • Алгоритмы параллельного и асинхронного программирования, которые сейчас являются одной из наиболее активно исследуемых областей в IT. В курсе им уделено особое внимание.
    • Принципы работы с объемными потоками/списками данных.
    • Парсинг текста, создание DSL (Domain Specific Language).
  • Познакомить с некоторыми математическими основаниями, на которых строится предмет Computer Science. Показать, что знания теории алгоритмов действительно применимы в практической разработке.


Предварительные знанияСвернуть )

ОрганизацияСвернуть )

Программа курсаСвернуть )

- - - - - - - - - - - - - - - - - -
Планируется к чтению вашим покорной слугой в следующем семестре на факультете ИПСА Киевского политехнического института.

В значительной мере основан на курсе Евгения antilamer Кирпичева, и на SICP, в числе источников также «ПФП», Brian McNamara, Харрисон, курс Дмитрия Сошникова и, конечно же, Guy E. Blelloch. Это не считая собственной практики ACM-олимпиад и алгоритмов плюс еще дюжины различных второстепенных источников.

Кто что скажет?
Всем-всем-всем очень рекомендую лекцию Александра Степанова, прочитанную им в Яндексе.
Сочинять сейчас для блога еще восхваленный текст нет сил, поэтому просто скопирую свои впечатления с разных источников: Твиттера, джаббера и т.д.

Александр Степанов дал в Яндексе просто потрясающую лекцию. С чем-то можно спорить, чему-то — восхищаться, но смотреть всем обязательно!


— там две части. первая более интересна математикам, наверное, а вторая - всем, но больше программистам. но для схватывания общей мысли лучше все же смотреть единым потоком мысли, всю сразу

— А о чем она?

— сложно сказать) начиналось все с того, что его попросили рассказать об обобщенном программировании. он взял пример Главного Алгоритма (тут нет иронии) - алгоритм Эвклида - и показал, как он менялся на протяжении 2500 лет. так сказать, наглядная иллюстрация идеи обобщения, шаблонизации и пр. это первая половина.
а во второй половине, когда исторический экскурс закончился, он плавно перешел к обсуждению идеи, как, по его мнению, правильно программировать вообще - основываясь на материале первой половины. и вот эта часть особенно офигенна, особенно учитывая, что с половиной его фраз хочется тут же согласиться и проповедовать массам, а с половиной спорить в штыки. то есть основной упор в рассказе идет на то, что программирование - это математика. и это он и показывает, доказывает, и рассуждает о текущем положении вещей в программировании и науках вообще.


Выдержки с рутрекераСвернуть )





Полный архив на Rutracker.Org
Давайте рассмотрим все алгоритмы, существующие на свете, и попытаемся узнать, можно ли автоматически, с помощью машины (т.е. опять же алгоритма) отвечать на какие-то вопросы, касающиеся тех или иных алгоритмов.

Рассмотрим два алгоритма и . Назовем их эквивалентными, если на одном и том же входе они оба либо не останавливаются, либо выдают один и тот же ответ.

Любой алгоритм имеет текст. Текст алгоритма — строка в некотором ограниченном алфавите. Так что мы можем выписать все строки, которые существуют в этом алфавите (например, в лексикографическом порядке), этих строк счетное число, и можно пронумеровать их последовательно натуральными числами. Некоторые из этих строк представляют собой корректные алгоритмы, остальные же — "не компилирующиеся" — будем считать алгоритмами, которые всегда зацикливаются. Итак, каждый алгоритм получил свой уникальный номер.

Рассмотрим некоторое числовое множество . Назовем его инвариантным, если выполняется следующее свойство: номера любых двух эквивалентных алгоритмов либо оба лежат в , либо оба не лежат в нем.
Например, множество "Алгоритмы, которые на входе 1 выдают 39" — инвариантно. Аналогично инвариантными являются множества "Алгоритмы, которые останавливаются хоть на каком-нибудь входе", "Алгоритмы, которые возвращают только четные числа", "Алгоритмы, которые никогда не зацикливаются" и так далее.

Фактически, понятие инвариантного множества можно представлять как некоторое свойство алгоритма. Причем мы берем только свойства, характеризирующие алгоритм как класс — зависящие от его входа, выхода и факта конечного времени работы. Например, множество "Алгоритмы, выполняющие ровно 42 шага" — не инвариантно.

Очевидно, если множество — инвариантно, то его дополнение также инвариантно.

Множество называется разрешимым, если для него можно построить разрешающий алгоритм , который для любого числа на входе всегда останавливается и выдает 1, если , и 0, если .
Простой пример разрешимого множества — простые числа. Сюда же относятся четные числа, любые конечные множества, все множество , и еще многие различные примеры. Существуют также неразрешимые множества, но в данном посте этот вопрос затрагивать не стоит.

Множество называется перечислимым, если для него можно построить полуразрешающий алгоритм , который принимает на вход число , и возвращает 1, если , в противном же случае () — зацикливается.
Понятно, что любое разрешимое множество является перечислимым: разрешающий алгоритм легко превратить в полуразрешающий, добавив ему в конец вечный цикл вместо возвращения значения 0. Гораздо интереснее вопрос "Существует ли перечислимое неразрешимое множество?" Правильный ответ — да, существует, и не одно, однако построение конкретных примеров тоже выходит за рамки данного поста.

Теорема Райса (в некоторых редакциях теорема Успенского-Райса) утверждает поразительный факт:
Любое нетривиальное свойство алгоритма является неразрешимым.
Иными словами:
Если некоторое инвариантное множество разрешимо, то имеет место либо , либо .

ДоказательствоСвернуть )
Таким образом, принципиально невозможно построить такую среду/оболочку/систему/IDE, которая по коду данного ей произвольного алгоритма будет автоматически определять, справедливо ли для него какое-то специфическое свойство, каким бы простым и очевидным это свойство ни было. В частности, неразрешима так называемая проблема останова — не существует алгоритма, который по коду другого алгоритма и входному числу определил бы, остановится ли на входе .

Примечательно, что огромное количество программистов, в глаза не видевших никогда теорию алгоритмов и theoretical computer science, свято уверены, что любую задачу на свете можно решить и запрограммировать, были бы время и ресурсы.

Если бы.

Метки: