Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 40

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

2.8. 1) Доказатгч что однократное применение операции миними- зации к всюду определенной числовой функции приводит к функции, определенной хотя бы в одной точке. 2) Привести пример одноместной примитивно рекурсивной функ- ции, из которой двукратным применением операции минимизации можно получить нигде не определенную функцию. 3) Сформулировать условие, необходимое и достаточное для того, чтобы функция д . г"(я) была нигде не определенной.

4) Сформулировать необходимое и достаточное условие того, что числовая функция д. 1(ж) является всюду определенной. 5) Доказать, что ссли функция у(т, у) нс является всюду опреде- ленной, то таким же свойством обладает каждая из функций длу(х, у) и ди((т, у). 2.5. Применить операцию минимизации к функции г' по переменной ж, (результирукгщукг функцию представить в «аналитической» форме): 1) ((т1) = 3, г = 1; 2) ((тг) = жг + 2, г = 1; 3) г(тг) = тг †' 2, г = 1; 4) 7(тг) = тг — 2, г = 1; 5) ((тг) = 2тг + 1, г = 1; 6) ((тг) = 2тг †' 1, 1 = 1; у'2.

Классы емчиелилых и рекурсивных фуякций 201 2.9. 1) У всюду определенной функции ?(х, д) обе переменные существенные. Предположим, что рх~(х, д) и ду?(х, д) -- всюду определенные функции. Может ли хотя бы одна из этих функций зависеть существенно только от одной переменной? 2) У всюду определенной функции Дх, д) ровно одна существенная переменная.

Могут ли у функции д,у(х, д) быть существенными обе переменные, если предположить дополнительно, что она всюду определена? 2.10. Обосновать вычислимость следующих функций: 1) е( ) ~ ] ( . зб(2х, )),( + 1)з. 2) Дх, д, х) = ( — '+ 2~ ?~~) ((хз — ' д) + х)); 3) ?(х, д, х) = 4л " ' — (хз+ 1)з.

(зб(х — ' 2У) + я); з з 4) ((х, д, х) = У 2се т"Р-Я~х хт1 2.11. Каковы мощности классов К„р, К,р, К„„и К„? 2. Некоторые специальные свойства рекурсивных функций. 2.12. Опровергнуть следующее утверждение: если машина Тьюринга вычисляет функцию ~з(х) Е К„р~К„р, то вычислимая на этой машине функция ?з(х, д) не является примитивно рекурсивной. 2.13. 1) Машины Тьюринга Т, и Тз вычисляют примитивно рекурсивные функции ~х(х) и ?з(х) соответственно. Следует ли отсюда, что композиция ТзТя этих машин вычисляет обязательно примитивно рекурсивную функцию? А если машины Тз и Тз правильно вычисляют функции?з и ?з? 2) Машина Тьюринга Т вычисляет примитивно рекурсивную функцию )(х). Справедливо ли следующее утверждение: если итерация машины Т вычисляет некоторую всюду определенную функцию д(х), то функция д(х) обязательно примитивно рекурсивна? 2.14.

Известно, что ?(х) Е Кер и что при всех х ) 0 выполняются соотношения Д(2х) = ? (х + 1) и ?" (2х + 1) = Д(х) . Вытекает ли отсюда, что? (х) примитивно рекурсивная функция? 2.15. Функции ед(х) и дз(х) являются всюду определенными вычислимыми функциями, удовлетворяющими следующому условию: какова бы ни была примитивно рекурсивная функция у(х), найдется хс такое, что з(хс) < дз(хв) + дз(хс). Показать, что хотя бы одна из функций дз(х) и дз(х) не является примитивно рекурсивной.

2.16. Функция у'(х) принадлежит множеству К„р)К„р (т. е. общерекурсивна, но не является примитивно рекурсивной функцией). Показать, что каждая из приводимых ниже функций также содержится в множестве К„р~К„р: 1) ?(х+ 3) 2) ?(х — '2); 3) ?(Н); 4) Яз?х)) 5) ?(х дз) 202 Гж 'е'. Зоемеиты теории алгоритмов б) 1(х — ' р'); 7) 1(2и +р); 8) 1(~ Р~). 2.17.

Пусть частично рекурсивная функция ~(ж) такова, .что функ- ция д(х), опредсляемая условием ( 0 в тех точках, где ~(х) определена, М.)=' 11 в точках, где Дт) не определена, является общерекурсивной. Показать, что функцию Дх) можно до- определить до общерекурсивной функции. 2.18. Выяснить, образует ли множество М полную систему отно- сительно совокупности операций Ю в классе К„р, если: 1) М = Ки„~Кар, б = 1операции примитивной рекурсии и мини- мизации); 2) М = Кар~Кот Ю = (операция отождествления переменных); 3) М = Кор1К„ю Ю = )операции суперпозиции и минимизации).

