WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS


Pages:     || 2 | 3 | 4 | 5 |

«В.Э. Вольфенгаген, Л.В. Гольцева, Л.Ю. Исмаилова АППЛИКАТИВНЫЕ ВЫЧИСЛЕНИЯ на основе комбинаторов и -исчисления Издание 3-е, стереотипное Проект: Аппликативные ...»

-- [ Страница 1 ] --

МОСКОВСКИЙ ИНЖЕНЕРНО-ФИЗИЧЕСКИЙ ИНСТИТУТ

(ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)

В.Э. Вольфенгаген,

Л.В. Гольцева,

Л.Ю. Исмаилова

АППЛИКАТИВНЫЕ

ВЫЧИСЛЕНИЯ

на основе комбинаторов и -исчисления

Издание 3-е, стереотипное

Проект: Аппликативные Вычислительные Системы

Руководитель проекта, кандидат технических наук Л.Ю.Исмаилова Москва 2007 I Факультет кибернетики Проект: Аппликативные Вычислительные Системы Руководитель проекта, кандидат технических наук Исмаилова Л.Ю.

Д.т.н., профессор Вольфенгаген В.Э., к.т.н., Гольцева Л.В., к.т.н., Исмаилова Л. Ю.

Аппликативные вычисления на основе комбинаторов и -исчисления.— 3-е изд.— М.: МИФИ, 2007.—72 с.

Основы аппликативных вычислительных систем изложены элементарными средствами, что обеспечивает студентов и аспирантов кратким и исчерпывающим руководством, которое может использоваться ‘для первого чтения’. Настоящее руководство в различных вариантах течение ряда лет использовалось для проведения практический занятий и лабораторных работ по соответствующим разделам курса компьютерных наук. Охватываются вопросы использования комбинаторов и -исчисления при реализации аппликативных вычислений. Приводится необходимый теоретический минимум, основное внимание уделено выполнению упражнений, иллюстрирующих применения основных вычислительных идей, понятий и определений. Для облегчения овладения предметом руководство снабжено простой обучающей программой, которая может использоваться в качестве вводного лабораторного практикума. При практической работе с обучающей программой следует иметь ввиду, что решение задач предполагает проведение дополнительных преобразований с целью оптимизации выражений, устранения в них переменных, упрощения целевого исполняемого выражения.

Аппликативные вычисления излагаются как набор таких методов и средств.

Для студентов и аспирантов всех специальностей. Может быть использована для первоначального самостоятельного изучения предмета.

c В.Э. Вольфенгаген, 1992– c Институт Актуального Образования “ЮрИнфоР-МГУ”, c Московский инженерно-физический институт, Московский инженерно-физический институт Лаборатория ИИТ и ВС, комната 119а Москва, 115409 РФ Fax: +7 (495) 323-94- E-mail: vew@jmsuice.msk.ru II Оглавление Предисловие к 1-му изданию........................... Предисловие ко 2-му изданию.......................... 1. Введение......................................... Часть I. Элементарная техника аппликативных вычислений 2. -исчисление..................................... 2.1 -обозначения................................... 2.2 Формальная система -исчисления................ 3. Структура терма и подстановка..................... 3.1 Структура терма................................. 3.2 Подстановка..................................... 4. Графическое представление термов................. 5. Свертывание...................................... 6. Комбинаторная логика............................. 6.1 Комбинаторы.................................... 6.2 Формальная система комбинаторов................ 7. Слабая редукция.................................. 8. Теорема о неподвижной точке...................... 9. Формальные теории и CL..................... IV Оглавление 10. Модели CL...................................... Часть II. Лабораторный практикум 12. Механизмы построения практикума................. 13. Восстановление скобок в -термах.................. 16. Разложение термов в базисах I, K, S и I, B, C, S.... 17. Расширение базисной системы комбинаторов........ 18. Техника анализа введенных результатов............. Предисловие к 1-му изданию Настоящее учебное пособие подготовлено для проведения семинарских занятий и лабораторных работ и охватывает вопросы использования комбинаторов и -исчисления при реализации аппликативных вычислений. Наряду с теоретическими сведениями основное внимание уделено выполнению упражнений, закрепляющих навык владения комбинаторной логикой. Материал ориентирован на развитие на развитие у студентов умения соединять теоретическое рассмотрение задачи с ее практической реализацией на компьютере. Решение задач предполагает проведение дополнительных преобразований с целью оптимизации выражений, устранения в них переменных, упрощения целевого исполняемого выражения. Аппликативные вычисления излагаются как набор таких методов и средств.

