copybook_m2 (Рабочая тетрадь)

Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Модуль 25. Анализ и построение алгоритмов (Семинар 5)Цель семинара: дать основные понятия теории алгоритмов.Задание №1. Продолжите фразуАлгоритм -Абстрактный алфавитЗадание №2. Для программы (по указанию преподавателя) приведите примеры всехтипов данных, использованных в реализованных в программе алгоритмах.Тип данныхПримерЗадание №3. Заполните таблицу, указав в ней символы данных по ГОСТ 19.701-90(ИСО 5807-85)НаименованиеГрафическое изображение29Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)НаименованиеГрафическое изображениеЗадание №4.

Поясните основные свойства алгоритма30Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Задание №5. Заполните таблицу, указав в ней символы процесса по ГОСТ 19.701-90(ИСО 5807-85)НаименованиеГрафическое изображениеЗадание №6. Для программы по указанию преподавателя составить словесную схемуалгоритмов, использованных в программе (по указанию преподавателя).31Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Задание №7. Заполните таблицу, указав в ней символы линий по ГОСТ 19.701-90(ИСО 5807-85)НаименованиеГрафическое изображениеЗадание №8. Поясните основные универсальные алгоритмические модели.32Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Задание №9.

Заполните таблицу, указав в ней специальные символы по ГОСТ 19.70190 (ИСО 5807-85)НаименованиеГрафическое изображениеЗадание №10. Заполните таблицу, выбрав верный, на Ваш взгляд, ответ на вопрос.№п/п1231ВопросОтветыА.ПростоевысказываниеБ.ОператорсуперпозицииВ. Оператор рекурсииГ.ЛогическоевыражениеА.

АлфавитБ.ЛогическаяфункцияВ. Базовая функцияГ.СложноевысказываниеА. Оператор рекурсииБ. Базовая функцияВ.ОператорсуперпозицииГ. ДизъюнкцияВерные ответыА.АлфавитныйоператорБ. КонъюнкцияВ.СложноевысказываниеГ.Операторпостроенияпопервому нулю33Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Задание №11.

Продолжите фразуТезис Черча -Алфавитный операторЗадание №12. Для программы по указанию преподавателя составить структурнуюсхему алгоритмов, использованных в программе (по указанию преподавателя).34Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Задание №13.

Заполните таблицу, указав в ней обозначения, используемые вграфических схемах алгоритмов.НазначениеОбозначениеЗадание №14. Нормальный алгоритм Маркова определен в алфавите А={a, b}системой подстановок:ba → aaa → abb → aaaaa →Заполнить таблицу, указав по шагам, в какое слово этот алгоритм переработаетследующие слова.№1Исходное словоabab2bbbb3abbaРезультат35Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Результат проверить с использованием эмулятора.Задание №15. Продолжите фразуТезис Маркова -Логическая схема алгоритма -Задание №16.

Построить алгоритм Маркова для перевода чисел из двоичной системыв унарную. Проверить правильность работы алгоритма на примере (по указаниюпреподавателя) с использованием эмулятора.Задание №17. Продолжите фразуМашина Тьюринга -Тезис Тьюринга-Черча -Задание №18. Построить алгоритм Маркова для шифрования по шифру Цезаря.Проверить правильность работы алгоритма на примере (по указанию преподавателя) сиспользованием эмулятора.36Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Задание №19. Нарисуйте схематически машину Тьюринга.Задание №20.

Продолжите фразуМашина Поста -Тезис Поста -Задание №21. Проиллюстрировать работу машины Тьюринга по шагам для примера,указанного преподавателем.№КонфигурацияКомандаТекущее состояние37Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Задание №22. Продолжите фразуВременная сложность алгоритмов -Пространственная сложность алгоритмов -Задание №23. Поясните основные универсальные схемы алгоритмов, используяментальные карты.38Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Задание №24.

Продолжите фразуАлгоритм называется полиномиальнымЭффективный алгоритм -Задание №25. Заполните таблицу, систематизировав данные о времени работыалгоритма (время выполнения одной операции по указанию преподавателя)ТрудоемкостьалгоритмаРазмер входа задачи, n20501005001000lg nn1000nn2n32nn!Построить графики зависимостей по точкам.39Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)40Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Задание №26. Продолжите фразуАлгоритм относится к NP-классуNP –полная задачаЗадание №27.

