Учебно-методический комплекс по дисциплине 230100 Теория алгоритмов Направление подготовки

Вид материала

Учебно-методический комплекс

Содержание X. список рекомендуемой для изучения литературы.

Подобный материал:

• Рабочая учебная программа по дисциплине «Математическая логика и теория алгоритмов», 69.99kb.
• Учебно-методический комплекс по дисциплине «Ботаника» Направление подготовки, 1843.23kb.
• Учебно-методический комплекс дисциплины б дв1 Теория систем и системный анализ Направление, 568.62kb.
• Рабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов шифр, 316.78kb.
• Учебно-методический комплекс по дисциплине опд. Ф. 04 Теория и методика обучения литературе, 2205.11kb.
• Учебно-методический комплекс умк учебно-методический комплекс теория и методика воспитания, 1435.61kb.
• Учебно-методический комплекс по дисциплине математическая логика и теория алгоритмов, 144.09kb.
• Учебно-методический комплекс по опд. Ф. 15 «Конституционное право зарубежных стран», 1206.51kb.
• Учебно-методический комплекс по дисциплине Теория систем Направление подготовки, 684.83kb.
• Учебно-методический комплекс дисциплины «Микроэкономика» Направление подготовки, 1978.69kb.

	Свойство алгоритма записываться в виде упорядоченной совокупности отделенных друг от друга предписаний (директив): понятность; 2) определенность; 3) дискретность; 4) массовость.
	Свойство алгоритма записываться в виде только тех команд, которые находятся в Системе Команд Исполнителя, называется: 1) понятность; 2)определенность; 3) дискретность; 4) результативность.
	Свойство алгоритма записываться только директивами однозначно и одинаково интерпретируемыми разными исполнителями: 1) детерминированность; 2) результативность; 3) дискретность; 4) понятность.
	Свойство алгоритма, что при точном исполнении всех предписаний процесс должен прекратиться за конечное число шагов с определенным ответом на поставленную задачу: 1) детерминированность; 2) результативность; 3) дискретность; 4) понятность.
	Свойство алгоритма обеспечения решения не одной задачи, а целого класса задач этого типа; 1) понятность; 2) детерминированность; 3) дискретность; 4) массовость.
	Что называют служебными словами в алгоритмическом языке: слова, употребляемые для записи команд, входящих в СКИ; слова, смысл и способ употребления которых задан раз и навсегда; вспомогательные алгоритмы, которые используются в составе других алгоритмов; константы с постоянным значением?
	Рекурсия в алгоритме будет прямой, когда: рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к которому в данном алгоритме имеется обращение; порядок следования команд определяется в зависимости от результатов проверки некоторых условий; команда обращения алгоритма к самому себе находится в самом алгоритме; один вызов алгоритма прямо следует за другим.
	Рекурсия в алгоритме будет косвенной, когда: рекурсивный вызов данного алгоритма происходит из вспомогательного алгоритма, к которому в данном алгоритме имеется обращение; порядок следования команд определяется в зависимости от результатов проверки некоторых условий; команда обращения алгоритма к самому себе находится в самом алгоритме; один вызов алгоритма прямо следует за другим.
	Команда машины Поста имеет структуру п Km, где: n — действие, выполняемое головкой; К — номер следующей команды, подлежащей выполнению; m - порядковый номер команды; n - порядковый номер команды; К — действие, выполняемое головкой; m — номер следующей команды, подлежащей выполнению; n — порядковый номер команды; К - номер следующей команды, подлежащей выполнению; m — действие, выполняемое головкой; n — порядковый номер команды; К— действие, выполняемое головкой; m — номер клетки, с которой данную команду надо произвести.
	Сколько существует команд у машины Поста: 1) 2; 2) 4; 3) 6; 4) 8?
	В машине Поста останов будет результативным: при выполнении недопустимой команды; если машина не останавливается никогда; если результат выполнения программы такой, какой и ожидался; по команде «Стоп».
	В машине Поста некорректным алгоритм будет в следующем случае: при выполнении недопустимой команды; результат выполнения программы такой, какой и ожидался; машина не останавливается никогда; по команде «Стоп».
	В машине Тьюринга рабочий алфавит: 1) А = {a40 0, b40 1, c40 2, … , w40 t}; 2) А = {a40 0, a40 1, a40 2, … , a40 t}; 3) А = {a40 0, a41 0, a42 0, … , a4t 0}; 4) А = {a10 0, a20 0, a30 0, … , a90 0}
	В машине Тьюринга состояниями являются: 1){a40 0, a40 1,a402, …,a40 t}; 2) {q41, q42, q43, …, q4s}; 3){q41, q42, q43, …, q4s, a40 0, a40 1, a40 2,…,a40 t}; 4){q40, q41, q42, …, q4s}.
	В машине Тьюринга предписание L для лентопротяжного механизма означает: 1) переместить ленту вправо; 2) переместить ленту влево; 3) остановить машину; 4) занести в ячейку символ.
	В машине Тьюринга предписание R для лентопротяжного механизма означает: 1) переместить ленту вправо; 2) переместить ленту влево; 3) остановить машину; 4) занести в ячейку символ.
	В машине Тьюринга предписание S для лентопротяжного механизма означает: 1) переместить ленту вправо; 2) переместить ленту влево; 3) остановить машину; 4) занести в ячейку символ.
	В алгоритме Маркова ассоциативным исчислением называется: совокупность всех слов в данном алфавите; совокупность всех допустимых систем подстановок; совокупность всех слов в данном алфавите вместе с допустимой системой подстановок; когда все слова в алфавите являются смежными.
	В ассоциативном счислении два слова называются смежными: если одно из них может быть преобразовано в другое применением подстановок; если одно из них может быть преобразовано в другое однократным применением допустимой подстановки; когда существует цепочка от одного слова к другому и обратно; когда они дедуктивны.
	В алгоритме Маркова дана цепочка Р P1 Р2 ... Рк, Если слова P1 , Р2 ,..., Рк-1, смежные, то цепочка называется: ассоциативной; 2) эквивалентной; 3) индуктивной; 4) дедуктивной.
	В алгоритме Маркова дана цепочка Р P1 Р2 ... Рк,. Если слова P1 , Р2 ,..., Рк-1, смежные и цепочка существует и в обратную сторону, то слова Р и Рк называют: ассоциативными; 2) эквивалентными; 3) индуктивными; 4) дедуктивными.
	В алгоритмах Маркова дана система подстановок в алфавите А = {а, b, с}: abc — с; ba — cb; са — аb. Преобразуйте с помощью этой системы слово bacaabc: 1) cbc; 2) ccbcbbc; 3) cbacba; 4) cbabc.
	В алгоритмах Маркова дана система подстановок в алфавите А = {а, b, с}: cb — abс; bac — ac; саb — b. Преобразуйте с помощью этой системы слово bcabacab: 1) ccb; 2) cab; 3) cbc; 4) bcaab.
	Способ композиции нормальных алгоритмов будет суперпозицией, если: выходное слово первого алгоритма является входным для второго; существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В; алгоритм D будет суперпозицией трех алгоритмов А В С, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p)=A(p), если С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка; существует алгоритм С, являющийся суперпозицией алгоритмов А и B такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
	Способ композиции нормальных алгоритмов будет объединением, если: выходное слово первого алгоритма является входным для второго; существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В; алгоритм D будет суперпозицией трех алгоритмов А В С, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = A(p), если С(р) = е, D(p) = В(р), если С(р) = е, где е — пустая строка; существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
	Способ композиции нормальных алгоритмов будет разветвлением, если: 1) выходное слово первого алгоритма является входным для второго; существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В; алгоритм D будет суперпозицией трех алгоритмов A B C, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) — В(р), если С(р) = е, где е — пустая строка; существует алгоритм С, являющийся суперпозицией алгоритмов А и В такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.
	Способ композиции нормальных алгоритмов будет итерацией, если: выходное слово первого алгоритма является входным для второго; существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В; алгоритм D будет суперпозицией трех алгоритмов A B C, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) — В(р), если С(р) = е, где е — пустая строка; существует алгоритм С, являющийся суперпозицией алгоритмов А и В такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

