Отправляет email-рассылки с помощью сервиса Sendsay

Информат - алгоритмическое и математическое мышление

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "физика YES" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Май 2003   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
ss77_ss77@mail.ru

Статистика

1.523 подписчиков
+1 за неделю
←   Все выпуски   →

Конкурсы и Олимпиады по Машинному программированию (КОМП)


Информационный Канал Subscribe.Ru 
   Весенняя олимпиада школьников 2003 года.

--- Новости ---
Приглашаются на заключительный (очный) тур все участники набравшие более 30 баллов
за все туры. Сводную таблицу смотрите на сайте http://olymp.udm.ru/school/index.html
---------------

---  Содержание ---
1. Результаты третьего тура
2. Комментарии к задаче "Генетика"
-------------------

 1. Результаты третьего тура

  Поскольку результаты третьего тура не влияют на прохождение на очный тур, жюри
решено зафиксировать текущие баллы.
  На призы могут расчитывать только участники очного тура.
  Ждём всех в Ижевске. Предварительно назначена дата 17 июня. Если есть возражения,
пишите - обсудим.


 2. Комментарии к задаче "Генетика"

Автор задачи профессор Н. Н. Непейвода предлагает разбор решения своей задачи
участниками.

Комментарии к задаче "Генетика"
В 1920 г. безумно гениальный петербургский молодой ученый Л.Шенфинкель создал
новую логическую систему. Он предложил рассматривать лишь функции, и применять
их к функциям. Соответственно, применение f к x для симметрии обозначалось (fx),
и можно было применять функцию в том числе и к самой себе. Он доказал, что для
построения всех возможных преобразований функций достаточно трех исходных операций
(комбинаторов):

(I x)= x.
(K x y )= x.
(S x y z) = ((x z) (y z )).


Он заметил и то, что функции от многих переменных могут быть сведены к функциям
высоких порядков от одной переменной. F(x,y,z) можно постепенно вычислить как
(((F x) y) z). Поэтому (((f x ) y) z) стали сокращать в (f x y z).

Полученную систему стали называть комбинаторной логикой.

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

В дальнейшем идеи комбинаторной логики развили американцы Черч и Карри. Черч
вместе с Россером доказал, что, если результат получается, то он получается один
и тот же независимо от пути преобразований.

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

Итак, система преобразований в задаче универсальная для алгоритмов. Поэтому проблема
установить, заканчивается ли вычисление и всегда ли оно заканчивается -- теоретически
неразрешима. Если же ограничиться нашим случаем (100 шагов 250 длина выражения)
она исключительно трудна и практически неразрешима. Но неразрешимые задачи можно
и нужно решать эвристическими методами. В данном случае к полному решению для
всех тестов приводил следующий эвристический метод.

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

Для нахождения наихудшего пути поменяйте приоритет преобразований на обратный.

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



                                Жюри.
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное