Замкнут класс примитивно рекурсивных множеств относительно пересечения

10 Является ли формула ИП: общезначимой.

Постройте машину Тьюринга, которая обращает слово.

Являются ли примитивно рекурсивные множества рекурсивно перечислимыми.

Замкнут ли класс рекурсивно перечислимых множеств относительно дополнения.

14 Является ли формула общезначимой ИП.

Существует ли рекурсивная, универсальная функция для класса рекурсивных функций

16. Представьте в виде обобщенной СДНФ в (формула в системе {0,1,2, функцию {000111111}.

17. Найдите существенные переменные функций :

Контрольная работа 4

Студенты А,Б,В,Г,Д выбрали спецкурсы а, б, в ,г, д . Найдите минимальное число пар в корректном расписании. На каждый спецкурс отводится только одно занятие. Поэтому, чтобы студенты посетили все выбранные спецкурсы, на одной паре не может быть поставлены спецкурсы выбранные одним и темже студентом.

а /А/; б /Б,В/; в/Г/; г/Б,Г/; д/А,В/

2.Какие из графов планарны, какие непланарны.

Снегоуборочная машина должна убрать снег с дорог в микрорайоне схема которого на рисунке а) в предыдущей задаче. Найдите кратчайший замкнутый маршрут. Длины всех участков дорог равны.

Верно ли, что в каждом ориентированном графе без тупиков существует цикл. Тупик- вершина, из которой нет выходящих ребер.

5. Покажите, что во всяком дереве с n >=2 вершинами не менее двух вершин висячие.

Контрольная работа 5:

1. На ж/д. станции имеется т светофоров. Сколько может быть дано раз­личных сигналов, если каждый светофор имеет три состояния: красный, желтый и зеленый?

2. Сколько существует матриц размера т, п, элементы которых прини­мают значения 0 или 1 ?

3. Какое число позиций из трех различных фигур существует на шах­матной доске 8х8?

4. Имеется шесть претендентов на три вакантные должности. Какое чи­сло возможных назначений имеется?

Имеется семь различных автобусов. Каким числом способов можно выбрать три из них на три различных маршрута?

6. Десять человек голосуют за трех кандидатов. Можно голосовать толь­ко за одного кандидата. Какое число возможных результатов выборов?

Подкидывают пять различных игральных костей. Какое возможное число исходов?

Какое число расстановок восьми одинаковых ладей имеется, чтобы никакая пара ладей не угрожала друг другу?

Какое число способов составить расписание из пяти предметов на один день имеется?

Найти число различных конъюнкций на множестве n переменных.

Найти число двоичных наборов длины n с k единицами.

12. Имеется колода из 36 карт, выбирают 3 карты. Какое число возмож­ных выборов имеется?

Имеется 10 предметов. Каким числом способов можно составить набор из трех предметов?