Главная » Просмотр файлов » Сборник задач для самостоятельных занятий

Сборник задач для самостоятельных занятий (1157984), страница 7

Файл №1157984 Сборник задач для самостоятельных занятий (Сборник задач для самостоятельных занятий) 7 страницаСборник задач для самостоятельных занятий (1157984) страница 72019-09-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Алгоритмическая полнота и алгоритмическая неразрешимость.313. Программа порождает всевозможные суффиксы заданного слова L, представленногосписком букв. Обращение к программе должно имет вид ? all_suffixes(L,X).4. Программа порождает список всех букв заданного конечного алфавита A = {a1 , a2 , .

. . , an },содержащихся в списке L однократно. Обращение к программе должно имет вид ?single(L,X).5. Программа порождает список всех букв заданного конечного алфавита A = {a1 , a2 , . . . , an },содержащихся в списке L многократно. Обращение к программе должно имет вид ?multiple(L,X).6. Программа порождает список всех букв заданного конечного алфавита A = {a1 , a2 , . . . , an },содержащихся в списке L1 и не содержащихся в списке L2 . Обращение к программедолжно имет вид ? filter(L1,L2,X).7. Программа порождает всевозможные сочетания элементов заданного бесповторного списка L1 .

Обращение к программе должно имет вид ? combination(L1,X).8. Программа порождает всевозможные сочетания элементов заданного бесповторного списка L1 , длина которых равна длине заданного списка L2 . Обращение к программе должноимет вид ? combination2(L1,L2,X).9. Программа порождает всевозможные сочетания c повторением элементов заданного бесповторного списка L1 , длина которых равна длине заданного списка L2 . Обращение кпрограмме должно имет вид ? combination_repit(L1,L2,X).1.13Алгоритмическая полнота и алгоритмическая неразрешимость.Упражнение 1.125. Возьмите ленточную конфигурацию α0 , представленную на рис. ??, ипостройте дерево SLD-резолютивных вычислений для запроса ? P (lef t(α0 ), right(α0 ), X, Y ),обращенного к логической программе Pπ , представленной на рис.

??.Упражнение 1.126. Какое устройство имеют деревья SLD-резолютивных вычислений запросов ? P (lef t(α), right(α), X, Y ), обращенных к логическим программам Pπ , соответствующим детерминированным программам машин Тьюринга.Упражнение 1.127. Пусть π — произвольная программа машины Тьюринга, α — ленточная конфигурация, являющаяся заключительной для программы π. Каково множествовычисленных ответов на запрос ? P (X, Y, lef t(α), right(α)) к логической программе Pπ ?Упражнение 1.128. Частично-рекурсивной функцией называется всякая частично определенная функция натурального аргумента f (n) : Nn0 → N0 , которая может быт построена избазовых функций• константы 0,• функции следования s(1) (x) = x + 1,32Глава 1.

УПРАЖНЕНИЯ• селекторных функций I (n) (x1 , x2 , . . . , xn ) = xm , n ≥ 1, 1 ≤ m ≤ n,при помощи следующих операций:(m)(m)1. суперпозиция S: для любой функции f (n) и набора из n функций g1 , . . . , gn , в результате применения операции суперпозиции S[f, g1 , . .

. , gn ] образуется функцияh(m) (x1 , . . . , xm ) = f (g1 (x1 , . . . , xm ), . . . , gn (x1 , . . . , xm ));2. примитивная рекурсия Π: для любой пары функций f (n) и g (n+2) в результате применения операции примитивной рекурсии Π[f, g] образуется функция h(n+1) (x1 , . . . , xn , xn+1 ),удовлетворяющая для любого набора значений переменнных x1 , . . . , xn и любого натурального числа k следующим двум равенствам:h(x1 , .

. . , xn , 0) = f (x1 , . . . , xn ),h(x1 , . . . , xn , k + 1) = g(x1 , . . . , xn , k, h(x1 , . . . , xn , k));3. неограниченная минимизации µ: для любой функции f (n) , n ≥ 1 в результате применения операции неограниченной минимизации µ[f ] образуется функция h(n) (x1 , . . . , xn ),значение которой для любого набора значений переменнных x1 , .

