copybook_m2 (1078411)
Текст из файла
Рабочая тетрадьстудента _______________________________________ группы ________________(Ф.И.О.)(номер группы)Модуль 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. Автоматизированное проектирование наносистем: учеб. пособие для вузов / Власов А. И.,Зинченко Л. А., Макарчук В. В., Родионов И. А. // ред. Шахнов В.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
