Дискретная математика-2.
для специальностей 080801, 230105 (Гос. 1995)
Математическая логика и теория алгоритмов
для специальности 230105 (Гос. 2000)
Сафьянова Е.Н.
Томск-2006

Формальные теории.

№ 1
Что представляет собой формальная теория?
• Множество всех формул некоторого формального языка с выделенным подмножеством истинных формул.

№ 2
В чем состоят особенности аксиоматической теории?
• Это формальная теория, в которой выделено подмножество истинных формул и указано конечное множество отношений между формулами.

№ 3
Что называется теоремой формальной теории?
• Такая формула А теории, что существует доказательство, в котором последней формулой является формула А.

№ 4
Что называется интерпретацией формальной теории в содержательную?
• Установление соответствия между формулами формальной теории и утверждениями содержательной теории.

№ 5
Какая интерпретация называется правильной?
• Такая, что каждой теореме формальной теории соответствует истинное утверждение содержательной теории.

№ 6
Какая интерпретация называется адекватной?
• Такая, что существует взаимно однозначное соответствие между теоремами формальной теории и истинными утверждениями содержательной теории.

№ 7
Что является признаком непротиворечивости формальной теории?
• Наличие в ней формул, не являющихся истинными.

№ 8
Какой смысл имеет понятие “исчисление” при построении формальных теорий?
• Дедуктивная система, в которой указываются исходные объекты и правила построения новых объектов из исходных и уже построенных.

№ 9
Какими свойствами обладает исчисление высказываний?
• Непротиворечивость, полнота и адекватность интерпретации в алгебру высказываний.

№ 10
Какими свойствами обладает исчисление предикатов?
• Непротиворечивость и адекватность интерпретации в логику предикатов.

Теория рекурсивных функций.

№ 11
Каковы основные свойства алгоритма в его интуитивном определении?
• Дискретность, определенность, результативность, массовость.

№ 12
В связи с чем возникла необходимость уточнения понятия алгоритма?
• Интуитивное понятие не позволяло доказать отсутствие алгоритма для некоторого класса задач.

№ 13
Какие функции называют вычислимыми?
• Числовые функции, значения которых можно вычислить с помощью некоторого алгоритма.

№ 14
Какие функции называются примитивно рекурсивными?
• Функции, полученные на основе простейших и других примитивно рекурсивных функций с помощью операторов подстановки и примитивной рекурсии.

№ 15
Какие функции называются частично рекурсивными?
• Функции, полученные на основе простейших и других примитивно рекурсивных функций с помощью операторов подстановки, примитивной рекурсии и минимизации.

№ 16
Как называются алгоритмы, являющиеся законами задания рекурсивных функций?
• Сопутствующие алгоритмы.

№ 17
Какой из алгоритмов является сопутствующим для функции s(x)=x´=x+1 ?
• Значением функции считать число, непосредственно следующее за числом, являющимся значением аргумента.

№ 18
Какой из алгоритмов является сопутствующим для функции С_aⁿ ( x₁,...,x_n)=a?
• Любой совокупности значений аргументов данной функции ставится в соответствие ее значение a.

№ 19
Какой из алгоритмов является сопутствующим для функции I_mⁿ( x₁,...,x_n)=x_m (1≤m≤n, n=1,2,…)?
• Значением функции считать значение m-го (считая в функциональной записи слева-направо) независимого переменного.

№ 20
Какой из алгоритмов является сопутствующим для оператора подстановки?
• Значения функций f1,...,fn принять за значения аргументов функции и вычислить ее значение.

№ 21
Какой из алгоритмов является сопутствующим для оператора примитивной рекурсии?
• Значением получаемой функции для нулевого значения главного дополнительного аргумента считать значение исходной функции n-го аргумента. Значением определяемой функции для каждого последующего значения главного аргумента считать значение второй из заданных функций при предыдущем значении главного аргумента и при значении вспомогательного аргумента, совпадающем с предыдущим значением определяемой функции.

№ 22
Какой из алгоритмов является сопутствующим для оператора минимизации?
• Придавать вспомогательному аргументу последовательные значения, начиная с нуля, до тех пор, пока не окажется, что функция f стала (в первый раз) равной нулю. Полученное значение вспомогательного аргумента принять за значение определяемой функции, соответствующее тем значениям основных аргументов, при которых осуществлялся описанный процесс.

№ 23
Как называется функция, задаваемая выражением С_aⁿ( x₁,...,x_n)=a?
• Функция-константа.

№ 24
Как называется функция, задаваемая выражением I_mⁿ( x₁,...,x_n)=x_m (1≤m≤n, n=1,2,…)?
• Функция тождества.

№ 25
Как называется функция, задаваемая выражением s(x)=x´=x+1?
• Функция следования.

№ 26
Как называется преобразование, с помощью которого получена функция g( x₁,...,x_m)=f(f₁(x₁,...,x_m),...,f_n( x₁,...,x_m))?
• Оператором подстановки.

№ 27
Как называется преобразование, с помощью которого получена функция f(x₁,...,x_n,0)=g(x₁,...,x_n), f(x₁,...,x_n,y+1)=h(x₁,...,x_n, y, f(x₁,...,x_n,y))?
• Оператором примитивной рекурсии.

№ 28
Как называется преобразование, с помощью которого получена функция mi_y(f(x₁,...,x_n-1,y)=x_n)?
• Оператором минимизации.

№ 29
Чему равно значение выражения I₂²(C₂¹(0),s(s(I₃⁴(1,6,C₁⁴(0,1,2,6),I₁²(8, 1)))))?
• 3.

№ 30
Чему равно значение выражения s(I₂³(1,I₂⁵(0,6,8,C₁²(1,8),C₂⁸(6,3,7,C₁¹(0),9,11,2,I₁²(3,7)))))?
• 7.

№ 31
Чему равно значение выражения s(s(s(s(I₁³(s(s(C_a²(1,2))),C_b²(x₁,s(s(s(x₂)))),I₁³(1,2,3))))))?
• a+6.

№ 32
Чему равна функция f, возникающая примитивной рекурсией из постоянной g=4 и функции h=6x+y.
• f(x+1)=3x(x+1)+4.

№ 33
Чему равна функция f, возникающая примитивной рекурсией из постоянной g=7 и функции h=8x+y.
• f(x+1)=4x(x+1)+7.

№ 34
С помощью какого оператора может быть получена функция f(x,y)=x-y?
• Оператора минимизации.

№ 35
С помощью какого оператора может быть получена функция f(x,y)=x+y?
• Оператора примитивной рекурсии.

№ 36
С помощью какого оператора может быть получена функция f(x,y)=xy?
• Оператора примитивной рекурсии.

№ 37
С помощью какого оператора может быть получена функция f(x,y)=x/y?
• Оператора минимизации.

№ 38
С помощью какого оператора может быть получена функция f(x,y)=log_xy?
• Оператора минимизации.

№ 39
С помощью какого оператора может быть получена функция f(x,y)=x^y?
• Оператора примитивной рекурсии.

№ 40
К какому классу функций относится функция f(x,y)=x-y?
• Частично рекурсивных.

№ 41
К какому классу функций относится функция f(x,y)=x+y?
• Примитивно рекурсивных.

№ 42
К какому классу функций относится функция f(x,y)=xy?
• Примитивно рекурсивных.

№ 43
К какому классу функций относится функция f(x,y)=log_xy?
• Частично рекурсивных.

№ 44
К какому классу функций относится функция f(x,y)=x/y?
• Частично рекурсивных.

№ 45
К какому классу функций относится функция f(x,y)=x^y?
• Примитивно рекурсивных.

№ 46
В каком случае функция f называется частично рекурсивной?
• Если она является одной из простейших функций или может быть получена из простейших с помощью конечного числа применений операторов подстановки, примитивной рекурсии и минимизации.

№ 47
В каком случае функция f называется примитивно рекурсивной?
• Если она является одной из простейших функций или может быть получена из простейших с помощью конечного числа применений операторов подстановки и примитивной рекурсии.

№ 48
В каком случае функция f называется общерекурсивной?
• Если она является одной из простейших функций или может быть получена из простейших с помощью конечного числа применений операторов подстановки, примитивной рекурсии и слабой минимизации.

№ 49
С каким классом функций совпадает класс алгоритмически вычислимых частичных числовых функций?
• С классом частично рекурсивных функций.

№ 50
Следующее утверждение справедливо?
• Все примитивно рекурсивные функции являются всюду определенными, но не все частично рекурсивные функции всюду определены.

Машина Тьюринга. Нормальные алгорифмы Маркова.

№ 51
Что представляет собой машина Тьюринга?
• Воображаемая машина, позволяющая производить вычисления в соответствии с некоторым алгоритмом.

№ 52
Что записывается в каждой ячейке внешней памяти машины Тьюринга?
• Один из символов внешнего алфавита.

№ 53
Что называется конфигурацией машины Тьюринга?
• Совокупность, образованная последовательностью символов состояний ячеек ленты, символом внутреннего алфавита и номером воспринимаемой ячейки.

№ 54
Что называется программой машины Тьюринга?
• Совокупность записей вида q_ia_ik→q_la_pkR, где R – одна из букв Л, П, С (влево, вправо, сохранение положения головки), q_i символ внутреннего алфавита, a_ik, a_pk – символы, записанные в обозреваемой ячейке.

№ 55
Какое преобразование машинных слов выполняет программа машины Тьюринга, стирающей данный массив единиц?
• 01^x0^y1^z-1q₁10⇒01^x-1q₀0^y+z+1.

№ 56
Какое преобразование машинных слов выполняет программа машины Тьюринга, заполняющей единицами промежуток до следующего справа массива единиц (за исключением одного нуля)?
• 01^xq₁10^y+11^z⇒01^x+yq₀101^z0.

№ 57
Какое преобразование машинных слов выполняет программа машины Тьюринга, сдвигающей головку влево на предыдущий массив единиц?
• 01^x+10^y1^zq₁1^w0⇒01^xq₀10^y1^z+w0.

№ 58
Какое преобразование машинных слов выполняет программа машины Тьюринга, стирающей предыдущий массив единиц?
• 01^x0q₁1^z-1q₁10⇒0^x+yq₀01^z0.

№ 59
Какое преобразование машинных слов выполняет программа машины Тьюринга, уменьшающей данное число на два?
• 01^xq₁1q₁0⇒01^x+y-3q₀1000.

№ 60
Какую задачу решает программа машины Тьюринга, выполняющая следующее преобразование машинных слов: 01^x0^y1^z-1q₁10⇒0^x+yq₀01^z0
• Стирает предыдущий массив единиц.

№ 61
Какую задачу решает программа машины Тьюринга, выполняющая следующее преобразование машинных слов: 01^x0^y1^z-1q₁10⇒01^x-1q₀10^y+z+1
• Стирает данный массив единиц.

№ 62
Какую задачу решает программа машины Тьюринга, выполняющая следующее преобразование машинных слов: 01^xq₁1^y0⇒01^x+y-3q₀1000
• Уменьшает данное число на два.

№ 63
Какую задачу решает программа машины Тьюринга, выполняющая следующее преобразование машинных слов: 01^x+10^y1^zq₁1^w0⇒01^xq₀10^y1^z+w0
• Сдвигает головку влево на предыдущий массив единиц.

№ 64
Какую задачу решает программа машины Тьюринга, выполняющая следующее преобразование машинных слов: 01^xq₁10^y+11^z⇒01^x+yq₀101^z0
• Заполняет единицами промежуток до следующего справа массива единиц (за исключением одного нуля).

№ 65
Сколько команд содержит программа машины Тьюринга, стирающей данный массив единиц?
• 4.

№ 66
Сколько команд содержит программа машины Тьюринга, заполняющей единицами промежуток до следующего справа массива единиц (за исключением одного нуля)?
• 5.

№ 67
Сколько команд содержит программа машины Тьюринга, сдвигающей головку влево на предыдущий массив единиц?
• 4.

№ 68
Сколько команд содержит программа машины Тьюринга, стирающей предыдущий массив единиц?
• 8.

№ 69
Сколько команд содержит программа машины Тьюринга, уменьшающей данное число на два?
• 4.

№ 70
Сколько внутренних состояний содержит программа машины Тьюринга, стирающей данный массив единиц?
• 3.

№ 71
Сколько внутренних состояний содержит программа машины Тьюринга, заполняющей единицами промежуток до следующего справа массива единиц (за исключением одного нуля)?
• 4.

№ 72
Сколько внутренних состояний содержит программа машины Тьюринга, сдвигающей головку влево на предыдущий массив единиц?
• 3.

№ 73
Сколько внутренних состояний содержит программа машины Тьюринга, стирающей предыдущий массив единиц?
• 5.

№ 74
Сколько внутренних состояний содержит программа машины Тьюринга, уменьшающей данное число на два?
• 4.

№ 75
С каким классом функций совпадает класс функций, вычислимых на машине Тьюринга?
• С классом частично рекурсивных функций.

№ 76
В каком случае говорят, что головка машины Тьюринга воспринимает систему чисел в стандартном положении?
• Числа разделены одной пустой ячейкой и головка воспринимает самую правую заполненную ячейку.

№ 77
Что представляют собой исходные данные и результаты в нормальных алгорифмах Маркова?
• Строки символов в некотором заданном алфавите.

№ 78
Какая операция называется Марковской подстановкой?
• Замена в некотором слове R первого вхождения слова P словом Q.

№ 79
Что представляет собой запись нормального алгорифма Маркова?
• Столбец формул, левые и правые части которых являются словами в некотором заданном алфавите.

№ 80
Как происходит выполнение нормального алгорифма Маркова?
• Двигаясь по столбцу формул, ищут первую формулу, левая часть которой входит в преобразуемое слово и выполняют соответствующую подстановку.

Комбинаторика.

№ 81
К какому классу задач комбинаторного анализа можно отнести задачу отыскания кратчайшего пути для почтальона, обязанного обслуживать заданное число населенных пунктов, если расстояние между каждой парой пунктов известно?
• Задачи отыскания наилучшего в некотором смысле решения (оптимизационные задачи).

№ 82
К какому классу задач комбинаторного анализа можно отнести следующую задачу: Из колоды, содержащей 52 карты, вынули 10 карт. В скольких случаях окажется, что среди вынутых карт: а) не менее двух тузов; б) ровно два туза?
• Задачи о количестве решений (перечислительные задачи).

№ 83
К какому классу задач комбинаторного анализа можно отнести задачу о беспорядках?
• Задачи о количестве решений (перечислительные задачи).

№ 84
К какому классу задач комбинаторного анализа можно отнести задачу о назначениях?
• Задачи отыскания наилучшего в некотором смысле решения (оптимизационные задачи).

№ 85
Что представляет собой множество возможных решений для задачи определения очередности выполнения заданий?
• Множество всевозможных перестановок из заданного множества I_N, где I_N – множество номеров (заданий, деталей, исполнителей).

№ 86
Что представляет собой множество возможных решений для задачи определения порядка обработки деталей?
• Множество всевозможных перестановок из заданного множества I_N, где I_N – множество номеров (заданий, деталей, исполнителей).

№ 87
Что представляет собой множество возможных решений для задачи распределения заданий?
• Множество всевозможных разбиений заданного множества I_N, где I_N – множество номеров (заданий, деталей, исполнителей).

№ 88
Что является целевой функцией для задачи определения порядка обработки деталей?
• Время обработки последней детали на последнем станке.

№ 89
Что является целевой функцией для задачи определения очередности выполнения заданий?
• Величина суммарного штрафа за нарушение директивных сроков.

№ 90
Что является целевой функцией для задачи распределения заданий?
• Суммарные затраты (например, по времени) на выполнение всех заданий.

№ 91
Как называются r-выборки из некоторого n-множества, если порядок расположения элементов в них неважен, и каждый элемент встречается только один раз?
• r-сочетаниями.

№ 92
Как называются r-выборки из некоторого n-множества, если порядок расположения элементов в них неважен, и каждый элемент может встречаться более одного раза?
• r-сочетаниями с повторениями.

№ 93
Как называются r-выборки из некоторого n-множества, если порядок расположения элементов в них важен, и каждый элемент встречается только один раз?
• r-перестановками.

№ 94
Как называются r-выборки из некоторого n-множества, если порядок расположения элементов в них важен, и каждый элемент может встречаться более одного раза?
• r-перестановками с повторениями.

№ 95
Какое из логических правил теории множеств (или их сочетаний) используется при решении следующей задачи: В городе N автобусные номера состоят из трех букв и четырех цифр. Сколько может быть автобусов с различными номерами, если используются 30 букв русского алфавита и 10 арабских цифр?
• Правило произведения.

№ 96
Какое из логических правил теории множеств (или их сочетаний) используется при решении следующей задачи: Каждый студент группы изучает только один иностранный язык: 9 человек – английский, 8 – французский, 6 – немецкий. Сколько студентов в группе?
• Правило суммы.

№ 97
Какое из логических правил теории множеств (или их сочетаний) используется при решении следующей задачи: Имеется 5 книг на английском языке, 7 – на немецком, 10 – на французском. Все книги различны. Сколькими способами можно выбрать две разноязычные книги?
• Правило суммы и правило произведения.

№ 98
В n -ичной системе счисления используется n цифр. Сколько в ней натуральных чисел, записываемых k знаками?
• (n-1)n^k-1.

№ 99
Сколькими способами можно посадить за круглый стол n мужчин и n женщин так, чтобы никакие два лица одного пола не сидели рядом?
• 2(n!²).

№ 100
Сколькими способами можно разместить n одинаковых шаров по m различным урнам при условии, что пустых урн нет?
• C (n-1,m-1).

№ 101
Одновременно подбрасывают три кубика, имеющих 6, 8 и 10 граней соответственно. Сколькими различными способами они могут упасть, если известно, что, по крайней мере, два кубика упали на цифру 1?
• 22.

№ 102
Какая из формул используется для вычисления числа перестановок без повторений из n элементов по r.
• n(n-1)...(n-r+1).

№ 103
Какая из формул используется для вычисления числа перестановок с повторениями из n элементов по r.
• n^r.

№ 104
Какая из формул используется для вычисления числа сочетаний без повторений из n элементов по r.
• n! / (r!(n-r)!).

№ 105
Какая из формул используется для вычисления числа сочетаний с повторениями из n элементов по r.
• (n+r-1)! / (r!(n-r!)).