X. СПИСОК РЕКОМЕНДУЕМОЙ ДЛЯ ИЗУЧЕНИЯ ЛИТЕРАТУРЫ.

Основная литература

	Брой М., Румпе Б. Введение в информатику: сборник задач. Структурированное собрание упражнений с образцами решений./Пер. с нем. – М.: Научный мир, Диалог-МИФИ, 2000 – 374с.
	Брой М. Информатика. Основополагающее введение. Ч.4./Пер. с нем. – М.: Диалог – МИФИ, 1998 – 224с.
	Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
	Зюзьков В.М., Шелупанов А.А. Математическая логика и теория алгоритмов. Учебное пособие для вузов. – 2-е изд. – М.: Горячая линия – Телеком, 2007. – 176с.
	Игошин В.И. Математическая логика и теория алгоритмов. – Саратов: Издательство Саратовского университета, 1991.
	Козлов К.П. Алгоритмы: Учеб. пособие. – Л., ЛГПИ, 1989. – 39с.
	Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – 4-е изд. – М.: ФИЗМАТЛИТ, 2001. – 256с.
	Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Курс лекций. Задачник-практикум и решения. Серия «Учебники для вузов. Специальная литература». – Спбю: Издательство «Лань», 1999. – 288с.
	Мальцев А.И. Алгоритмы и рекурсивные функции. – 2-е изд. – М.: Наука, 1986.
	Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – М.: Мир, 1972.
	Кейслер Г., Чен Ч. Теория моделей. - М.: Мир, 1977.
	Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – 2-е изд., перераб. и доп. – М.: Энергоатомиздат, 1988.-480с.
	Алферова З.А. Теория алгоритмов. – М.: Статистика, 1973.
	Манин Ю.И. Вычислимая и невычислимое, - М.: Сов. радио, 1980.
	Машины Тьюринга и вычислимые функции: Пер. с нем., - М.: МИР, 1972.
	Трахтенброт Б.А. Алгоритмы и вычислительные автоматы. – М.: Сов. радио, 1974.
	Успенский В.А. Машина Поста. – М.: Наука, 1988.
	Языки и автоматы. Сборник переводов./Под ред. Маслова А.К. - М.: Мир.
	Могилев А.В. и др. Практикум по информатике: Учеб. пособие для студ. всш. учеб. заведений/ А.В. Могилев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. – М.: Издательский центр «Академия», 2001. – 608с.
	Могилев А.В. и др. Информатика: Учеб. пособие для студ. всш. учеб. заведений/ А.В. Могилев, Н.И. Пак, Е.К. Хеннер; Под ред. Е.К. Хеннера. – М.: Издательский центр «Академия», 1999. – 608с.

Дополнительная литература

1. Бауэр Ф.Л., Гооз Г.. Информатика. В 2-х тт. М., “Мир”, 1990.
   
2. Вирт Н. Алгоритмы и структуры данных. М., “Мир”, 1989.
   
3. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск данных. М., “Мир”, 1978.
   
4. Лавров И. А. , Максимов А. А.. Задачи по теории множеств, математической логике и теории алгоритмов. М., 1975.
   
5. Мальцев А. И. Алгоритмы и рекурсивные функции. М., Наука,1965.
   
6. Яблонский С.В.. Введение в дискретную математику. М., “Высшая школа”, 2001.
   
7. Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М-СПб-К, “Вильямс”, 2001.
   
8. Горбатов В.А. Фундаментальные основы дискретной математики. М., “Наука. Физматлит”, 2000.
   
9. Зубов В.С. Справочник программиста. М., “Филинъ”, 1999.
   
10. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. М., ЛБЗ, 2001.
    
11. Игошин В. И. Математическая логика и теория алгоритмов. – Саратов. Изд-во Саратовского университета, 1991 г.
    
12. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М., МЦМНО, 2001.