Москва, МИФИ 2 Предисловие Предисловие ко 2-му изданию Настоящее руководство написано как краткий и элементарный курс, который надо практически изучить, чтобы помочь в овладении специальной литературой в области компьютерных наук. В обычных университетских курсах по математике или информатике, как правило, остаются без должного внимания вопросы исчисления объектов. В мировой практике за последние два десятилетия сложился относительно новый язык изложения результатов научных исследований в области программирования или информационных технологий, который основан на систематическом и явном использовании метаоператоров аппликации и функциональной абстракции. Книга принесет наибольшую пользу студенту, аспиранту или специалисту, не имеющего должной подготовки в области теоретических компьютерных наук, но имеющему необходимость войти в круг идеи аппликативных вычислений.

Общая идея разработки практикума, который бы позволил начинающему без излишних трудозатрат освоить методы записи аппликативных форм возникла в 1986 г. при проведении в МИФИ практических занятий со студентами по соответствующим разделам дисциплин по компьютерным наукам. Постановка задачи принадлежит к.т.н. Л.Ю. Исмаиловой, под чьим общим руководством аспиранткой Л.В. Гольцевой было реализовано программное обеспечение.

Москва, Институт Актуального Образования “ЮрИнфоР-МГУ” 4 Предисловие 1. Введение -исчисление – это бестиповая теория, рассматривающая функции как правила, а не как графики. Понятие ‘функции как закона или правила’ подразумевает переход от аргумента к значению, процесс, закодированный некоторым определением. -исчисление рассматривает функции с точки зрения их вычисления.

Как теория комбинаторов, так и -исчисление имеют общую цель – описать некоторые базисные и общие свойства операторов и комбинаций операторов. Обе теории можно рассматривать как абстрактные языки программирования, так как они содержат в себе концепцию вычисления в ее наиболее полном и общем виде, но с минимумом синтаксических деталей и сложностей. -исчисление с успехом используется в качестве метатеории для различных формальных систем, основанных на определении функции. Такие системы строятся для описания основных способов комбинирования операторов и функций для формирования других операторов. На практике каждая -система обладает собственной синтаксической структурой, определяемой способами ее применения. В некоторых системах есть дополнительные константы, большинство из них имеет встроенные синтаксические ограничения, например, типовые ограничения. Будем рассматривать наиболее простую из синтаксических систем.

6 1. Введение Элементарная техника аппликативных 2. -исчисление, основные определения 2.1 -обозначения Для пояснения -обозначений рассмотрим математическое выражение ‘x y’. Его можно рассматривать как определение функции f от x или функции g от y:

Для их различения требуется такое определение, которое дает функциям f и g различные имена некоторым систематическим способом. Нотация Черча – это систематический способ построения для выражения, включающего переменную ‘x’, обозначения для соответствующей функции от x (аналогичным способом для y):

Например, рассмотрим равенства В -обозначениях они принимают вид:

-обозначения могут быть распространены на случай функций от более, чем одной переменной. Например, выражение ‘x y’ определяет две функции h и k от двух переменных как Эти определения можно переписать как 10 2. -исчисление Однако можно избежать использования специальных обозначений для функций с различными переменными, используя функции, значения которых являются не числами, а представляют собой другие функции. Например, вместо 2-местной функции h, определенной выше, рассмотрим 1-местную функцию h, определенную посредством Для каждого числа ‘a’ получаем:

Следовательно, для каждой пары чисел a и b:

2.2 Формальная система -исчисления Построим формальную систему -исчисления.

Положим, что дана бесконечная последовательность различных символов, называемых переменными, и конечная, бесконечная или пустая последовательность различных символов, называемых константами (когда последовательность констант пуста, система будет называться чистой, в противном случае – прикладной).

Определение 2.1 (-терм). Множество выражений, называемых -термами, определяется следующим способом:

i) все переменные и константы, являющиеся -термами, называются атомами;

ii) если M и N – произвольные -термы, то (M N ) – -терм, называемый аппликацией;

iii) если M – произвольный -терм, а x - произвольная переменная, то (x.M ) – -терм, называемый абстракцией.

Пример 2.1. Примеры -термов:

(x.(xy)), ((y.y)(x.(xy))), (x(x(x.x))), (x.(yz)) Прописными буквами будем обозначать произвольные -термы.

Строчными буквами ‘x’, ‘y’, ‘z’, ‘u’, ‘v’, ‘w’ будем обозначать переменные. Скобки опускаются таким образом, что, например, ‘M N P Q’ обозначает (((M N )P )Q). Это преобразование называется сокращением (восстановлением) скобок по ассоциации влево.

В дальнейшем будут использоваться также сокращения:

Графическое равенство будет обозначаться знаком ‘=’. Например, запись ‘M = N ’ будет обозначать, что M в точности такой же терм, что и N. В дальнейшем будет предполагаться, что если Также будет предполагаться, что 4-е класса термов – переменные, константы, аппликации, абстракции, – не имеют общих элементов. Это принимается всегда при определении множеств выражений. Такое определение терма позволяет сформировать больше термов, чем это необходимо для приложений системы. Следовательно, часть термов остается неинтерпретированной.

Если терм M был проинтерпретирован как функция или оператор, то (M N ) интерпретируется как результат приложения (апплицирования) M к аргументу N с обеспечением того, что этот результат определен. Терм (x.M ) представляет оператор, значение которого на аргументе N вычисляется подстановкой N вместо x всюду, где x имеет свободные вхождения в M.

Примеры Пример 2.2. x.x(xy) представляет операцию применения функции дважды к объекту, обозначаемому y, и равенство ( x.x(xy))N = N(Ny) выполняется для всех термов N в том смысле, что обе стороны имеют одинаковую интерпретацию.

Пример 2.3. x.y представляет константную функцию, которая принимает значение y для всех аргументов, и равенство несет тот же смысл, что и предыдущее.

12 2. -исчисление Упражнения Упражнение 2.1. Представить следующие выражения в формальном -обозначении, используя D для обозначения оператора дифференцирования:

Упражнение 2.2. Расставить недостающие скобки:



Pages:     || 2 | 3 | 4 | 5 |
 


Похожие работы:

«В.В. Соколов О Ч Е Р К И Э К О Л О Г О -К Л И М А Т И Ч Е С К О Й И С Т О Р И И Р О С С И И М он ограф и я РГГМУ Санкт-Петербург 2010 У Д К 502:93 Б Б К 20.1 Соколов В.В. Очерки эколого-климатической истории России. М онограф ияСПб.: РГГМУ, 2010. - 309 с. IS B N 978-5-86813-281-0 Приводятся сведения эколого-климатического характера, влияющие на формирование государственности России: природная среда, эколого-климатические ресурсы, природопользование, экологизация новой исторической реаль­ ности...»

«1. Цель освоения дисциплины Целью освоения дисциплины Экологическое право является формирование у студентов навыков работы с нормативно-правовыми актами, анализа правовых явлений и правовых отношений в сфере взаимодействия природы и общества. 2. Место дисциплины в структуре ООП ВПО В соответствии с учебным планом по направлению подготовки 022000.68 Экология и природопользование дисциплина Экологическое право относится к дисциплинам по выбору вариативной части общенаучного цикла. Дисциплина...»

«Программа трудового обучения 1-4 класс Пояснительная записка Трудовое обучение в начальных классах является органической составной частью единой системы обучения, воспитания и развития учащихся. Цель трудового обучения - воспитание творческой социально активной личности, проявляющей интерес к техническому творчеству и желание трудиться, формирование у детей культуры труда. Основными задачами трудового обучения учащихся начальных классов являются: воспитание трудолюбия, уважения к людям труда;...»

