Реализация сетевой модели вычислений с аксиоматической и рекурсивной формами задания функций и предикатов (бакалаврская работа) (544461)
Текст из файла
НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙУНИВЕРСИТЕТ«МЭИ»Институт Автоматики и вычислительной техникиКафедра Прикладной математикиВЫПУСКНАЯ РАБОТАбакалавра Прикладной математики и информатикипо направлению «Прикладная математика и информатика» (010500)Тема:«Реализациясетевоймоделивычисленийсаксиоматической и рекурсивной формами задания функций ипредикатов»СтудентАфанасьев С.ЕА-13-08фамилия, и. огруппа,подписьНаучныйруководительПрофессорд.т.нФальк В.Н.должностьзваниеФамилия, и.о. подпись«Работа допущена к защите»Зав. кафедройЕремеев А.П.датаФамилия, и.о.Дата_____________Москва2012 г.подпись1ВведениеТеория направленных отношений, разработанная Фальком В.Н.
иКутеповымВ.П., являетсяуниверсальнойтеоретическоймоделью,позволяющей в естественной форме описывать и вычислять рекурсивнозаданные объекты некоторой предметной области. На базе теориинаправленныхотношенийфункционально-логическогобыла разработана одна из реализацийязыка программирования FLOGOL (Functionand LOGic Oriented Language), обладающая возможностью в компактнойсхемнойформезадаватьопределения конструктивных объектоввтерминах направленных отношений.Цель работы:Создание системы функционально-логического программирования(СФЛП), основанной на формализме направленных отношений (НО) иобладающей развитыми интерфейсными средствами построения и отладкипрограмм.Основные задачи:— исследование языка FLOGOL и формальное описание егосемантики;— разработка основных принципов и метода компиляции FLOGOLзапросов;— разработка специальной технологии ввода программ исоответствующих интерфейсных средств;21.
Теоретическая часть1.1. Основные понятияВосновенаправленноготеориинаправленныхотношения (НО).отношенийРазличаютдвалежитвидапонятиенаправленныхотношений – бестиповые и типизированные.,Направленным отношением типаназывается график соответствия из , на носителе. Пара | |, |вD| называетсяарностью этого НО.Подкласс НО на носителе D,обозначается.Типилитипа(арности < | |, |,арностьНО| >)при необходимостиуказываются в виде правого верхнего индекса.Здесь D – множество всевозможных кортежей элементов множества Dдлины ϑ. Иными словами, направленное отношение R арности < n , n’’ >на носителе D (точнее, его график) есть множество упорядоченных пар′ ′′вида < d1′...dn′' , d1′′...dn′′'' > , где все di , di ∈ D .
Кортеж d1′...dn′' назовем входным, акортеж d1′′...dn′′'' – выходным для соответствующего элемента d -отношения R .Кортеж нулевой длины (пустой кортеж) обозначается λ , а в случаях егоиспользования в выражениях там, где это не приводит к недоразумениям, онпредставляется непосредственно пустым словом.В случае если в качестве Dвыбирается односортный носитель(универсум), то тип любого НО на D вполне определяется его арностью. Вязыке программирования FLOGOL в качестве носителя выбран односортныйноситель, поэтому язык можно считать нетипизированным.
Однаковследствиетого,чтомногосортныйносительможетбытьлегкопромоделирован с использованием односортного носителя, введение в языкпользовательских типов данных затруднений не вызывает.3НОназывается обратным для НО∀ ∀,∈ ≈, если,∈НО могут обладать некоторыми фундаментальными свойствами, вопределенном смысле не зависящими от выбора носителя.
К такимсвойствам относятся функциональность и тотальность.НО арности∀,на∈→∃называется тотальным, если∈&#,∈ $НО R называется функциональным, если∀ ∀ ′∀ ′′,∈ &,∈→= ′′Этими свойствами могут обладать как само НО, так и братное ему НО.Свойства функциональности и тотальности, определенные для обратногоотношения, будем называть свойствами обратной функциональности итотальности.Свойства функциональности и тотальности играют значительную рольв процедурах редукции, использующихся в базовой модели вычислениянаправленныхотношенийиввычислительнойподсистемеданнойреализации языка.1.2. Языки и схемы направленных отношенийВ основу построения данной реализации языка FLOGOL положеноопределенное понятиеязыкасхемНО.Длязаданияязыкасхемнеобходимо определение области интерпретации, символов элементарныхконстант и переменных, связок и операторов.
Связки используются дляобозначения результатовпримененияоперацийкомпозицииНОнаобласти интерпретации.Область интерпретации задается уточнением носителя. Бинарнымиоперациями,являютсярассматриваемымипоследовательнаявтеориикомпозиция,направленыхпараллельнаяотношений,композиция,4конкатенация, условная композиция, эквализация (унификация), операцииобъединения и пересечения типизированных НО.НОПоследовательная композиция∙обозначается через'':∙Если∙и' –и'≅{'НО арности,|∃,,, ∈& ,,,– НО арностейи∈,'}соответственно, то, ′′ .
Операция последовательной композицииассоциативна.иПараллельная композиция НОопределяетсяграфиковЕслито#'какираздельное'обозначаетсядекартовопроизведение|&#'икомпонентов':#'и'≅{','– НО арности+ ′' , – НО арности,∈,и', '', ∈'}соответственно,'+ ′′' . Операция параллельнойкомпозиции ассоциативна.Объединение НОи'обозначается черезкак теоретико-множественное объединения НО∪и''и определяется, гдеи'соответствующие графики. Объединение накладывает требование равенстваарности НО, причем результат объединения имеет ту же арность. Операцияобъединения ассоциативна и коммутативна.Пересечение НО R и R ' обозначается через R ∩ R ' и определяетсякак теоретико-множественное пересечениеНО Rи R ' как графиков.Пересечение накладывает требование равенства арности НО, причемрезультат пересечения имеет ту же самую арность.
Операция пересеченияассоциативна и коммутативна.5Операция эквализации (унификации). Эквализация d -отношений R1 иR2 определяется как декартово произведение первых компонентов графиковпри равных вторых компонентах:R1∇R2 ≅ {< α1α 2 , β >|< α1 , β >∈ R1 & < α2 , β >∈ R2 }.< n1 , n > иЭквализация определена только для операндов арностей< n2 , n > . Результат операции будет иметь арность < n1 + n2 , n > .Условная композиция d -отношений R1 и R2 обозначается знаком →и представляет собой проекцию R2 по первому компоненту графика наобласть определения d -отношения R1 :R1 → R2 ≅ {< α , β >|< α , β >∈ R2 & ∃β ' (< α , β ' >∈ R1 )}.Арности операндов условной композиции должны быть< n,n1 >и< n,n2 > , соответственно.
Результат композиции, очевидно, имеет арностьвторого операнда.< n ,n >Операция итерации. Итерация d -отношения Rобозначается {R}и определяется так:{ R} ≅U R (k )k ≥0( 0)n, где R ≅ {< α ,α >| α ∈ D } (тождественное d -отношение(1 )( i +1)≅ R (i ) • Rарности < n, n > ), R ≅ R и RОчевидно, что итерация {R} d -отношения R является наименьшимрешением уравнения x = R( 0)∪ R • x , т.е.{ R} = { x = R (0) ∪ R • x} .Результатприменения< n, n >, n ≥ 0 , что и ее операнд.итерациибудетиметьтужеарность6< n ,n >Операция повторения. Повторение d -отношения Rобозначается[R ] и определяется так:[R] ≅ U R (k ) = R • { R}k ≥1.Результат применения операции повторения будет иметь ту же арность< n, n >, n ≥ 0 , что и ее операнд.Реализация языка функционально-логическогоFLOGOL опираетсянаформализмпрограммированиянаправленногоотношения,чтопозволяет в естественной форме выражать основные семантическиеобъекты, используемые при формулировке задач искусственного интеллекта.К таким объектам относятся предикаты, функции, конструкторы,кортежи и др.
Программа на языке FLOGOL представляется в виде базыданных определений НО, одно из которых выделено в качестве запроса кбазе[1].Вычислениезапросапроизводитсянаосновесетевогопредставления направленных отношений.1.3. Комбинаторные d -отношения.d -отношениеназывается комбинаторным, если оно являетсяRфиксированной точкойдля любой перестановкиξна носителеD:ξ (R) = R для любого всюду определенного на D взаимно-однозначногоотображенияξ .
Класс комбинаторныхd -отношений на носителеDобозначим R к , полагая, что сам носитель ясен из контекста (фактически насинтересует только его мощность).Пустое множество задает пустое комбинаторное d -отношение.Среди простых комбинаторныхследующие d -отношения:d -отношенийособо выделим71) тождественные < n, n > -арные, n ≥ 0 , d -отношенияα ∈ D n } . Очевидно, чтоn• R <n ',n"> = R = R •последовательной композиции d -отношений:0≅2)≅ {<, >} .< n′, n′′ > -арные3) пустыеn′n";– правая и левая единица операции# R = R = R#параллельной композиции:≅ {< α ,α >|– правая и левая единица операцииn'0n;d -отношения,n′, n′′ ≥ 0, обозначаются∅n′′ .
n′ ∅n′′ – правые и левые единицы для операции объединения d -отношений:n'∅n" ∪ R<n′,n′′> = R = R∪n′ ∅n′′ ;< n′, n′′ > -арные4) универсальныеn′обозначаютсяn′′n′n′′.d-отношения, n′, n′′ ≥ 0,– правые и левые единицы для операциипересечения d -отношений:n′n′′∩ R < n′,n′′> = R = R ∩ n′n′′Выделим в множестве простых комбинаторныхследующее подмножество элементарных d -отношений:R кпэ ≅ {,,,где <>≅{<, >},≅ {< α , >| α ∈ D}≅ {<,α >| α ∈ D} ,≅ {< αα ,α >| α ∈ D} ,,,,},d -отношений8≅ {< α ,αα >| α ∈ D} ,≅ {< α , β >| α ∈ D & β ∈ D & α ≠ β } ,≅ {< α 'α ",α "α ' >| α '∈ D & α "∈ D} .Пусть n ≥ 0 . Определим сначала тождественное < n, n > -арное d 0nотношениеn +1≅: a), b)n≅#≅, где•.nd -Отношения≅ {< α , >| α ∈ D n }nи≅ {<, α >| α ∈ D n }определимтак:00=n +1=≅,n′′#< n′, n′′ >Универсальноеn′n +1nn′n′′≅ {< α ′,α ′′ >| α '∈ D & α ′′ ∈ D }n≅,#-арноеопределяется так:.-отношениеdn′n′′n′≅•n′′.Остальные константы:n≅ {< α ,αα >| α ∈ D n } ,n≅ {< αα ,α >| α ∈ D n } ,n≅ {< α , β >| α ∈ D n & β ∈ D n & α ≠ β } ,n'n"≅ {< α ′α ′′,α ′′α ′ >| α ′ ∈ D n′ & α ′′ ∈ D n′′ }могут быть определены следующим образом:0n1)1n′′+102)=n≅ (1≅0n′′≅nn′′,)•(#n +1,n′+1≅(≅ (n′#1n′′) • ( n′n′′#),n′′#n#);)•(n#n1#),903)04)≅n +1,≅ ∅ ,n +1n≅(≅n#n#1n∪)•(#n#),n#.1.4.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