Поясните основные этапы анализа алгоритма.Задание №28. Реализуйте программу (алгоритмы по заданию преподавателя).Задание №29. Продолжите фразу.Нисходящее проектирование алгоритмовВосходящее проектирование алгоритмовЗадание №30. Продолжите фразуNP –трудная задачаФормулировка задачи сортировки -41Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Задание №31.

Заполните таблицу, сравнив достоинства и недостатки различныхалгоритмов сортировки.№п/пАлгоритмсортировкиХарактеристикиалгоритмаДостоинстваНедостатки12345678Контрольные вопросы1. Перечислите основные свойства алгоритма.2. Какие универсальные алгоритмические модели Вы знаете?3. Сравните характеристики алгоритмов сортировки.4. Перечислите основные универсальные схемы алгоритмов.42Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)6.

Решение практических задач на основе теории графов (Семинар 6)Цель семинар: дать навыки применения теории графов при решении практическихзадач конструкторско-технологической информатики.Задание №1. Продолжите фразуСвязность графа -Реберная связность графа -Задание №2. Приведите примеры:2.1.

Граф является эйлеровым и гамильтоновым2.2. Граф является неэйлеровым и гамильтоновым43Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)2.3. Граф является эйлеровым и негамильтоновым2.4. Граф является неэйлеровым и негамильтоновымЗадание №3.

Укажите размерность входных данных для обработки графа (задание№7, семинар №2).Задание №4. Реализуйте программу, в которой реализуются следующие алгоритмы(по заданию преподавателя).МинимумМаксимум44Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Задание №5. Продолжите фразуДерево -Задача Штейнера -Задание №6.

Продолжите фразуЦикломатическое число графа -Хроматическое число графа -Задание №7. Разработайте алгоритм, проверяющий, является ли данный графдеревом.45Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Задание №8. Покажите основные шаги алгоритма при построении минимальногоостовного дерева (номер примера по указанию преподавателя)Пример №Алгоритм Прима46Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Алгоритм КрускалаЗадание №9.

Заполните таблицу, сравнив достоинства и недостатки различныхалгоритмов для работы с графами.№п/пАлгоритм дляработы с графамиХарактеристикиалгоритмаДостоинстваНедостатки123447Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Контрольные вопросы1. Поясните соотношения между связностью графа и его реберной связностью.2. Проведите сравнительный анализ алгоритмов Прима и Крускала.3. Чем хроматическое число графа отличается от цикломатического числа графа.4. Поясните алгоритм раскраски графа.48Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)ЗАКЛЮЧЕНИЕКурс «Функциональная логика и теория алгоритмов» может читаться в соответствие сметодикой, принятой на кафедре, причем в зависимости от учебных планов отдельные разделыпрограммы могут излагаться более расширенно или более сжато; очередность разделов курсаможет варьироваться.Теория алгоритмов представляет собой непрерывно развивающуюся и обогащающуюсяновыми разделами дисциплину.

В связи с этим рекомендуется регулярное обновление курса всоответствие с последними достижениями в области теории алгоритмов.Автор глубоко признательна рецензентам за множество ценных замечаний и советов,способствовавших улучшению методических материалов.Автор считает своим приятным долгом выразить глубокую признательность всем своимколлегам, с которыми авторов связывают многолетние научные связи и контакты, заобсуждение методических материалов, позволившее улучшить содержание работы.Если методические материалы помогут читателю более глубоко понять рольавтоматизации проектирования в изучении явлений, происходящих в микро- и наносистемах,то автор будет считать свою задачу выполненной. Все замечания, предложения и пожеланияавтором будут с благодарностью приняты.49Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)ЛИТЕРАТУРА1.

Кнут Д. Искусство программирования. М.: Вильямс, 2000.2. Ахо А.В., Хопкрофт Дж.Э., Ульман Дж.Д. Структуры данных и алгоритмы: Учеб.пособие: пер.с англ. / ред. Минько А.А.; пер. Минько А.А. -М.: Издат. дом "Вильямс", 2000.- 382 с.3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО,1999. – 955 с.4. Автоматизированное проектирование наносистем: учеб. пособие для вузов / Власов А. И.,Зинченко Л. А., Макарчук В. В., Родионов И. А. // ред. Шахнов В.