«Волжский филиал федерального государственного бюджетного образовательного учреждения высшего профессионального образования Московский автомобильно-дорожный государственный технический университет (МАДИ) ОТЧЕТ ПО САМООБСЛЕДОВАНИЮ (2008-2013 гг.) Чебоксары 2013 Содержание Введение I. Реализация основных профессиональных образовательных программ высшего профессионального образованияв Волжском филиале МАДИ 1.1 Документы, регламентирующие право осуществления образовательной деятельности Волжским...»

«УЧПЕДГИЗ -1959 Е. Е. Соловьева, Н. Н. Щепетова, Л. А. Карпинская, В. И. Волынская, А. А. Канарская. Родная речь, Книга для чтения в III классе начальной школы. Редактор 3. А. Богданова Художественный редактор Б. М. Кисин Технический редактор М. Д. Козловская Корректоры А. П. Тарасова и В. А. Глебова *** Подписано к печати с матриц 24/VII 1958 г. 60X921/16. Печ. л. 24 + 0,5 цветных вклеек. Уч.-изд. л. 18,86 + 0,22 цветных вклеек. Тираж 1200 тыс. (1—400000) экз. Заказ № 915. *** Учпедгиз. Москва,...»

«Nuclear Weapons After the Cold War. Электронная версия: http://www.carnegie.ru/ru/pubs/books. Книга подготовлена в рамках программы, осуществляемой некоммерческой неправительственной организацией — Московским Центром Карнеги при поддержке фонда Джона Д. и Кэтрин Макартуров, фонда Старр и Корпорации Карнеги Нью-Йорка. В книге отражены личные взгляды авторов, которые не должны рассматриваться как точка зрения Фонда Карнеги за Международный Мир или Московского Центра Карнеги. Научно-техническое...»

«/ А.Б. Повалко / / Л.М. Огородова / 23 декабря 2013 г. 24 декабря 2013 г. КОНКУРСНАЯ ДОКУМЕНТАЦИЯ по проведению конкурсного отбора на предоставление субсидий в рамках реализации федеральной целевой программы Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014 - 2020 годы Мероприятие 1.2, 2 очередь. Проведение исследований и создание научно-технического задела в области информационно-телекоммуникационных систем CОГЛАСОВАНО CОГЛАСОВАНО...»

«Москва, 3 июня 2011 г. Понятие технологической платформы Основные принципы государство Объединение усилий наиболее значимых и заинтересованных сторон (государства, бизнеса, науки) бизнес наука ОЦЕНКА ВЫЗОВОВ Обеспечение выработки и реализации долгосрочных приоритет РАЗРАБОТКА (стратегических) приоритетов в ПРОГРАММЫ масштабах определенных отрасль ИССЛЕДОВАНИЙ секторов экономики ОПРЕДЕЛЕНИЕ ПУТЕЙ РЕАЛИЗАЦИИ Технологическая модернизация в наиболее перспективных для предложение спрос развития...»

«УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС Дисциплина ОПД.Ф.09 БУХГАЛТЕРСКИЙ УЧЕТ Направление 080500.62 – Менеджмент Разработчик УМК доцент Давыдова Г.В. Екатеринбург 2010 2 Министерство образования и науки РФ Уральский государственный лесотехнический университет Кафедра бухгалтерского учета и аудита Одобрена: Утверждаю: кафедрой бухгалтерского учета и аудита Декан ФЭУ В.П.Часовских протокол № 1 от 1 сентября 2010 г. Зав.кафедрой _ В.П. Часовских методической комиссией ФЭУ 2010 г. Протокол № 1 от 20...»

«II. НАУЧНАЯ ДЕЯТЕЛЬНОСТЬ ИКИ РАН 2.1. Соблюдение порядка оформления и утверждения планов НИР и отчётов о результатах научных исследований В соответствии с п. 5.8. Устава Института космических исследований РАН учёный совет разрабатывает основные направления научных исследований Института; рекомендует к утверждению программы и планы научно-исследовательских работ, которые затем согласовываются с Бюро ОФН РАН и утверждаются вице-президентом РАН. Все темы выполняемых научно-исследовательских работ...»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.