Глава У1 ГРАФЫ И СЕТИ З 1. Основные понятия теории графов 1. Простейшие свойства графов. Изоморфизм графов. Пусть г' — - конечное непустое множество и Х вЂ” некоторый набор пар элементов из г'. В наборе Х могут встречаться пары, состоящие из одинаковых элементов, а также одинаковые пары. Множество Ь' и набор Х определяют граф с кратными ребрамп, а петлями (или, короче, гшввдогрпф) С = (Г, Х). Элементы множества Р' называются веришншми псевдографа, а элементы набора Х -- ребрами псевдо- графа. Ребра вида (о, о), о е р', называются петлями.

Псевдограф без петель называется графом с кратнымя ребра и (или, короче, мультиграфом). Если в наборе Х нет петель и ни одна пара не встречается более одного раза, то мультиграф С = (Г, Х) называется графом. Ниже почти все определения даются для графов. Эти определения, как правило, легко переносятся на мультиграфы и псевдографы.

В тех случаях, когда различия в определениях существенны, даются определения и для псевдографов. Если пары в набора Х являются упорядоченными, то граф называется ориентированным графом (или, короче, орграфом). Ребра ориентированного графа часто называются дугами. Если пары в наборе Х являются неупорядоченными, то граф называется неориснтированным графом (или просто графом). Если и = (и, о) †.

ребро графа, то вершины и и и называются концами ребра т. Если вершина и является концом ребра и, то говорят, что о и т инцидентны. Вершины и и о графа С называются смежными., если существует ребро графа С, соединяющее их (т. е, (и, о) б Х). Лва ребра называются смежными если они имеют общую вершину. Степенью вершины о (обозначения д(о) и йе„(о)) называется число ребер графа, инцицентных вершине и. В псевдографе степень вершины и равна общему числу ребер (и петель), инцидентных этой вершине, сложенному с числом петель, инцидентных ей (т.е.

каждая петля, инцидентная вершине о, в величину степени вершины о «вносит вклад», равный 2). Вершина графа, имеющая степень О, 204 Гл. Уй Графы и сети называется изолированной, а вершина, имеющая степень 1, висячей (ипи концевой). Ребро, инцидентное висячей вершине, называют концевым. Последовательность п»х» игхгпз... ил»х„— »ио (и Ъ 2), в которой чередуются вершины и ребра и при етом дпя каждого 1 = = 1, ..., и — 1 ребро х; имеет вид (ин и,, »), называется маршрутом, соединяющим всришны и» и ив (или, короче, (ю~, ин)-маршру1пом). Число ребер в маршруте называется его длиной. Маршрутом длины нуль называется последовательность, состоящая из единственной вершины.

Маршрут, в котором всо ребра разные, называется цепью. Маршрут, в котором все вершины разные, называется простой цепью. Маршрут (1) называется замкнуп»ььм, если и» = и„. Замкнутый маршрут, в котором все ребра различные, называется циклом. Цикл, в котором все вершины, кроме первой и последней, разные, называется простым циклом. Граф называется связным, если для любых двух различных его вершин существует цепь (маршрут, простая цепь), соединяющая их. Расстоянием между вершинами связного графа называется длина кратчайшей (а значит, простой) цепи, соединяющей зти вершины. Яиаметром связного графа называется расстояние между двумя наиболее удаленными друг от друга вершинами.

Лиаметр графа С обычно обозначают через Р(С). Подграфо,м графа С называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа С. Подграф называется собственным, если он отличен от самого графа. Компонентой связности (или, короче, компонентой) графа С называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа графа С.

Остовным называется подграф, содержащий все вершины графа. Подграфом графа С = (У, Х), порожденным подмножеством П (П С У), называется граф Н = (все, У), множество робер которого состоит из тех и только тех ребер графа С, оба конца которых лежат в П. Графы (псевдографы) С = (ь'., Х) и Н = (с», У) изоморфны, если существуют такие два взаимно однозначных соответствия ун У е» П и ф; Х е» У, что ддя всякого ребра х = (и, и) из Х справедливо соотношение у»1х) = г»»(и), у»(и)). В случае графов можно дать следующее определение.

Графы С = = (ь'., Х) и Н = (с», У) пзоморфны, если существует такое взаимно однозначное отображение у»: У е» П, что (и, и) е Х тогда и только тогда, когда (у»(и), р(и)) Е У. Такое отображение у» называется изоморфным (или изоморфизма,м). Операция удаления вершины из графа С состоит в удалении некоторой вершины вместе с инцидентными ей ребрами. Операция уда,— ления ребра из графа С = (Ъ; Х) заключается в удадении соот- г 1.

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

Список файлов книги