?

Log in

No account? Create an account

Категория: it


Цели курса


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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Если бы.

Метки:

Here Comes Tiburon. Part II

Пришла мне наконец написать давно планируемый пост про один из самых знаменательных релизов Borland, CodeGear и Embarcadero. Про релиз, который, право слово, станет знаменательным. Про релиз, который приносит в нашу жизнь вагон возможностей, который ставит Делфи в один ряд с возможностями многих признанных языков и технологий... короче, харе пафоса =) Всё очень просто. Сегодня я хочу написать в блоге про Delphi & C++Builder 2009 aka Tiburon.

Согласно статье на eWeek, с 25 августа начинается приём заказов. Немногим позже продукт официально выходит в продажу.

Приношу свои извинения за то, что "пост" по факту представляет собою три поста: даже у ЖЖ, как выяснилось, есть ограничения на объём записи (да что вы говорите... :-D ). Каждый пост будет оформлен в виде списка возможностей с пунктами и подпунктами. А по каждому подпункту - краткое описание плюс кучка ссылок. Ссылок много, очень много, пост будет полон ими чуть более, чем наполовину. Практически все из них - на инглише, но это дело десятое, я полагаю. Интересующемуся человеку прочесть не составит труда, угу? Итак, я начинаю.

Оглавление:
Part I: Юникод и параметризированные типы aka дженерики.
 —> Part II: Анонимные методы, IDE и VCL, разнообразное прочее.
Part III: Нововведения в С++Builder`e.


III. Anonymous methodsСвернуть )

IV. IDE и VCLСвернуть )

V. MiscellaneousСвернуть )


Оглавление:
Part I: Юникод и параметризированные типы aka дженерики.
 —> Part II: Анонимные методы, IDE и VCL, разнообразное прочее.
Part III: Нововведения в С++Builder`e.

Метки: