Класс. МУПР ОП.08 Теория алгоритмов. Методические указания по проведению практических работ по дисциплине Теория алгоритмов
 Скачать 3.39 Mb.
|
|
Человек использует компьютер для решения самых разнообразных информационных задач: работа с текстами, создание графических изображений, получение справки из базы данных, табличные расчеты, решение математических задач, расчет технических конструкций и многое другое. Для их решения в распоряжении пользователя имеется обширное программное обеспечение: системное ПО (ядром которого является операционная система) прикладное ПО (программы, предназначенные для пользователя) системы программирования (средства для создания программ на языках программирования). Процесс решения задач на компьютере – это совместная деятельность человека и ЭВМ. На долю человека приходятся этапы, связанные с творческой деятельностью – постановкой, алгоритмизацией, программированием задач и анализом результатов, а на долю персонального компьютера – обработка информации с разработанным алгоритмом. Рассмотрим эти этапы на примере: пусть требуется найти сумму двух чисел. Первый этап – постановка задачи. На этом этапе участвует человек, хорошо представляющий предметную область задачи (биолог, экономист, инженер). Он должен чётко определить цель задачи, дать словесное описание содержания задачи и предложить общий подход к её решению. Для задачи вычисления суммы двух чисел человек, знающий, как складываются числа, может описать задачу следующим образом: ввести два целых числа, сложить их и вывести сумму в качестве результата решения задачи. Второй этап – выбор метода решения (математическое или информационное моделирование). Цель данного этапа – создать такую математическую модель решаемой задачи, которая могла быть реализована в компьютере. Существует целый ряд задач, где математическая постановка сводится к простому перечислению формул и логических условий. Этот этап тесно связан с первым этапом, и его можно отдельно не рассматривать. Однако возможно, что для полученной модели известны несколько методов решения и необходимо выбрать лучший. Для нашего примера: введённые в компьютер числа запомним в памяти под именами А и В,а результат запомним в памяти под именем Summa. Третий этап – алгоритмизация задачи. На основе математического описания необходимо разработать алгоритм решения. Алгоритм – система точных и понятных предписаний о содержании и последовательности выполнения конечного числа действий, необходимых для решения любой задачи данного типа (класса). Понятие возникло и используется давно. Сам термин «алгоритм» ведёт начало от перевода на европейские языки имени арабского математика Аль-Хорезми (IX век). Им были описаны правила (в нашем понимании – алгоритмы) выполнения основных арифметических действий в десятичной системе счисления. Задача составления алгоритма не имеет смысла, если не известны или не учитываются возможности его исполнителя (ребёнок может прочесть, но не может решить сложную задачу). Исполнителем может быть не только человек, но и автомат. Компьютер – лишь частный, но наиболее впечатляющий пример исполнителя, чьё поведение основано на реализации алгоритма. Более того, создание персонального компьютера оказало воздействие на развитие теории алгоритмов, одной из областей дискретной математики. Эффективный метод построения алгоритма – метод пошаговой детализации (последовательного построения). При этом сложная задача разбивается на ряд более простых. Для каждой подзадачи – свой алгоритм. Универсальный эффективный метод построения алгоритма является основой структурного программирования (языки QBasic, Turbo Pascal и др.). Если алгоритм разработан, то его можно вручить разным людям (пусть и не знакомым с сутью решаемой задачи), и они, следуя системе правил, будут действовать одинаково и получат (при безошибочных действиях) одинаковый результат. Используются различные способы записи алгоритмов: – словесный (запись рецептов в кулинарной книге, инструкции по использованию технических устройств и т. п.); – графический – пример на рисунке; – структурно-стилизованный (для записи используется язык псевдокода).  Пример графического изображения алгоритма Свойства алгоритма.При составлении и записи алгоритма необходимо обеспечить, чтобы он обладал рядом свойств. Однозначность алгоритма – единственность толкования исполнителем правил выполнения действий и порядка их выполнения. Чтобы алгоритм обладал этим свойством, он должен быть записан командами из системы команд исполнителя (сложить А и В). Конечность алгоритма – обязательность завершения каждого из действий, составляющих алгоритм, и завершимость алгоритма в целом. Представленный на рисунке алгоритм обладает этим свойством. Результативность алгоритма – предполагает, что выполнение алгоритма должно завершиться получением определённых результатов. У нас для целых А и В всегда будет вычислена сумма. Массовость – возможность применения данного алгоритма для решения целого класса задач, отвечающих общей постановке задачи. В нашем примере алгоритмом используется обозначение, а не конкретные числа, поэтому он может быть использован для сложения любых целых чисел. Правильность алгоритма – способность алгоритма давать правильные результаты решения поставленных задач. Четвёртый этап – программирование.Программой называется план действий, подлежащих выполнению некоторым исполнителем, в качестве которого может выступать компьютер. Программа позволяет реализовать разработанный алгоритм. Именно этому этапу посвящена большая часть данного учебного пособия. Пятый этап – ввод программы и исходных данных в ЭВМ с клавиатуры с помощью редактора текстов и их запись на гибкий или жёсткий диск для постоянного хранения. Шестой этап – тестирование и отладка программы.Исполнение алгоритма с помощью ЭВМ, поиск и исключение ошибок. При этом программисту приходится выполнять рутинную работу по проверке работы программы, поиску и исключению ошибок, и поэтому для сложных программ этот этап часто требует гораздо больше времени и сил, чем написание первоначального текста программы. Отладка программы – сложный и нестандартный процесс, который заключается в том, чтобы протестировать программу на контрольных примерах. Контрольные примеры стремятся выбрать так, чтобы при работе с ними программа прошла все основные пути блок-схем алгоритма, поскольку на каждом из путей могут быть свои ошибки, а детализация плана зависит от того, как поведёт себя программа на этих примерах. На одном она может «зациклиться», на другом дать бессмысленный результат. Сложные программы отлаживают отдельными фрагментами. Для повышения качества выполнения этого этапа используются специальные программы – отладчики, которые позволяют исполнить программу «по шагам» с наблюдением за изменением значений переменных, выражений и других объектов программы, с отслеживанием выполнения операторов. Седьмой этап – исполнение отлаженной программы и анализ результатов.На этом этапе программист запускает программу и задаёт исходные данные, требуемые по условию задачи. Полученные результаты анализируются постановщиком задачи, и на основании этого анализа вырабатываются соответствующие решения, рекомендации, выводы. Например, если при решении задачи на ПК результат 2+3=4, то следует изменить алгоритм и программу. Практическое задание Задание 1. составить в виде блок-схемы алгоритм нахождения середины отрезка при помощи циркуля и линейки опираясь на пример алгоритма естественного языка Дан отрезок АВ. Пример: «Алгоритм деления отрезка АВ пополам». поставить ножку циркуля в т.А; установить раствор циркуля равным длине отрезка АВ; провести окружность; поставить ножку циркуля в т.В; провести окружность; через точки пересечения окружностей провести прямую; отметить точку пересечения этой прямой с отрезком АВ. Задание 2. Используйте ресурсы Интернета для нахождения определения свойств алгоритма и запишите их в тетрадь. Приведите примеры. Задание 3. Допишите в тетради в основные алгоритмические конструкции недостающие правила блок-схем. Задание 4. Сделать вывод о проделанной практической работе Проектное задание Постройте структурную схему алгоритма поиска среднего роста учащихся в колледже, а также минимального и максимального значений роста. Используйте массив для описания списка учащихся, циклическую алгоритмическую конструкцию для поиска минимума и максимума, суммирования всех элементов этого массива. Результат представьте, как итог вычисления среднего арифметического, а для минимального и максимального значений роста учащихся сообщите соответствующие номера этих учащихся в списке группы. |