По словам автора
Герой рассказа Ийон Тихий ищет в «Космической энциклопедии» информацию о «сепульках», попадая в цикл косвенной рекурсии:
Нашёл следующие краткие сведения:
«СЕПУЛЬКИ — важный элемент цивилизации ардритов (см.) с планеты Энтеропия (см.). См. С ЕПУЛЬКАРИИ».
Я последовал этому совету и прочёл:
«СЕПУЛЬКАРИИ — устройства для сепуления (см.)».
Я поискал «Сепуление»; там значилось:
«СЕПУЛЕНИЕ — занятие ардритов (см.) с планеты Энтеропия (см.). См. С ЕПУЛЬКИ».
— С. Лем. « Звёздные дневники Ийона Тихого. Путешествие четырнадцатое»
В романе «Осмотр на месте» обе энцианские державы в своих нотах ставят Тихому в вину, что он в «Дневниках» превратно истолковал сущность сепулек. Тихий звонит профессору Тарантоге и слышит:
— И вы не могли мне сказать об этом немного раньше? — возмутился я; похоже было на то, что весь свет против меня сговорился.
Отправляясь с визитом на Энцию, Тихий надеялся выяснить этот вопрос.
В советском мультфильме «Из дневников Ийона Тихого» по мотивам рассказов Лема режиссёр Геннадий Тищенко изобразил сепульки как зародыши, по которым обитатели Энтеропии восстанавливали из резервных копий погибших под хмепом (метеоритным дождём) сородичей.
Сепулькарий упоминается во второй серии мультфильма «На задней парте».
Сепулька и сепулькарий упомянуты в песне «Слава роботам!» из альбома «Носитель идей» группы «Технология».
На сайте Lurkmore существует пасхальное яйцо в виде статей «Сепульки», «Сепулькарии», и «Сепуление», содержимое которых соответствует определениям «Космической энциклопедии», и которые соответствующим образом ссылаются друг на друга гиперссылками.
Об этимологии слова «сепулька» нет данных, фонетически оно созвучно с лат. — могила, гробница.
Лучшее за неделю
Страницы:
1 2 3 5 6 7 8 9 10 11 12 13
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
В Википедии есть статьи о других людях с фамилией Лем.
Стани́слав Ге́рман Лем (польск. Stanisław Herman Lem; 12 сентября 1921, Львов, Львовское воеводство, Польша — 27 марта 2006, Краков, Польша) — польский философ, футуролог и писатель (фантаст, эссеист, сатирик, критик). Его книги переведены на более чем 50 языков, продано более 40 млн экземпляров. Автор философского труда «Сумма технологии», в котором предвосхитил создание виртуальной реальности, искусственного интеллекта, развил идеи автоэволюции человека, сотворения искусственных миров и другие.
В годы оккупации
Евреи у синагоги во Львове, 1941 год
Евреи во Львовском гетто
Первые шаги в литературе
«Босх вызывает у меня чувство изумления, но прежде всего беспомощного недоумения. Откуда он все это взял? Он не имел права все это знать и тем более прийти к такому видению». Иероним Босх, «Сад земных наслаждений»
Лем в 2005 году
Космос, человек, знание
Двутелы. Иллюстрация к роману С. Лема «Эдем». Алексей Андреев
«Этот вспыльчивый человек и мизантроп всегда мне казался симпатичным». Артур Шопенгауэр, портрет работы
От утопии к антиутопии
Картина А. Андреева «Непобедимый»
Теория литературы Лема
Электрический поэт Электрувор (Elektrybałt) в Центре Науки «Коперник», Варшава
Теория фантастики и детектива
Коллекция первых изданий книг Станислава Лема на польском языке
Лем в СССР и России
Издания романа «Солярис»
Переводы на европейские и азиатские языки
на русском языке
на английском языке
на болгарском языке
на немецком языке
на чешском языке
Рекурсивное изображение экрана
Визуальная форма рекурсии страницы Википедии
Визуальная форма рекурсии (эффект Дросте)
Реку́рсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике.
В математике рекурсия имеет отношение к методу определения функций и числовых рядов: рекурсивно заданная функция определяет своё значение через обращение к себе самой с другими аргументами. При этом возможно два варианта:
, где бесконечную рекурсию, н
Прямой расчёт по приведённой формуле вызов
конечно). Для приближённого вычисления значения e достаточно искусственно ограничить глубину рекурсии некоторым наперёд заданным числом и по достижении его использовать вместо единицу.
Другим примером рекурсии в математике является числовая последовательность, заданная рекуррентной формулой, когда каждый следующий член последовательности вычисляется как результат функции от n предыдущих членов. Таким образом с помощью конечного выражения (представляющего собой совокупность рекуррентной формулы и набора значений для первых n членов ряда) может даваться определение бесконечной последовательности.
С рекурсией тесно связана математическая индукция: она является естественным способом доказательства свойств функций на натуральных числах, рекурсивно заданных через свои меньшие значения.
В математике отдельно рассматривается класс так называемых «примитивно рекурсивных» функций. Определение примитивно рекурсивной функции также рекурсивно, оно задаёт набор примитивных функций и набор правил; функция является примитивно рекурсивной, если она может быть представлена как комбинация примитивно рекурсивных функций, образованная по этим правилам.
Примеры рекурсии в математике:
Блок схема рекурсивного алгоритма решения Ханойской башни.
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция вызывает функцию , а функция — функцию . Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Рекурсивная программа позволяет описать повторяющееся или даже потенциально бесконечное вычисление, причём без явных повторений частей программы и использования циклов.
Структурно рекурсивная функция на верхнем уровне всегда представляет собой команду ветвления (выбор одной из двух или более альтернатив в зависимости от условия (условий), которое в данном случае уместно назвать «условием прекращения рекурсии»), имеющую две или более альтернативные ветви, из которых хотя бы одна является рекурсивной и хотя бы одна — терминальной. Рекурсивная ветвь выполняется, когда условие прекращения рекурсии ложно, и содержит хотя бы один рекурсивный вызов — прямой или опосредованный вызов функцией самой себя. Терминальная ветвь выполняется, когда условие прекращения рекурсии истинно; она возвращает некоторое значение, не выполняя рекурсивного вызова. Правильно написанная рекурсивная функция должна гарантировать, что через конечное число рекурсивных вызовов будет достигнуто выполнение условия прекращения рекурсии, в результате чего цепочка последовательных рекурсивных вызовов прервётся и выполнится возврат.
Помимо функций, выполняющих один рекурсивный вызов в каждой рекурсивной ветви, бывают случаи «параллельной рекурсии», когда на одной рекурсивной ветви делается два или более рекурсивных вызова. Параллельная рекурсия типична при обработке сложных структур данных, таких как деревья. Простейший пример параллельно-рекурсивной функции — вычисление ряда Фибоначчи, где для получения значения n-го члена необходимо вычислить (n-1)-й и (n-2)-й.
Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов.
Вопрос о желательности использования рекурсивных функций в программировании неоднозначен: с одной стороны, рекурсивная форма может быть структурно проще и нагляднее, в особенности, когда сам реализуемый алгоритм по сути рекурсивен. Кроме того, в некоторых декларативных или чисто функциональных языках (таких как Пролог или Haskell) просто нет синтаксических средств для организации циклов, и рекурсия в них — единственный доступный механизм организации повторяющихся вычислений. С другой стороны, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии. Так, широко распространённый в учебной литературе пример рекурсивного вычисления факториала является, скорее, примером того, как не надо применять рекурсию, так как приводит к достаточно большой глубине рекурсии и имеет очевидную реализацию в виде обычного циклического алгоритма.
Имеется специальный тип рекурсии, называемый «хвостовой рекурсией» (структура рекурсивного алгоритма такова, что рекурсивный вызов является последней выполняемой операцией в функции, а его результат непосредственно возвращается в качестве результата функции). Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивается выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. Однако далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.
Теоретически, любую рекурсивную функцию можно заменить циклом и стеком. Однако такая модификация, как правило, бессмысленна, так как приводит лишь к замене автоматического сохранения контекста в стеке вызовов на ручное выполнение тех же операций с тем же или большим расходом памяти. Исключением может быть ситуация, когда рекурсивный алгоритм приходится моделировать на языке, в котором рекурсия запрещена.
Доказательство корректности программ
В отличие от явно-циклических программ, для доказательства корректности рекурсивных нет необходимости искусственно вводить инвариант. Аналитическое доказательство корректности рекурсивной функции сводится к методу математической индукции, то есть к доказательству следующих утверждений:
Из суммы первого и второго утверждений следует, что в случае достижения терминальной ветви (а это значит — во всех случаях, когда вычисление функции окажется конечным) функция вернёт правильный результат. Третье положение доказывает, что конечным будет любое вычисление. Следовательно, любой вызов функции с корректными параметрами вернёт правильный результат (с очевидной «технической» оговоркой — если глубина рекурсии не окажется настолько большой, что вызовет переполнение памяти).
Рекурсивное определение данных возникает тогда, когда структура данных (запись, объект) содержит вложенный объект, структурно аналогичный самому себе или (что бывает чаще) ссылку на такой же объект. Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение способно описать потенциально бесконечную структуру данных. Подобные структуры используются при описании списков и графов. Пример описания списка (C):
/* указатель на следующий элемент того же типа */
/* некие данные */
Поскольку бесконечное число вложенных объектов невозможно разместить в конечной памяти, в реальности такие рекурсивно-определённые структуры всегда конечны. В заключительных (терминальных) ячейках обычно записываются пустые указатели, являющиеся одновременно флагами, указывающими программе, обрабатывающей структуру, что достигнут её конец.
Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных. В последние годы стала популярной концепция так называемых «ленивых вычислений», согласно которой данные, обрабатываемые программой, вычисляются лишь тогда, когда в них возникает необходимость. Реализация этой концепции привела к появлению в некоторых языках (Haskell, Python) возможности описывать потенциально-бесконечные, в том числе рекурсивные последовательности без явного ограничения на порождение объектов и свободно работать с ними.
Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала: в них образуются два коридора из уменьшающихся отражений зеркал.
Другим примером бесконечной рекурсии является эффект самовозбуждения (положительной обратной связи) у электронных схем усиления, когда сигнал с выхода попадает на вход, усиливается, снова попадает на вход схемы и снова усиливается. Усилители, для которых такой режим работы является штатным, называются автогенераторы.
Нашёл следующие краткие сведения:
«СЕПУЛЬКИ — важный элемент цивилизации ардритов (см.) с планеты Энтеропия (см.). См. С ЕПУЛЬКАРИИ».
Я последовал этому совету и прочёл:
«СЕПУЛЬКАРИИ — устройства для сепуления (см.)».
Я поискал «Сепуление»; там значилось:
«СЕПУЛЕНИЕ — занятие ардритов (см.) с планеты Энтеропия (см.). См. С ЕПУЛЬКИ».
Лем С. « Звёздные дневники Ийона Тихого. Путешествие четырнадцатое.»
Рекурсивный герб Российской Федерации
Битюцкий В. П., Папуловская Н. В. Математическая логика. Исчисление высказываний и предикатов
ние алгоритма всегда завершается, какая бы стратегия ни была принята при выборе и . Если N – число атомов, первоначально присутствующих в S (c учётом повторений), то процедура вычисления резольвенты будет выполняться N раз.
Существует два случая завершения алгоритма: либо порождён пустой дизъюнкт, тогда множество будет не выполнимым, либо получено множество S, не содержащее дизъюнктов для вычисления очередной резольвенты, тогда множество S будет выполнимым.
Показано, что любую предметную область можно представить в виде фраз Хорна. Для этого любую формулу в описании предметной области необходимо преобразовать в КНФ (конъюнктивную нормальную форму – конъюнкцию элементарных дизъюнкций) и далее каждую элементарную дизъюнкцию представить в виде фразы Хорна.
Пусть предметная область описана в виде
A v (B & D) ( A v B) & ( A v D). Этому высказыванию соответствует две фразы Хорна ( A v B) и ( A v D).
A v D – является фразой Хорна.
1.7. Примеры использования метода резолюций в логике высказываний
Метод резолюций применяется в качестве механизма доказательства при реализации принципа дедукции.
В любом рассуждении в логике высказываний можно проверить, будет ли истинность следствия этого рассуждения определяться истинностью фигурирующих в нём высказываний. Если это имеет место в данном рассуждении, то говорят, что оно логически правильное.
Например, выясним, является ли логически правильным следующее простое рассуждение. Студент пойдёт домой () или останется в университете (). Он не останется в университете. Следовательно, студент пойдёт домой. ( Буквами обозначены имеющиеся в этом рассуждении простые высказывания).
Можно считать, что данное рассуждение логически правильное.
Выяснить, являются ли логически правильными следующие рассуждения. Доказательство провести методом прямого вывода, методом «от противного».
Выразить описание задачи через фразы Хорна и провести доказательства, используя метод резолюций.
Или Пётр и Иван братья, или они однокурсники. Если Пётр и Иван братья, то Сергей и Иван не братья. Если Пётр и Иван однокурсники, то Иван и Михаил также однокурсники. Следовательно или Сергей и Иван не братья, или Иван и Михаил однокурсники.
Если Петр не встречал Ивана, то либо Иван не был на лекциях, либо Пётр лжёт. Если Иван был на лекциях, то Пётр встречал Ивана, и Сергей был в читальном зале после лекций. Если Сергей был в читальном зале после лекций, то либо Иван не был на лекциях, либо Пётр лжёт. Следовательно, Иван не был на лекциях.
Наша футбольная команда либо выигрывает матч, либо проигрывает, либо сводит его к ничьей. Если матч выигран или проигран, то он не перенесён. Команда матч не выиграла и не свела его к ничьей. Следовательно, матч не перенесён и проигран
Если Джон не встречал этой ночью Смита, то либо Джон был убийцей, либо Джон лжет. Если Смит не был убийцей, то Джон не встречал Смита этой ночью, и убийство имело место после полуночи. Если же убийство имело место после полуночи, то либо Смит был убийцей, либо Джон лжет. Следовательно, Смит был убийцей.
Известно, что хроничные сепульки всегда латентны или бифуркальны.
Какие из следующих утверждений в этом случае истинны:
сепульки не хроничны только в случае отсутствия у них свойства латентности;
латентность сепулек не является необходимым условием их хроничности или бифуркальности;
хроничность сепулек является достаточным условием их латентности или бифуркальности;
для нехроничности сепулек необходимо отсутствие у них как бифуркальности, так и латентности.
1.8. Непротиворечивость аксиом
Приведенное в примере 1 множество аксиом непротиворечиво, так как на наборе значений, где A=T, B=F, C=T и D=T, каждая аксиома принимает значение «истина».
называется высказывание, которое ложно во всякой предметной области. Противоречие будем обозначать как A& A (это высказывание является и простейшим примером противоречия) или как 0. Для более сложных высказываний проверку на то, является ли высказывание противоречием, проверяется так же, как высказывания на общезначимость, через построение таблицы. Значение функции в этом случае должно быть равным F.
Если множество аксиом противоречиво, то высказывание
Каждый раз, когда в экспертной системе строится описание предметной области, его проверяют на непротиворечивость. Непротиворечивость достигается через уточнение высказываний.
Кроме проверки множества аксиом на непротиворечивость, возникает задача проверки это множество на .
Пусть, например, в качестве аксиом выступают свидетельство людей, причастных к преступлению, и необходимо выявить, кто является преступником. Возникает вопрос, насколько можно доверять этим свидетельствам? Здесь
можно использовать такой приём. Будем считать, что свидетельства людей, не совершивших преступление, истинны, а свидетельства преступников – ложны. Тогда каждое свидетельство породит две аксиомы, имеющие вид импликаций: ЕСЛИ A невиновен ТО его свидетельство верно, и ЕСЛИ A преступник ТО его свидетельство – ложно.
1.9. Аксиоматизация логики высказываний
Любая математическая система основывается на множестве аксиом, т.е. выражений, считающихся общезначимыми и множестве правил вывода, т.е. механизмов, позволяющих строить новые общезначимые выражения. Такие выражения называют . Доказательством теорем называется последовательность из аксиом, правил вывода и уже доказанных теорем, позволяющих получить новую теорему. Важно, что логические правила, которые используются для вывода новых теорем из аксиом и ранее доказанных в данной системе теорем, не порождали в качестве «теорем» ложные высказывания.
Рассмотрим предметную область, включающую все возможные высказывания. Определим множество аксиом, определяющих эту область. Такими вопросами занимается область матлогики, называемая .
Необходимо предложить такие формализмы, которые бы определяли все процедуры и не требовали дополнительно никаких ссылок на смысловое содержание. В вышеприведённых примерах мы решали задачу вывода исходя из того, что известны понятия И, ИЛИ, ЕСЛИ ТО и др., которые использовались при выводе. Так, если аксиома определена как A&B, то, исходя из смысла этой операции, выводилась истинность высказываний A и B. В исчислении высказы-
– правильные схемы рассуждений, в которых заключение верно в силу именно рассуждения, а не .
Правильным умозаключением называется такое умозаключение, значение которого истинно всякий раз, когда истинны его гипотезы. Правила вывода являются правильными умозаключениями или силлогизмами. Силлогизм записывается в виде:
Если A студент то А посещает занятия , A посещает занятия, значит A – студент
Продолжение таблицы 1
Простая конструктивная дилемма
Сложная конструктивная дилемма
Простая деструктивная дилемма
Сложная деструктивная дилемма
Сведение к абсурду
Рассмотрим пример использования правила вывода Modus Ponens . Пусть P и Q заданы следующим образом: P– «A является студентом УГТУУПИ», Q– «A посещает занятия»,
Рассуждения, построенные по схеме силлогизмов, правильны именно в силу своей структуры. Рассмотрим пример формального доказательства правильности умозаключения
R – гипотеза;
Q – 2, 3, правило
P – 4, 5 и правило
Определите, какое из перечисленных умозаключений является правиль-
а) P v Q, P v S, S
b) P v Q, R v Q,P
P v Q, R v Q,P, S
2. Исчисление предикатов
Логика высказываний позволяет формализовать лишь малую часть множества рассуждений. Высказывания, описывающие некоторые свойства объектов, или отношения между объектами выходят за рамки логики высказываний. Например, мы не сможем судить о логической правильности такого простого рассуждения: «Каждое натуральное число является корнем некоторого квадратного уравнения. Число 5 –натуральное. Следовательно, 5 является корнем некоторого квадратного уравнения».
Логика предикатов начинается с анализа строения высказываний, которые выражают тот факт, что объекты обладают некоторыми свойствами, или находятся между собой в некоторых отношениях. Понятие «свойства» и понятие «отношения» рассматриваются как частный случай общего понятия «предиката». Объекты, о которых говорится в высказывании, называются термами или .
Пример функции F: X1X2 Y, где X1 – вес товара, X2– его цена, а Y–
стоимость, которая определяется как Y=X1 X2.
называется функция, аргументы которой принимают значения из некоторого множества, а сама функция – значение 0 («ложь») или 1 («истина»).
Пример предиката: ФАМИЛИЯ = «Петров». Здесь ФАМИЛИЯ – переменная, «Петров» – константа.
Предикаты, в которых описывается некоторое свойство объекта, называется предикат-свойство. Если предикат определяет отношение между несколькими объектами, то такой предикат называется предикат-отношение. В зависимости от того, между скольким числом объектов устанавливаются отношения, различают двуместные, трёхместные и n-местные отношения
Трёхместные: P(x,y,z) = «число x является НОД (наибольший общий делитель) чисел y и z» , R(x,y,z) = (z = x + y).
Предикатную функцию P(x, y) можно рассматривать как функцию, определённую на декартовом квадрате N. Множество тех пар (x, y) для которых данная функция принимает значение истины, есть область истинности предиката P(x, y). Табличную запись функции называют предиката.
