МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«Забайкальский государственный университет»
(ФГБОУ ВО «ЗабГУ»)
Факультет _____________ Энергетический____________________________
Кафедра __________ Прикладной информатики и математики_____________
УЧЕБНЫЕ МАТЕРИАЛЫ
для студентов заочной формы обучения
(с полным сроком обучения)
по дисциплине
«Теория автоматов и теория алгоритмов»
наименование дисциплины
для направления подготовки
09.03.03 «Прикладная информатика»
Общая трудоемкость дисциплины – 2 зачетные единицы.
Форма текущего контроля в семестре – контрольная работа.
Курсовая работа (курсовой проект) (КР, КП) – нет.
Форма промежуточного контроля в семестре – зачет
1
Краткое содержание курса
Раздел 1. Основы алгоритмизации
Тема 1. Основы алгоритмизации
Алгоритм и его свойства. Предмет теории алгоритмов. Блок-схемы
алгоритмов,
композиция
алгоритмов.
Алгоритмические
модели.
Алгоритмическая неразрешимость.
Тема 2. Функция сложности алгоритма
Функция сложности алгоритма. Виды функции сложности алгоритмов.
Временная функция сложности. Анализ функции сложности по программе.
Оценка алгоритма бинарного поиска. Теоретическая и практическая функции
сложности
Раздел 2. Алгоритмы обработки структур данных
Тема 3. Алгоритмы обработки структур данных. Методы сортировки
Методы сортировки. Сортировка выбором. Сортировка вставкой,
слиянием, обменом. Шейкерная сортировка. Сортировка Шелла. Сортировка
Хоара. Турнирная и пирамидальная сортировка
Тема 4. Алгоритмы обработки структур данных. Методы поиска
Методы
поиска.
Последовательный
поиск.
Бинарный
поиск.
Фибоначчиев поиск. Интерполяционный поиск. Поиск по бинарному дереву.
Поиск по Бору. Поиск хешированием.
Раздел 3. Элементы математической логики
Тема 5. Элементы математической логики
Алгебра высказываний. Законы математической логики.
Раздел 4. Математические модели формальных исполнителей
Тема 6. Математические модели формальных исполнителей
Что такое формальная обработка информации? Конечные автоматы.
Универсальные исполнители.
Тема 7. Математические модели формальных исполнителей
2
Машина Тьюринга. Основные определения, описание и примеры.
Интерпретация поведения и представление данных в МТ.
Тема 8. Математические модели формальных исполнителей
Машина Поста. Основные определения, описание и примеры.
Интерпретация поведения и представление данных в МП.
Семестр 4
Форма текущего контроля
Основной формой отчета студентов о самостоятельной подготовке в
межсессионный период является контрольная работа, предусматривающая
выполнение теоретической и практической частей.
Общие методические указания по выполнению и оформлению заданий
контрольной работы.
Для полноценной подготовки студентов к аттестации необходимо
выполнить контрольную работу по дисциплине «Теория автоматов и теория
алгоритмов» и самостоятельно разобрать теоретический материал (см.
перечень тем из краткого содержания курса).
Задания для контрольной работы состоят из десяти вариантов. Номер
варианта определяется по букве, с которой начинается фамилия студента.
Буква, с
которой
начинается
фамилия студента
А, Б,
В, Г
Д, Е
Ж, 3, И,
К, Л, М
Н, О, П
Р, С, Т
У, Ф, Х
Ц, Ч, Ш
Щ, Ю, Я
3
№
варианта
1
2
3
4
5
6
7
8
9
10
Каждый вариант содержит два теоретических вопроса из 1 и 2
разделов и один практический из 2 раздела. Результат выполнения
контрольной работы должен быть представлен на электронном
носителе в виде документа, выполненного в текстовом процессоре Word
(теоретические вопросы) и решения задачи из второго раздела, используя
язык программирования Паскаль (практический вопрос).
В конце контрольной работы приводится список используемой
литературы, Интернет – источников. Источники должны быть актуальными.
Объём теоретической части контрольной работы должен быть
представлен в пределах 10-15 страниц стандартного формата. На диске
студент
указывает
фамилию,
имя,
отчество,
контактный
телефон,
электронный адрес, номер варианта, номер зачётной книжки, курс, группу.
Текст документа выполняют с использованием компьютера на одной
стороне листа белой бумаги формата А4 (210×297) ГОСТ 9327-60. Гарнитура
шрифта основного текста — «Times New Roman». Размер шрифта для
основного текста —14 пт, для таблиц —12 пт или 14 пт. Междустрочный
интервал основного текста – полуторный, цвет шрифта – черный. Текст
следует размещать, соблюдая размеры полей: левое – не менее 30 мм, правое
– не менее 10 мм, верхнее – не менее 20 мм, нижнее – не менее 20 мм,
абзацный отступ – 1,25 см.
После проверки контрольной работы преподавателем, и устранения
всех указанных недочетов по ней проводится собеседование, которое служит
допуском к сдаче зачёта.
Варианты контрольной работы:
Вариант 1.
1. Понятие алгоритма, свойства алгоритмов. Типы алгоритмов. Способы
задания алгоритмов. Графическое построение алгоритма.
2. Что понимается под сортировкой? Каковы методы сортировки? Каковы
особенности сортировки выбором? Каковы особенности сортировки
вставкой?
3. Решить задачу, используя язык программирования Паскаль
(практический вопрос):
4
Упорядочить элементы массива А в порядке возрастания элементов
методом нахождения последовательных минимумов.
Вариант 2.
1. Этапы
решения
задачи.
Линейная
структура
алгоритмов.
Разветвляющая структура алгоритмов. Циклическая структура
алгоритмов.
2. Что понимается под сортировкой? Каковы методы сортировки? Каковы
особенности сортировки Шелла?
3. Решить задачу, используя язык программирования Паскаль
(практический вопрос):
Упорядочить массив А в порядке возрастания элементов методом
пузырька.
Вариант 3.
1. Понятие технологии программирования. Характеристика языков
программирования. Структура языка программирования. Трансляторы
с языков программирования.
2. Что понимается под сортировкой? Каковы методы сортировки? Каковы
особенности сортировки обменом? Какова основная идея шейкерной
сортировки?
3. Решить задачу, используя язык программирования Паскаль
(практический вопрос):
Дан массив Т, элементы которого упорядочены по возрастанию.
Вставить в него элемент Х, не нарушая упорядоченности массива.
Вариант 4.
1. Алгоритмический язык Паскаль: особенности, назначение. Алфавит и
словарь языка Паскаль. Константы и переменные.
2. Что понимается под сортировкой? Каковы методы сортировки? Каковы
особенности сортировки Хоара?
3. Решить задачу, используя язык программирования Паскаль
(практический вопрос):
Сортировка
простым
обменом
(«пузырек»).Упорядочить
целочисленный массив А[1..n] по неубыванию, многократно
переставляя каждые два соседних элемента, нарушающих порядок.
Процесс продолжается до достижения упорядоченности массива.
Вариант 5.
1. Структура программы. Требования к написанию программ.
Классификация типов данных. Стандартные типы данных.
Пользовательские типы данных.
2. Что понимается под сортировкой? Каковы методы сортировки?
Каковы особенности турнирной и пирамидальной сортировки?
5
3. Решить задачу, используя язык программирования Паскаль
(практический вопрос):
Сортировка простым выбором. Упорядочить целочисленный массив
А[1..n] по неубыванию, меняя местами очередной элемент с
максимальным среди неупорядоченной части массива, то есть
используя метод: A[i] = Max{A[j], j = 1..i}; i = n, n - 1, ..., 3, 2.
Вариант 6.
1. Выражения, операции, операнды. Приоритеты выполнения операций.
Понятие оператора. Простые операторы.
2. Каковы методы поиска? Каковы особенности последовательного и
бинарного поиска?
3. Решить задачу, используя язык программирования Паскаль
(практический вопрос):
Сортировка простыми вставками. Упорядочить целочисленный
массив А[1..n] по неубыванию, используя следующий метод: для i от 2
до n каждый элемент A[i] вставляется на свое место в упорядоченной
ранее части массива А[1], ..., A[i — 1]. При этом, естественно, если это
необходимо, происходит сдвиг элементов массива.
Вариант 7.
1. Выражения, операции, операнды. Структурные операторы: составной
оператор.
2. Каковы методы поиска? Каковы особенности фибоначчиевого и
интерполяционного поиска?
3. Решить задачу, используя язык программирования Паскаль
(практический вопрос):
Сортировка подсчетом. Упорядочить целочисленный массив А[1..n]
по неубыванию.
Вариант 8.
1. Выражения, операции, операнды. Структурные операторы: условные
операторы.
2. Каковы методы поиска? Каковы особенности поиска по бинарному
дереву?
3. Решить задачу, используя язык программирования Паскаль
(практический вопрос):
Упорядочить целочисленный массив А[1..n] по неубыванию методом
«пузырька», исключив, если они есть, лишние просмотры элементов
массива. Например, массив состоит из 6 элементов: 12, 3, 5, 7, 9, 10. За
один просмотр методом «пузырька» он становится отсортированным,
остальные просмотры лишние.
6
Вариант 9.
1. Выражения, операции, операнды. Структурные операторы: операторы
повтора.
2. Каковы методы поиска? Каковы особенности поиска по бору?
3. Решить задачу, используя язык программирования Паскаль
(практический вопрос):
Упорядочить целочисленный массив А[1..n] по неубыванию методом
«пузырька», устранив несимметричность метода по отношению к
различным исходным данным.
Вариант 10.
1. Понятие массива, характеристика массива. Описание массивов.
2. Каковы методы поиска? Каковы особенности поиска хешированием?
3. Решить задачу, используя язык программирования Паскаль
(практический вопрос):
Сортировка слияниями. Метод основан на идее слияния двух
отсортированных частей массива, поэтому первоначально массив
разбивается на две части, которые независимо сортируются, а затем
результаты сливаются в единое целое. С каждой из частей
выполняются аналогичные действия, до тех пор, пока количество
элементов в сортируемой части массива не станет равно двум. В этом
случае выполняется простое сравнение элементов и их перестановка,
если она необходима. Реализовать метод.
Форма промежуточного контроля
Промежуточная аттестация по данной дисциплине осуществляется в 4
семестре в виде зачёта.
Вопросы к зачёту:
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
Понятие алгоритма, свойства алгоритмов.
Типы алгоритмов
Способы задания алгоритмов.
Графическое построение алгоритма
Этапы решения задачи
Линейная структура алгоритмов.
Разветвляющая структура алгоритмов.
Циклическая структура алгоритмов.
Понятие технологии программирования.
Характеристика языков программирования.
Структура языка программирования.
Трансляторы с языков программирования.
Алгоритмический язык Паскаль: особенности, назначение.
7
17. Алфавит и словарь языка Паскаль.
18. Константы и переменные.
19. Структура программы. Требования к написанию программ.
20. Классификация типов данных.
21. Стандартные типы данных.
22. Пользовательские типы данных.
23. Выражения, операции, операнды.
24. Приоритеты выполнения операций.
25. Понятие оператора. Простые операторы.
26. Структурные операторы: составной оператор.
27. Структурные операторы: условные операторы.
28. Структурные операторы: операторы повтора.
29. Понятие массива, характеристика массива.
30. Описание массивов.
31. Порядок разработки программы на Паскале.
32. Дайте определение функции сложности.
33. Укажите виды функций сложности алгоритмов
34. Что включает понятие сложности алгоритма?
35. Укажите правила для определения функции сложности.
36. Какие виды функции сложности существуют?
37. Каким образом определяется временная функция сложности?
38. Назовите способы анализа функции сложности по программе.
39. Какие значения принимает экспериментальная функция сложности?
40. Что понимается под сортировкой? Каковы методы сортировки?
41. Каковы особенности сортировки вставкой?
42. Каковы особенности сортировки выбором?
43. Каковы особенности сортировки обменом?
44. Каковы особенности сортировки Шелла?
45. Каковы особенности сортировки Хоара?
46. Каковы особенности турнирной сортировки?
47. Каковы особенности пирамидальной сортировки?
48. Какова основная идея шейкерной сортировки?
49. Каковы особенности последовательного поиска?
50. Каковы особенности бинарного поиска?
51. Каковы особенности интерполяционного поиска?
52. Каковы особенности фибоначчиевого поиска?
53. Каковы особенности поиска по бинарному дереву?
54. Каковы особенности поиска по бору?
55. Каковы особенности поиска хешированием?
56. Структура машины Тьюринга. Назначение составных частей.
57. Состав команды машины Тьюринга и последовательность ее
выполнения.
58. Состав универсальной машины Тьюринга. Особенности размещения
информации на ленте.
59. Этапы выполнения команды машиной Тьюринга. Содержание этапов.
8
60. Типы автоматов. Комбинационные схемы и автоматы с памятью, их
особенности.
61. Структура машины Поста. Назначение составных частей.
Оформление письменной работы согласно МИ 4.2-5/47-01-2013
Общие требования к построению и оформлению учебной текстовой
документации
Учебно-методическое и информационное обеспечение дисциплины
1.1.
Основная литература*
1.1.1. Печатные издания
1. Глухов Михаил Михайлович. Математическая логика. Дискретные
функции. Теория алгоритмов: учеб. пособие / Глухов Михаил
Михайлович, Шишков Алексей Борисович. – Санкт-Петербург: Лань,
2012. – 416 с.
2. Лихтарников Леонид Моисеевич. Математическая логика. Курс
лекций. Задачник-практикум и решения – 3-е изд., испр.: учеб. пособие
/ Лихтарников Леонид Моисеевич, Сукачева Тамара Геннадьевна. –
Санкт-Петербург: Лань, 2008. – 288с.
1.1.2. Издания из ЭБС
3. Абдеева Наталья Анатольевна. Теория автоматов и теория алгоритмов:
учеб. пособие / Н. А. Абдеева. – Чита: ЗабГУ, 2016. – 204 с.
4. Трофимов,
Валерий
Владимирович.
Алгоритмизация
и
программирование: Учебник / Трофимов Валерий Владимирович;
Трофимов В.В. - отв. ред. - М.: Издательство Юрайт, 2017. - 137.
1.2.
Дополнительная литература
1.2.1. Печатные издания
5. Дискретная математика: учеб. пособие / Куликов Валерий Васильевич.
– Москва: РИОР, 2013. – 174 с.
9
6. Дискретная математика. Алгоритмы и программы. Расширенный курс:
учеб. пособие / Иванов Борис Николаевич. – Москва: Известия, 2011. –
512 с.
1.2.2. Издания из ЭБС
7. Скорубский, Владимир Иванович. Математическая логика : Учебник и
практикум / Скорубский Владимир Иванович; Скорубский В.И., Поляков
В.И., Зыков А.Г. - М.: Издательство Юрайт, 2017. - 211с.
1.3.
Базы данных, информационно-справочные и поисковые
системы
8.
www.intuit.ru – Интернет – университет информационных технологий
9.
http://ru.wikipedia.org/wiki/ - Всемирная электронная энциклопедия
Википедия (Россия)
10.
http://window.edu.ru/ - электронная библиотека (единое окно доступа к
образовательным ресурсам).
11.http://math.ru/lib/plm/54 (электронная версия книги В.А. Успенского
«Машина Поста»).
12.http://softsearch.ru/programs/45-346-interpretator-mashiny-postadownload.shtml (имитатор машины Поста).
13.http://www.osp.ru/ - сайт журнала о компьютерах и компьютерной технике,
программном обеспечении.
Преподаватель ________________________доцент кафедры ПИМ
к.п.н. Н.А. Абдеева
Заведующий кафедрой __________________д.э.н., профессор,
И.П. Глазырина
10
