X
Контрольная работа по дисциплине «Дискретная математика»
Контрольные вопросы.
Вариант 1
Отношение. Общие свойства отношений.
Операции над графами
Симметризация отношений. Сечения отношения. Композиция отношений.
Матричные представления графов
Вариант 2
Отношение эквивалентности. Классы эквивалентности. Свойства классов эквивалентности
Структура автоматов.
Независимые множества. Клики в графе.
Связность и компоненты графа
Вариант 3
Равносильности алгебры предикатов. Способы их доказательства
Теорема Тьюринга.
Подграфы и типы графов.
Интуитивное понятие алгоритма.
Контрольная работа № 00
по предмету «Дискретная математика»
(код ДИ)
Задание 1.Дан граф с вершинамиA,B,C,D,Eи ребрамиAB,AC,BC,BD,BE,DE. Укажите в нем эйлерову линию.
Задание 2. На вопрос: «Кто из трех студентов изучал математическую логику?» получен верный ответ - «Если изучал первый, то изучал и третий, но неверно, что если изучал второй, то изучал и третий.» Ответьте, кто изучал математическую логику?
Задание 3.Докажите общезначимость формулы> с помощью алгоритма редукции.
Задание 4.Найти совершенную д.н.ф. для формулы:> .
Задание 5.Найти КНФ формулы> путем эквивалентных преобразований.
Задание 6.Выразить функцию> формулой, в которой использована только импликация и отрицание.
Задание 7.Проверьте однозначность алфавитного кодирования со схемой> :
>
Задание 8.Дана формула> , в которой предикаты определены на множестве натуральных чисел. Найти значение этой формулы, если
> : «числохделится на 3 без остатка»;
> : «числохделится на 4 без остатка»;
> : «числохделится на 2 без остатка»;
Задание 9.Вычислить значение формулы> , если предикат> имеет значение «числоxменьше числаy» и определен для любых натуральных чиселxиy.
Задание 10.Постройте модель для формулы:> .
СБОРНИК ЗАДАНИЙ
ПО ПРЕДМЕТУ «ДИСКРЕТНАЯ МАТЕМАТИКА» (код ДИ)
Задание 1
Изучить главу 1 части 1. Выписать в конспект определения и формулировки теорем. Выполнить практическое задание N 1 из приложения.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Что нужно задать (начертить или записать) для того, чтобы строго определить граф, не являющийся нуль-графом?
1. Таблицу футбольных соревнований
2. Ломанную кривую линию
3. Набор точек и набор линий, их соединяющих
4. Начертить несколько пересекающихся линий
5. Поставить несколько точек и обозначить их буквами
Вопрос 2. Чему равно число ребер полного графа> ?
1.>
2.>
3.>
4.>
5.>
Вопрос 3. Какие графы называют изоморфными?
1. Графы, изображения которых при наложении совпадают
2. Графы, у которых число ребер совпадает
3. Графы, у которых одинаковое количество вершин
4. Графы, у которых ребра пересекаются только в вершинах
5. Графы, у которых одинаковое количество вершин (обозначим его> ) и одинаковое количество ребер, причем можно так пронумеровать вершины каждого графа числами от 1 до> , чтобы, если в одном графе соединены ребром вершины с номерами> и> , то и в другом графе вершины> и> тоже обязательно соединены ребром
Вопрос 4. Какие графы называют плоскими?
1. Графы, начерченные на плоской поверхности
2. Графы, все ребра которых являются отрезками прямых линий
3. Графы, начерченные так, что их ребра пересекаются только в вершинах
4. Графы, изображающие улицы города
5. Графы, которые можно начертить так, что их ребра будут пересекаться только в вершинах
Вопрос 5. Предположим, что граф> имеет 5 вершин со степенями 4, 1, 1, 3, 1. Каково число ребер этого графа?
1. 10
2. 8
3. 7
4. 5
5. 6
Задание 2
Изучить главу 2 части 1. Выписать в конспект определения и формулировки теорем.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Рассмотрим граф на Рис.13. Какая из указанных ниже последовательностей ребер является элементарной цепью?
1.A B C D E G B A
2.C E G A F E D
3.G F E C B A F
4.F A G B C D E
5.E C D E F G
Вопрос 2. Рассмотрим граф на Рис.13. Какая из указанных ниже последовательностей ребер является циклом?
1.A G E D C B
2.A F E D C E G A
3.A G E F G A
4.G B C D E G F
5.E G F E D C B
Вопрос3. Рассмотрим пять разных графов с одинаковым числом вершин, обозначенныхA,B,C,D,E.Ниже для каждого из этих графов указан набор степеней вершин. Какому из наборов соответствует граф, имеющий цепь, содержащую все его ребра по одному разу?
1.> (A)=1,> (B)=3,> (C )=3,> (D)=3,> (E)=4
2.> (A)=2,> (B)=3,> (C )=1,> (D)=1,> (E)=3
3.> (A)=0,> (B)=3,> (C )=3,> (D)=3,> (E)=3
4.> (A)=1,> (B)=3,> (C )=1,> (D)=3,> (E)=2
5.> (A)=2,> (B)=3,> (C )=2,> (D)=1,> (E)=2
Вопрос 4. Что называют эйлеровым графом?
1. Граф, сумма степеней вершин которого четна
2. Граф, в котором можно найти путь, проходящий через все ребра равно по одному разу
3. Граф, ребра которого соответствуют кенигсбергским мостам
4. Граф, имеющий цикл, содержащий все ребра, причем по одному разу каждое
5. Граф, который не содержит эйлеровой линии
Вопрос 5. В каком случае граф не имеет эйлеровой линии?
1. Если граф является эйлеровым
2. Если граф является связным
3. Если в графе нет цикла, содержащего по одному разу все его ребра
4. Если граф является связным и степени всех его вершин четны
5. Во всех перечисленных случаях граф может иметь эйлерову линию
Задание 3
Изучить главу 3 части 1. Выписать в конспект определения и формулировки теорем. Выполнить практическое задание N 2 из приложения.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Что называется деревом?
1. Граф, содержащий по крайней мере один цикл.
2. Граф, имеющий гамильтонову линию.
3. Граф, заданный матрицей инцидентности.
4. Однородный граф, у которого число ребер> , где> - число вершин графа,> - степень графа.
5. Связный граф, не содержащий циклов.
Вопрос 2. Что называется лесом?
1. Множество деревьев.
2. Граф, образованный при соединении ребрами некоторого числа деревьев.
3. Граф с> вершинами, имеющий> ребер.
4. Граф, полученный добавлением ребер к некоторому дереву.
5. Граф, образованный из дерева путем соединения корня ребрами со всеми концевыми вершинами.
Вопрос 3. Сколько компонент содержит лес, состоящий из> вершин и> ребер?
1.>
2.>
3.>
4.>
5.>
Вопрос 4. Если у графа> вершин и> ребер, то чему равно его цикломатическое число?
1.>
2.>
3.>
4.>
5.>
Вопрос 5. При каком условии можно установить взаимно однозначное соответствие между ребрами и инцидентными вершинами связного графа?
1. Наличие гамильтоновой линии.
2. Отсутствие эйлеровой линии.
3. Требуется, чтобы граф являлся деревом.
4. Граф должен совпадать со своим единственным циклом.
5. Отсутствие гамильтоновой линии.
Задание 4
Изучить главу 4 части 1. Выписать в конспект определения и формулировки теорем. Повторить п. 3.1 главы 3 части 1.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Какой граф называется двудольным?
1. Граф, множество вершин которого> можно разбить на два непересекающихся множества> и> так, что для любых двух вершин> если> , то в графе нет ребра, соединяющего> и> .
2. Граф, распадающийся на два графа после удаления одного ребра.
3. Граф состоящий из двух непересекающихся циклов.
4. Граф, множество вершин которого> можно разбить на два непересекающихся множества> и> > так, что если> и> или> и> или> и> , то в графе отсутствует ребро, соединяющее> и> .
5. Граф, множество вершин> которого можно разбить на два непересекающихся множества> и> > так, что если вершина> , а вершина> , то в графе существует ребро, соединяющее> и> .
Вопрос 2. Какое условие является достаточным для того, чтобы была разрешимой задача о назначениях на должности?
1. Условие однородности графа возможных назначений.
2. Граф возможных назначений должен быть двудольным.
3. Условие разнообразия.
4. Условие Коши.
5. Граф возможных назначений должен быть связным.
Вопрос 3. Каким графом с> или> вершинами удобно изобразить встречи "кругового турнира", когда каждый из> участников должен сыграть с каждым?
1. Деревом.
2. Двудольным графом.
3. Эйлеровым графом.
4. Полным графом.
5. Бинарным деревом.
Вопрос 4. Какому графу соответствует структура каталога файлов персонального компьютера?
1. Двудольному.
2. Полному графу.
3. Эйлерову.
4. Лесу.
5. Бинарному дереву.
Вопрос 5. Что называется листом дерева?
1. Минимальный цикл.
2. Концевая вершина.
3. Изолированная вершина.
4. Корень дерева.
5. Любая вершина дерева.
Задание 5
Изучить главу 5 части 1. Выписать в конспект определения, формулировку теоремы, условия описания графом генетического эксперимента.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Какой граф называется ориентированным?
1. Граф, имеющий единственную элементарную цепь.
2. Граф, не имеющий циклов.
3. Граф, цикломатическое число которого равно единице.
4. Граф, цикломатический порядок которого совпадает с цикломатическим числом.
5. Граф, на каждом ребре которого указано направление.
Вопрос 2. Какой граф называется смешанным?
1. Граф, имеющий как ориентированные, так и неориентированные ребра.
2. Граф, который после удаления некоторого ребра распадается на дерево и полный граф.
3. Граф, множество вершин которого> представляет собой объединение множества вершин> и> , причем, если вершина> , а> , то на ребре, соединяющем> с> заданно направление от> к> .
4. Неоднородный граф.
5. Граф, состоящий из нескольких связных компонент.
Вопрос 3. В каком случае ребро, соединяющее вершины> ,> графа называется перешейком?
1. Если оно является единственным путем графа от> к> .
2. Если этому ребру приписывается ненулевая пропускная способность.
3. Если его удаление не нарушает связности графа.
4. Если оно является единственным ребром графа, для которого не указано направление.
5. Если граф описывает структуру гидротехнических сооружений.
Вопрос 4. Что называется циклическим ребром?
1. Любое ребро ориентированного графа.
2. Ребро кратности 1.
3. Ребро кратности более 1.
4. Любое ребро, не являющееся связывающим.
5. Ребро, входящее в ту же вершину, из которой оно выходит.
Вопрос 5. Какому из условий не удовлетворяет граф, описывающий генетический эксперимент?
1. Граф является ациклическим.
2. Число ребер каждого "чередующегося" цикла кратно четырем.
3. Граф содержит по крайней мере один ориентированный цикл.
4. Каждая из вершин графа имеет не более двух входящих ребер.
5. Для каждой вершины> графа> .
Задание 6.
Изучить п.п. 1.1, 1.2 главы 1 части 2. Выписать определения, формулировку теорем, вид и табличное представление элементарных функций. Выполнить практическое задание N 3 из приложения.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Что такое булевская функция?
1. Функция, принимающая значение 0 или 1, аргументами которой являются буквы.
2. Функция> , аргументы которой определены на множествеE2={0, 1}, значения которой - целые числа.
3. Функция, определенная на множестве {0, 1}, от переменных, каждая из которых может принимать значение 0 или 1.
4. Функция> на множествеE2, для которой выполняется условие> приn1m.
5. Здесь нет правильного определения.
Вопрос 2. Каково число функций алгебры логики, зависящих от S переменных?
1.S2
2.>
3.>
4.>
5. 2S
Вопрос 3. Какая из переменных является фиктивной в функции
>
Используйте табличное представление функции.
1. x1
2. x2
3. x3
4. x4
5. Функция не имеет фиктивных переменных.
Вопрос 4. Какая из приведенных функций не является симметрической относительно переменных x1, x2?
1.>
2.>
3.>
4. x1/ x2
5. x1® x2
Вопрос 5. Кто из ученых первым попытался создать аксиоматическое построение математической теории?
1. Рассел
2. Аристотель
3. Клейн
4. Евклид
5. Лобачевский
Задание 7.
Изучить п. 1.3 главы 1 части 2 и входящие в него примеры формализации условий. Выписать в конспект определения. Повторить определения элементарных булевских функций.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Какая из следующих импликаций не является истинной?
1. если 2 ` 2 = 4, то 2
2. если 2 ` 2 = 4, то 2 > 3
3. если 2 ` 2 = 5, то 2
4. если 2 ` 2 = 5, то 2 > 3
5. Ни одна из импликаций не является истинной.
Вопрос 2. При каких значениях x и y выполняется равенство (1 ® x) ® y = 0
1. x = 0, y = 0
2. x = 0, y = 1
3. x = 1, y = 0
4. x = 1, y = 1
5. Равенство всегда неверно.
Вопрос 3. Пусть> . Которая из формул является формулой над> ?
1.>
2.>
3.>
4.>
5.>
Вопрос 4. Которая из формул реализует функцию> ?
1.>
2.>
3.>
4.>
5.>
Вопрос 5. Которое из следующих предложений (выражений) нельзя представить (реализовать) функцией алгебры логики?
1. Москва - столица России
2.a > b
3. Луна есть спутник Марса
4. (a - b) b
5.a - b.
Задание 8.
Изучить п. 1.4 и 1.5 главы 1 части 2 и входящие в него примеры и замечания. Выписать в конспект определения, свойства элементарных функций, формулировки теорем и принципа двойственности. Выполнить практическое задание N 4 из приложения.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Под каким из номеров записаны неэквивалентные формулы?
1.>
2.>
3.>
4.>
5. Под всеми номерами даны пары эквивалентных формул.
Вопрос 2. Под каким из номеров записана пара функций не являющихся двойственными друг другу?
1.
| x1 | x2 | x3 | f1(x1,x2,x3) | f2(x1,x2,x3) |
| 1 | 1 | |||
| 1 | 1 | 1 | ||
| 1 | ||||
| 1 | 1 | 1 | ||
| 1 | ||||
| 1 | 1 | 1 | 1 | |
| 1 | 1 | |||
| 1 | 1 | 1 |
2.>
3.>
4.>
5. Под каждым из предыдущих номеров записана пара двойственных функций.
Вопрос 3. Под каким номером записана функция, двойственная кx1®x2?
1.>
2.>
3.
| x1 | x2 | f(x1,x2) |
| 1 | ||
| 1 | 1 | |
| 1 | ||
| 1 | 1 | 1 |
4.>
5.>
Вопрос 4. Под каким номером представлена совершенная д. н. ф. функции> ?
1.>
2.>
3.>
4.>
5.>
Вопрос 5.Рассмотрим функцию,заданную таблицей
| x1 | x2 | x3 | f(x1,x2,x3) |
| 1 | |||
| 1 | |||
| 1 | 1 | ||
| 1 | 1 | ||
| 1 | 1 | 1 | |
| 1 | 1 | ||
| 1 | 1 | 1 |
В какой из строк указано разложение этой функции по переменнойx3?
1.>
2.>
3.>
4.>
5.>
Задание 9.
Изучить п. 1.6 главы 1 части 2. Выписать в конспект определения и теоремы. Выполнить практическое задание N 5 из приложения.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Под каким из номеров система функций не является полной?
1.>
2.>
3.>
4.>
5. Все приведенные системы функций являются полными.
Вопрос 2. Под каким из номеров представлена формула, не являющаяся полиномом Жегалкина?
1.>
2.>
3.>
4.>
5.>
Вопрос 3. Под каким из номеров представлен полином Жегалкина для функции> ?
1.>
2.>
3.>
4.>
5.>
Вопрос 4. Которая из функций имеет совершенную д. н. ф.> ?
1.>
2.>
3.>
4.>
5.>
Вопрос 5. Которая из строк содержит неверное утверждение?
1.>
2.>
3.>
4.>
5.>
Задание 10.
Изучить п.п. 1.7, 1.8 главы 1 части 2. Выписать в конспект определения и теоремы. Выполнить практическое задание N 6 из приложения.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Каково количество булевых функцийnпеременных, сохраняющих константу 1?
1.>
2. 2n
3. 2n-1
4.>
5. Здесь нет верного ответа.
Вопрос 2. Каково число самодвойственных функций отnпеременных?
1.>
2. 2n-1
3.>
4.>
5. 0.
Вопрос 3. Какой из приведенных классов функций не является замкнутым?
1. Класс S самодвойственных функций.
2. Класс Т1функций, сохраняющих константу 1.
3. Класс L линейных функций.
4. Класс> .
5.P2
Вопрос 4. Какой из перечисленных ниже классов функций не является полным?
1. Класс, образованный функциями из Т1и Т.
2. Класс, образованный монотонными функциями и функциейх.
3. Класс, образованный линейными и самодвойственными функциями.
4. Класс, образованный функциями из Ти функцией> .
5. Класс, образованный монотонными функциями и функцией> .
Вопрос 5. Сколько всего предполных замкнутых классов?
1. 1
2. 2
3. 3
4. 4
5. 5
Задание 11
Изучить п.п. 2.1 - 2.3 главы 2 части 2. Выписать определения в конспект.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Какой из перечисленных ниже символов не используется в исчислении высказываний для обозначения логических или пропозициональных связок?
1.>
2.>
3.>
4.>
5.>
Вопрос 2. Сколько символов включает в себя пропозициональный логический словарь?
1. Бесконечное счетное множество
2. 5
3. 38
4. 33
5. Около сотни
Вопрос 3. Что такое грамматика исчисления высказываний?
1. Это - грамматика русского языка
2. Это - правила вычисления значений формул
3. Это - правило образования формул из высказываний с помощью пропозициональных связок
4. Это - набор международных обозначений
5. Это - часть грамматики английского языка
Вопрос 4. Какая из строк содержит формулу, не относящуюся к исчислению высказываний?
1.> &>
2.>
3.&>
4.>
5.a>
Вопрос 5. Какой объект позволяет описать порядок применения правил построения формулы из подформул?
1. Дерево
2. Элементарная цепь графа
3. Многоугольник
4. Матрица
Задание 12
Изучить п.п. 2.4 - 2.6 главы 2 части 2. Выписать определения в конспект.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Что называется моделью формулы?
1. Словесное описание формулы
2. Интерпретация, при которой формула принимает значение И
3. Отображениеi, сопоставляющее каждому элементарному высказыванию значение И или Л
4. ИнтерпретацияIзаданная на множестве формул посредством таблиц истинности
5. Булевская функция, соответствующая формуле
Вопрос 2. Обозначим литеройpутверждение, что некоторое целое числоxявляется четным, а литеройq- утверждение, что целое числоx- нечетно. Как на языке исчисления высказываний записывается утверждение естественного языка "целое число четно или нечетно"?
1.>>
2.>
3.>
4.>
5.>
Вопрос 3. В каком случае множество формулEназывается выполнимым или семантически выполнимым?
1. Если существует интерпретация, которая является моделью для каждой из формул множестваЕ
2. Если конъюнкция всех формул множестваЕобщезначима
3. Если каждая из формул множестваЕявляется выполнимой
4. Если все формулы изЕявляются общезначимыми
5. Если определен способ определения истинности каждой формулы изЕ
Вопрос 4. В чем состоит проблема дедукции?
1. В решении любой логической задачи
2. В развитии способностей по анализу ситуаций
3. В решении вопроса: "Является ли формула общезначимой?"
4. В проверке: является ли формула логическим следствием заданного множества формул
5. В проверке общезначимости множества формулЕ
Вопрос 5. Как символически записывается принцип дедукции?
1.>
2.>> C>
3.>>
4.B> A> >>
5.> A
Задание 13
Изучить п.п. 2.7 - 2.9 главы 2 части 2. Выписать в конспект определения, свойства и эквивалентные преобразования. Выполнить практическое задание N 10 из приложения. Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Чем отличается семантическое деревоD, построенное по алгоритму Куайна для формулыС, от полного семантического дерева?
1. В деревеDотсутствуют листья, соответствующие моделям формулыС
2. Вычисление значения формулыСдля всех интерпретаций, соответствующих листьям дереваD, невозможно
3. Вычисление значения формулыСдля всех интерпретаций, соответствующих листьям дереваD, позволяет судить о выполнимостиС, но не позволяет судить о ее общезначимости
4. В деревеDотсутствуют некоторые поддеревья, листьям которых соответствуют модели формулыС
5. В полном дереве формулыСменьше листьев, чем у дереваD
Вопрос 2. Для чего предназначен алгоритм редукции?
1. Для поиска моделей
2. Для построения интерпретаций
3. Для проверки выполнимости формул
4. Для построения семантического дерева
5. Для доказательства общезначимости
Вопрос 3. Под какой цифрой представлена запись применения алгоритма редукции к формуле
> ?
1.>>>> > что противоречит>
2.>>>> > что противоречит>
3.>>>>> что соответствует>
4.> > > > > что противоречит>
5. Здесь нет записи, представляющей применение алгоритма редукции к указанной формуле
Вопрос 4. Каким из перечисленных свойств не обладает отношение порядка> ?
1. Рефлексивность
2. Антисимметричность
3. Транзитивность
4. Коммутативность
5. Элиминация
Вопрос 5. В какой строке указан закон де Моргана?
1.>
2.>
3.>
4.>
5.>
Задание 14
Изучить п.п. 2.10-2.11 главы 2 части 2. Выписать в конспект определения, эквивалентные преобразования и формулировку леммы и теоремы.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. При каком условии дизъюнктDявляется невыполнимым?
1. Если вместе с некоторой литеройpдизъюнкт содержит и ее отрицание> .
2. ЕслиDявляется тавтологией.
3. ЕслиDне является общезначимой формулой.
4. ЕслиDне является пустым дизъюнктом.
5. ЕслиDявляется пустым дизъюнктом.
Вопрос 2. Какая из формул является приведенной КНФ?
1.> &>
2.>>
3.>
4.>
5.>
Вопрос 3. Какая из формул является КНФ для> ?
1.>
2.>
3.>
4.>
5. Здесь нет КНФ для указанной формулы.
Вопрос 4. Какое из определений алгоритма Девиса и Патнема является более точным?
1. Это - модификация алгоритма редукции.
2. Это - алгоритм построения семантического дерева для КНФ, при котором не строят поддеревья для явно невыполнимых подформул и применяют специальное правило для выбора литеры (возможно литеры с отрицанием), приписываемой очередному ребру дерева.
3. Это - модификация алгоритма Куайна, в которой не строятся поддеревья для невыполнимых подформул> или> .
4. Это - алгоритм проверки общезначимости, КНФSс помощью семантического дерева, при котором предпочтение при выборе очередной литеры отдается литереp, если вSвходит толькоpили> .
5. Это - усовершенствованный алгоритм Куайна для проверки выполнимости КНФ.
Вопрос 5. Какую литеру следует выбрать на первом шаге проверки выполнимости множества> с помощью алгоритма Девиса и Патнема?
1.>
2.>
3.>
4.>
5.>
Задание 15
Изучить п.п. 2.12 - 2.14 главы 2 части 2. Выписать определения, формулировки лемм и их следствий.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. ПустьAиB- дизъюнкты. В какой строке дана формальная запись правила резолюций?
1.>
2.>
3.>
4.>
5.>
Вопрос 2. Пусть> и> - дизъюнкты нормальной формы> . В каком случае дизъюнкт> является резольвентой дизъюнктов> и> ?
1. Если существует литера> такая, что> , и если> .
2.>
3.>
4.>
5. Если> .
Вопрос 3. Какая из цепочек преобразования формул не может быть названа результатом применения метода резолюций?
1.> ;
> ,
> ,
> ,
>
2.>
>
>
>
>
>
3.>
>
>
>
4.>
>
>
> ,
>
>
>
5. Все представленные записи могут быть названы записями применения метода резолюций кS.
Вопрос 4. В каком случае алгоритм проверки выполнимости множества дизъюнктовSметодом резолюций будет бесконечным?
1. Если для образования резольвенты бесконечное число раз избирается одна и та же пара дизъюнктов> и> .
2. Если множество дизъюнктовSбесконечно.
3. Если множествоSневыполнимо.
4. Если число резольвент, которые требуется вычислить превышает> , гдеn- число разных высказываний, входящих вS.
5. Если множествоSсодержит все резольвенты своих элементов.
Вопрос 5. В каком случае можно утверждать, что множество дизъюнктовSвыполнимо?
1. Если множествоSбесконечно.
2. ЕслиSсодержит пустой дизъюнкт.
3. ЕслиSсодержит тавтологию.
4. ЕслиSне содержит ни одной пары дизъюнктов, позволяющих образовать резольвенту.
5. ЕслиSне содержит резольвенты своих элементов.
Задание 16
Изучить п. 2.15 главы 2 части 2. Выписать в конспект определения и формулировку теоремы.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Какой из приведенных ниже дизъюнктов не является хорновским?
1.>
2.>
3.>
4.>
5.>
Вопрос 2. Какой из приведенных ниже дизъюнктов является унитарным позитивным?
1.>
2.>
3.>
4.>
5.>
Вопрос 3. ПустьS- множество хорновских дизъюнктов без тавтологий, содержащее унитарный позитивный дизъюнкт, аN- число символов (с учетом повторений) присутствующих вS. Каково максимальное число шагов необходимых при проверке выполнимостиSметодом резолюций? (Под шагом понимается вычисление резольвенты).
1.>
2.>
3.>
4.>
5.>
Вопрос 4. ПустьM- множество моделей для конечного множества дизъюнктовS. Что называют минимальной моделью дляS?
1. Пересечение множества интерпретаций изМ.
2. ИнтерпретациюI, определяемую подмножеством высказываний (литер)> , которым она сопоставляет значениеИ.
3. Интерпретацию, определяемую минимальным по числу элементов подмножеством высказываний> , которым сопоставляется значениеИ.
4. Интерпретацию> , определяемую из равенства> (где> - подмножество высказываний, которым модельIсопоставляет значениеИ), если она является моделью.
5. Интерпретацию> , определяемую из равенства> (гдеJ- множество интерпретацийS,> - подмножество высказываний, которым модельIсопоставляет значениеИ), если она является моделью.
Вопрос 5. Сколько разных минимальных моделей может быть у множества хорновских дизъюнктов, включающего в себяNлитер (с учетом повторений)?
1.>
2.>
3.>
4.>
5.>
Задание 17
Изучить п.п. 3.1 - 3.4, 3.7, 3.8 главы 3 части 2. Выписать в конспект определения.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Какую константу можно назвать предикатной?
1. Индивидную константу.
2. Функциональную константу с определенным числом мест, принимающую значение И или Л.
3. Функциональную константу, обозначаемуюP,QилиR.
4. Булевскую константу.
5. Индивидную константу с нулевым числом термов.
Вопрос 2. Что такое "функциональная форма"?
1. Функциональная константа, для которой указан полный набор ее термов.
2. Это - д. н. ф. с кванторами> и> .
3. Набор индивидных констант, соединенных логическими связками.
4. Предикатная константа без термов.
5. Булевская константа.
Вопрос 3. Что такое "предикатная форма"?
1. Функциональные формы, соединенные логическими связками.
2. Предикатная константа, перед которой стоит квантор> или> .
3. Атом, соединенный связкой> с индивидной константой.
4. Предикатная константа, для которой указан полный набор ее термов.
5. Здесь нет определения предикатной формы.
Вопрос 4. Что такое "атом"?
1. Любой набор термов.
2. Предикатная форма или равенство.
3. Одноместная предикатная константа.
4. Булевская функция.
5. Элементарное высказывание.
Вопрос 5. Какая из записей не является формулой исчисления предикатов?
1.>
2.>
3.>
4.>
5.>
Задание 18
Изучить п.п. 3.5 - 3.6, повторить п.3.4. главы 3 части 2. Выписать в конспект новые определения и общезначимые схемы формул, касающиеся отношений между связками и кванторами.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. В какой из формул вхождение переменнойx- свободное?
1.>
2.>
3.>
4.>
5.>
Вопрос 2. Какая из схем не является общезначимой?
1.>
2.>
3.>
4.>
5.>
Вопрос 3. Что подразумевается под термином "подстановка" в исчислении предикатов?
1. Отображение множества атомов на множество> .
2. Отображение множества термов в множество переменных.
3. Отображение множества переменных в множество термов.
4. Отображение множества формул исчисления высказываний в множество формул исчисления предикатов.
5. Набор натуральных чисел.
Вопрос 4. Как обозначается множество переменных термаt?
1.>
2.>
3.>
4.>
5.>
Вопрос 5. Пусть формулаAсодержит свободные переменные> . В какой строке записано экзистенциональное замыкание формулыA?
1.>
2.>
3.>
4.>
5.>
Задание 19
Изучить п.1 части 3. Законспектировать, выписать определения.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Рассмотрим алфавиты> и> . Что называют алфавитным кодированием?
1. Схему, ставящую в соответствие каждой букве алфавита> некоторое слово из букв алфавита> .
2. Отображение из> в> .
3. Отображение некоторого множества> слов над алфавитом> в множество слов над алфавитом> .
4. Способ установления взаимно однозначного соответствия между элементами множества> и элементами множества> при> .
5. Установление взаимно однозначного соответствия между множеством слов над> и множеством слов над> .
Вопрос 2. Рассмотрим слово> , имеющее вид>> .Что не может быть названо префиксом слова> ?
1.> .
2.> .
3.> .
4. Пустое слово.
5. Все перечисленные выше слова и части слова могут быть названы префиксами слова> .
Вопрос 3. Пусть задана схема алфавитного кодирования> :
> ,
. . . . . .
> .
В каком случае говорят, что схема> обладает свойством префикса?
1. Если для любого> , такого, что> , слово> имеет префикс.
2. Если конец любого слова> не совпадает с его префиксом при> .
3. Если для любых> и> , удовлетворяющих неравенствам> , слово> не является префиксом слова> .
4. Если для любых> ,>> слово> является префиксом слова> .
5. Здесь нет подходящего ответа.
Вопрос 4. Рассмотрим схему кодирования десятичных цифр от 1 до 9 русскими буквами> такую, что номер буквы в алфавите совпадает с цифрой, которая этой буквой кодируется.
Какое из утверждений не является верным?
1. Схема> задает алфавитное кодирование.
2. Схема> задает равномерное кодирование.
3. Схема> обладает свойством префикса.
4. Не допускается кодирование слов (натуральных чисел) с пропущенными буквами (цифрами).
5. Схема> позволяет однозначно кодировать и декодировать наборы натуральных чисел.
Вопрос 5. Какое из утверждений является верным?
1. В данном разделе рассматриваются вопросы кодирования и декодирования информации, представленной только одним словом исходного алфавита> .
2. В данном разделе принято допущение, что информация не может быть искажена при передаче.
3. В данном разделе под каналом связи подразумевается устройство, декодирующее сообщения.
4. Канал связи - устройство для кодирования сообщений.
5. В данном разделе рассматривается передача сообщений, состоящих из групп слов.
Задание 20
Изучить п.2 части 3. Выписать в конспект формулировки теорем. Выполнить практическое задание N 8 из приложения.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Какая из схем не обеспечивает взаимно однозначного кодирования?
1.> :> ,
> ,
> .
2.> :> ,
> ,
3.> :> ,
> ,
> .
4.> :> ,
> ,
> .
5.> :> ,
> ,
> .
Вопрос 2. Рассмотрим схему> :> ,
> ,
> .
Какая из схем описывает> ?
1.> ,
> ,
> .
2.> ,
> ,
> .
3.> ,
> ,
> .
4.> ,
> ,
> .
5.> ,
> ,
> .
Вопрос 3. Что такое> ?
1. Мощность множества> .
2. Множество непустых слов в алфавите> с длиной> .
3. Множество непустых слов в алфавите> с длиной не превосходящей> .
4. Отображение из множества> в множество> .
5. Схема кодирования> элементов множества> .
Вопрос 4. Рассмотрим схему> :> ,
. . . . . .
> .
Что обозначено буквой> в формулировке теоремы Маркова?
1. Длина слова> .
2. Длина слова> .
3.> .
4. Множество слов длины> .
5. Множество слов длины не более> .
Вопрос 5. Что называется неприводимым словом?
1. Слово, которое декодируется однозначно.
2. Слово, которое декодируется неоднозначно.
3. Слово> , если оно принадлежит множеству> некоторой схемы алфавитного кодирования.
4. Слово, не поддающееся декодированию (расшифровке).
5. Слово, допускающее не менее двух расшифровок, если оно не содержит внутри себя слов (меньшей длины), допускающих более одной расшифровки.
Задание 21
Изучить п. 3 части 3. Выписать в конспект формулировки теорем и следствий.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Рассмотрим схему алфавитного кодирования> , обладающую свойством префикса:
>
для которой> при> и количество символов алфавитаbравно двум. Какому неравенству удовлетворяет> ?
1.>
2.>
3.>
4.>
5.> .
Вопрос 2. Пусть задано алфавитное кодирование со схемой> :
>
причем число букв в алфавитеbравноq, и величиной> обозначена длина элементарного кодаBi> Какому условию подчиняются величиныqи> при> , если> обладает свойством взаимной однозначности?
1.>
2.>
3. Для любыхiиjотвечающих условиям> выполняется>
4.>
5.> .
Вопрос 3. Рассмотрим набор чисел> Какому условию должны удовлетворять эти числа для того, чтобы существовало алфавитное кодирование> со свойством префикса такое, что> - длины элементарных кодов> в алфавитеb, состоящем изqбукв?
1.>
2.>
3.>
4.>
5.> .
Вопрос 4. Что можно сказать об алфавитном кодировании, если длины его элементарных кодов над алфавитом из двух символов представлены множеством {3, 3, 3, 3, 3, 2}?
1. Кодирование является однородным
2. Кодирование является префиксным
3. Кодирование является взаимно однозначным
4. Кодирование не является взаимно однозначным
5.r - q= 2.
Вопрос 5. Пусть задан алфавит> и известно, что для некоторого алфавита> невозможно построить алфавитное взаимно однозначное кодирование с длинами элементарных кодов
>
Что можно утверждать относительно числа буквqв алфавитеb.
1.>
2.>
3.>
4.>
5.> .
Задание 22
Изучить п. 4 части 3. Выписать в конспект формулировки лемм и теорем. Выполнить практическое задание N 9 из приложения.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Какие коды называют кодами Хафмана?
1. Коды, задаваемые схемами равномерного кодирования
2. Коды, для которых>
3. Коды, для которых>
4. Коды, для которых>
5. Коды, задаваемые схемами, обладающими свойством префикса.
Вопрос 2. Что можно сказать о кодовом дереве для кода Хафмана?
1. Это дерево всегда является бинарным
2. Вероятности, приписанные концевым вершинам нижних ярусов не превышают вероятностей, приписанных концевым вершинам верхних ярусов (более близких к корню)
3. Все концевые вершины этого дерева являются насыщенными
4. Оно не может быть насыщенным
5. Оно имеет листья только на одном ярусе
Вопрос 3. Какой код называется приведенным?
1. Код минимальной избыточности с насыщенным кодовым деревом, у которого концевым вершинам пучка ребер, исходящих из исключительной вершины приписаны вероятности> при соблюдении условия>
2. Код минимальной избыточности с насыщенным кодовым деревом, у которого концевым вершинам пучка ребер, исходящих из исключительной вершины приписаны вероятности> причем>
3. Код минимальной избыточности с насыщенным кодовым деревом, у которого при наличии исключительной вершины концевым вершинам, соединенным ребрами с исключительной вершиной, приписаны вероятности> > , если же исключительная вершина отсутствует, то такой набор вероятностей при> должен быть приписан концевым вершинам произвольного пучка ребер нижнего яруса
4. Код с минимальной избыточностью, кодовое дерево которого является насыщенным
5. Код с минимальной избыточностью, кодовое дерево которого является насыщенным и не имеет исключительной вершины.
Вопрос 4. Пусть> . Какой будет длина самого длинного из элементарных кодов> , если построить приведенный код? (Постройте насыщенное кодовое дерево)
1. 2
2. 3
3. 4
4. 5
5. 6
Вопрос 5. Пусть> . Сколько концевых вершин будет соединено ребрами с исключительной вершиной, если построить насыщенное дерево?
1. 2
2. 3
3. 4
4. 5
5. 6
Задание 23
Изучить п. 5 части 3. Выписать в конспект определения, формулировки теорем и следствия.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Допустим, что при передаче сообщения> используется самокорректирующийся код, позволяющий исправить ошибку в одном символе. Какому условию должна подчиняться величинаl, равная длине кода> ?
1.>
2.>
3.>
4.>
5.>
Вопрос 2. Рассмотрим код Хэмминга> . Какие> являются контрольными?
1.>
2.>
3.>
4.>
5.>
Вопрос 3. Пусть из канала связи, искажающего не более одного символа в сообщении, получен код Хэмминга: 011010111. Какой символ искажен?
1. Первый
2. Второй
3. Третий
4. Четвертый
5. Пятый
Вопрос 4. Что обозначает> ?
1. Множество элементарных кодов>
2. Множество слов вида> , содержащих один искаженный символ
3. Коды Хэмминга длиныl
4. Самокорректирующийся код, выявляющийlошибок
5. Алфавит изlсимволов.
Вопрос 5. Пусть для любых точек> и> множестваH, принадлежащего единомуl-мерному кубу выполняется неравенство:> Что можно утверждать относительно множестваH?
1. МножествоHнаходится внутри шара радиусар
2. МножествоHпринадлежит сфере радиуса>
3. Существуют три точки> множестваH, для которых выполняется неравенство>
4. МножествоHсодержит четное число точек
5. МножествоHпринадлежит самокорректирующемуся коду коду относительно источника помех, вызывающего не болеерошибок.
Задание 24
Изучить п.п. 1, 2, 3 части 4. Выписать в конспект определения и теоремы.
Выбрать правильный ответ к вопросу и отметить его в карточке ответов.
Вопрос 1. Какое из перечисленных свойств не является характерной чертой алгоритма?
1. Массовость
2. Транзитивность
3. Элементарность шагов
4. Результативность
5. Детерминированность
Вопрос 2. Какое из перечисленных ниже множеств разрешимо?
1. Множество квадратов натуральных чисел
2. Множество четных чисел
3. Множество слов русского языка
4. Множество всевозможных сочетаний букв русского алфавита
5. Множество отрицательных целых чисел
Вопрос 3. Пусть множестваMиL- эффективно перечислимы. Какое из перечисленных ниже множеств может не быть эффективно перечислимыми?
1.>
2. CL ( дополнение множества L)
3.>
4. Пустое множество (множество не содержащее элементов)
5. Все перечисленные множества эффективно перечислимы
Вопрос 4. Какая из перечисленных ниже функций не является общерекурсивной?
1.>
2.y+5x
3.>
4.>
5.>
Вопрос 5. Какая из перечисленных ниже функций не является частично рекурсивной?
1.>
2.>
3.>
4.>
5.>
Задание 25
Изучить п. 4 части 4. Выписать в конспект определения и описание порядка работы машины Тьюринга. Выполнить практическое задание N 10 из приложения
Выбрать правильный ответ к вопросу и отметить его в карточке ответов
Вопрос 1. Как называется конечное множество символов, которые по одному считывает (обозревает) или записывает управляющая головка машины Тьюринга?
1. Внутренний алфавит
2. Цифры
3. Множество состояний
4. Результирующая информация
5. Внешний алфавит
Вопрос 2. В каком случае говорят, что машина Тьюринга неприменима к начальной информации> ?
1. Если в результате работы машины Тьюринга после ее остановки на ленте сохраняется информация>
2. Если алфавит, использованный при записи информации> отличается от внутреннего алфавита машины Тьюринга
3. Если, начав обрабатывать информацию> машина Тьюринга никогда не остановится
4. Если алфавит, использованный при записи информации> отличается от внешнего алфавита машины Тьюринга
5. Если машина Тьюринга переходит в стоп-состояние (останавливается), начав обрабатывать информацию>
Вопрос 3. Пусть имеется внешний алфавит> , внутренний алфавит> . Какая из записей может быть командой машины Тьюринга с такими алфавитами?
1.>
2.>
3.>
4.>
5.>
Вопрос 4. "Всякий алгоритм может быть задан тьюринговой функциональной схемой и реализован в соответствующей машине Тьюринга." Как можно охарактеризовать это утверждение?
1. Это утверждение - гипотеза (предположение)
2. Это - аксиома
3. Это - теорема
4. Это ложное утверждение
5. Это - бессмысленный набор слов
Вопрос 5. Задана функция> . Какая из перечисленных программ машины Тьюринга ее реализует?
1.
| > |
> 2.
> 3.
4.
| > |
5. Здесь нет такой программы