. . , xn−1 , xn удовлетворяет следующему соотношению:k,если существует такое натуральное число k, чтоi) выполняется равенство f (x1 , . . . , xn−1 , k) = xn ,ii) для любого m, 0 ≤ m ≤ k − 1,значение функции f (x1 , . .

. , xn−1 , m)h(x1 , . . . , xn−1 , xn ) =определено и отлично от xn ,неопределено в противном случае.Из тезиса Черча следует, что класс эффективно вычислимых арифметических функций совпадает с классом частично-рекурсивных функций. Поэтому для доказательства алгоритмической полноты хорновских логических программ достаточно показать, что все частичнорекрсивные функции могут быть вычислены логическими программами.Условимся представлять натуральные числа в виде списков: пустой список nil будет обозначать число 0, одноэлементный список nil nil — число 1, список nil nil nil — число 2 и т. д.Список, соответствующий натуральному числу k, будем обозначать k.Покажите, что для каждой частично-рекурсивной функции f (x1 , .

. . , xn ) можно ввести пре(n+1)дикатный символ Pfи построить такую хорновскую логическую программу Pf , котораяна любой запрос G : ? Pf (k1 , . . . , kn , Y ).. .• вычисляет единственный ответ {Y /m} тогда и только тогда, когда f (k1 , . . . , kn ) = m,• не имеет успешных вычислений тогда и только тогда, когда значение f (k1 , .

. . , kn ) неопределено.Упражнение 1.129. Выясните, можно ли построить алгоритмы, способные для любойхорновской логической программы P, произвольного запроса G и произвольной подстановкиθ выяснить,1.13. Алгоритмическая полнота и алгоритмическая неразрешимость.331. является ли дерево SLD-резолютивных вычислений запроса G к логической программеP конечным?2. является ли подстановка θ правильным ответом на запрос G к программе P?3. является ли подстановка θ вычисленным ответом на запрос G к программе P?4. существует ли хотя бы один запрос к программе P, для которого существует успешноевычисление?5.

существует ли бесконечно много различных успешных вычислений запроса G к программе P?6. верно ли, что нак запрос G программа P вычисляет то же самое множество ответов,что и некоторая заданная хорновская логическая программа P 0 ?Упражнение 1.130.

Докажите, что ни одна система автоматического доказательства теорем не может гарантировать решения следующих вопросов для произвольных формул логикипредикатов:1. является ли заданное предложение ϕ логическим следствием заданного множества предложений Γ?2. является ли заданная формула ϕ противоречивой?3. является ли заданная формула ϕ выполнимой?4. является ли выполнимой система дизъюнктов Γ = {D1 , . . . , DN }, каждый дизъюнкт Diкоторой содержит не более двух литер?5. имеет ли заданное предложение ϕ конечную модель?6.

являются ли две формулы логики предикатов ϕ1 и ϕ2 равносильными?Упражнение 1.131. Алгоритмическая неразрешимость проблемы общезначимости для логики предикатов первого порядка не отменяет возможности построения алгоритмов, проверяющих общезначимость формул специального вида.Докажите, что существует алгоритм, проверяющий общезначимость т. н. ∀-формул, предваренная нормальная форма которых имеет вид∀x1 ∀x2 . . . ∀xn ϕ(x1 , x2 , . . .

, xn ).Каков этот алгоритм?Упражнение 1.132. Докажите, что не существует алгоритма, проверяющего общезначимость т. н. ∃-формул, предваренная нормальная форма которых имеет вид∃x1 ∃x2 . . . ∃xn ϕ(x1 , x2 , . . . , xn ).А существует ли алгоритм проверки общезначимости ∃-формул, в матрице ϕ(x1 , x2 , .

. . , xn )которых не содержится функциональных символов?34Глава 1. УПРАЖНЕНИЯУпражнение 1.133. Докажите, что не существует алгоритма, проверяющего общезначимость формул, предваренная нормальная форма которых имеет вид∃x1 ∃x2 ∃x3 ∀y1 . . . ∀yn ϕ(x1 , x2 , x3 , y1 , . . . , yn ),где n ≥ 1.Упражнение 1.134. Диадической логикой называется множество формул логики предикатов, содержащих только двухместные предикатные символы.

Постройте алгоритм, которыйдля произвольной формулы логики предикатов ϕ строит такую формулу диадической логикиϕ∗ , для которой верно соотношение:|= ϕ ⇐⇒ |= ϕ∗ .Докажите, что проблема общезначимости формул диадической логики алгоритмически неразрешима.Упражнение 1.135. Докажите, что не существует алгоритма, проверяющего общезначимость формул диадической логики, построенных в сигнатуре σ = h∅, ∅, {P (2) }i, т. е.

формул несодержащих констант и функциональных символов и содержащих только один двухместныйфункциональный символ P (2) .Упражнение 1.136. Постройте алгоритм, проверяющий общезначимость формул монади(1)(1)(1)ческой логики, т. е. формул, которые строятся в сигнатуре σ = h∅, ∅, {P1 , P2 , . . . , PN }i,не содержащей констант и функциональных символов и содержащей только одноместныепредикатные символы P1 , P2 , . . .

, PN .Сохранится ли алгоритмическая разрешимость проблемы общезначимости для формул, построенных из одноместных предикатов, в том случае, если в этих формулах наряду с предикатами разрешить использовать многоместные функциональные символы?.

Характеристики

Тип файла
PDF-файл
Размер
344,27 Kb
Тип материала
Высшее учебное заведение

Список файлов учебной работы

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6508
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее