дипломы,диссертации,курсовые,контрольные,рефераты,отчеты на заказ

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

Указаны только правильные ответы, другие варианты можно узнать скачав файл из архива → Дис_мат2.АСУ.

Тема: 1. Формальные теории
дипломы,курсовые,рефераты,контрольные,диссертации,отчеты на заказ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

№ 24
Как называется функция, задаваемая выражением Imn( x1,...,xn)=xm (1≤m≤n, n=1,2,…)?
• Функция тождества.

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

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

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

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

№ 29
Чему равно значение выражения I22(C21(0),s(s(I34(1,6,C14(0,1,2,6),I12(8, 1)))))?
• 3.

№ 30
Чему равно значение выражения s(I23(1,I25(0,6,8,C12(1,8),C28(6,3,7,C11(0),9,11,2,I12(3,7)))))?
• 7.

№ 31
Чему равно значение выражения s(s(s(s(I13(s(s(Ca2(1,2))),Cb2(x1,s(s(s(x2)))),I13(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)=logxy?
• Оператора минимизации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

№ 55
Какое преобразование машинных слов выполняет программа машины Тьюринга, стирающей данный массив единиц?
• 01x0y1z-1q110⇒01x-1q00y+z+1.

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

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

№ 58
Какое преобразование машинных слов выполняет программа машины Тьюринга, стирающей предыдущий массив единиц?
• 01x0q11z-1q110⇒0x+yq001z0.

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

№ 60
Какую задачу решает программа машины Тьюринга, выполняющая следующее преобразование машинных слов: 01x0y1z-1q110⇒0x+yq001z0
• Стирает предыдущий массив единиц.

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

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

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

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

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

Тема: 4. Комбинаторика

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

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

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

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

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

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

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

№ 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)nk-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.
• nr.

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

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


на главную база по специальностям база по дисциплинам статьи