Лекция 2. Лекция 2 Решение задач на эвм
 Скачать 2.55 Mb.
|
|
Информатика Лекция 2 Решение задач на ЭВМ Решение задач на ЭВМ Этапы разработки программы 1. Содержательная постановка задачи 2. Формализованная постановка (математическая модель) 3. Алгоритмизация 4. Разработка структур данных 5. Программирование и отладка 6. Испытания программы 7. Документирование программы 2 Кузнецов И.Р. Содержательная постановка Формулировка задачи специалистом предметной области ◦ Необходимые исходные данные ◦ Что должно быть получено в результате ◦ Какие ограничения наложены на область применения программы ◦ Дополнительные требования по быстродействию, памяти и др. Контрольные примеры, отражающие сущность задачи Кузнецов И.Р. 3 Формализованная постановка Описание задачи и метода ее решения с помощью соответствующего математического аппарата ◦ Определить и описать математическую форму представления исходных данных и конечных результатов ◦ Сформулировать метод решения (необходимые преобразования, численные методы, правила получения результатов по исходным данным) Кузнецов И.Р. 4 Алгоритмизация Формальное описание вычислительного процесса, направленного на получение результатов из произвольных исходных данных ◦ Преобразование формул к виду, удобному для алгоритмизации ◦ Проектирование схемы алгоритма с пошаговой детализацией процесса вычислений (ГОСТ 19.701-90) ◦ Обработка исключительных ситуаций Кузнецов И.Р. 5 Разработка структуры данных Определение структур, типов и имен для объектов программы ◦ (учет диапазонов значений и требуемой точности) Формирование физической и логической структур данных Разработка физической структуры внешнего представления данных ◦ (выбор форматов и расположения данных на конкретных носителях) Кузнецов И.Р. 6 Программирование и отладка Кодирование ◦ Запись на языке программирования с комментариями и стилем оформления текста программы ◦ Соблюдение правил структурного программирования Автономная отладка модулей, комплексирование и отладка в целом ◦ Определение промежуточных результатов и узловых точек программы Кузнецов И.Р. 7 Испытания программы Проверка соответствия техническому заданию ◦ Разработка тестов (контрольных примеров для всех блоков программы) ◦ Проверка всех вариантов ввода-вывода ◦ Выполнение всех ветвей алгоритма Внесение изменений в программу и соответствующую документацию Кузнецов И.Р. 8 Документирование программы Вид программного документа Содержание программного документа по ГОСТ 19.101-77 Ведомость эксплуатационных документов Перечень эксплуатационных документов на программу Формуляр Основные характеристики программы, комплектность и сведения об эксплуатации программы Описание применения Сведения о назначении программы, области применения, применяемых методах, классе решаемых задач, ограничениях для применения, минимальной конфигурации технических средств Руководство системного программиста Сведения для проверки, обеспечения функционирования и настройки программы на условия конкретного применения Руководство программиста Сведения для эксплуатации программы Руководство оператора Сведения для обеспечения процедуры общения оператора с вычислительной системой в процессе выполнения программы Описание языка Описание синтаксиса и семантики языка Руководство по техническому обслуживанию Сведения для применения тестовых и диагностических программ при обслуживании технических средств Кузнецов И.Р. 9 Отображение Закон по которому каждому элементу некоторого заданного множества ставится в соответствие вполне определенный элемент другого заданного множества x , y , y = f( x ) либо f: (множество - область определения отображения, а множество - множество значений отображения) Понятие отображения совпадает с понятиями функция, оператор, преобразование Кузнецов И.Р. 10 Функция Величина y называется функцией переменной величины x, если каждому из тех значений, которые может принимать x соответствует одно или несколько определенных значений y (совокупность всех значений, которые может принимать аргумент x функции f( x ) называется областью определения функции) Способы задания функции: табличный, графический, аналитический Кузнецов И.Р. 11 Алгоритмизация Кузнецов И.Р. 12 Алгоритм Точное предписание, задающее вычислительный процесс, начинающийся с произвольного набора исходных данных и направленный на получение полностью определяемых ими результатов Абстрактный вычислительный алгоритм применяется к математическим объектам, записывается в математических терминах и не связан с конкретным языком программирования Кузнецов И.Р. 13 Свойства алгоритма Конечность (финитность) ◦ Всегда заканчивается после конечного числа шагов Определенность (детерминированность) ◦ Однозначность и недвусмысленность выполняемых действий на каждом шаге Результативность (направленность) ◦ Получение результата, в том числе в точках неопределенности с выдачей соответствующей информации Массовость ◦ Алгоритм служит для решения целого класса задач Эффективность Кузнецов И.Р. 14 Способы задания алгоритма Способы задания Словесный Графический Диаграмма Несси- Шнейдермана Псевдокоды Программный Кузнецов И.Р. 15 Словесное задание алгоритма Словесный Алгоритмические системы Языки программирования Языки схем алгоритмов Схемы алгоритмов Янова, Ляпунова, операторные схемы Лаврова и проч. Кузнецов И.Р. 16 Алгоритм Евклида Даны два целых положительных числа m и n . Требуется найти их наибольший общий делитель, т.е. наибольшее положительное целое число, которое нацело делит как m , так и n Е1. {Нахождение остатка} Разделим m на n . Пусть остаток равен r , где ≤ r ≤ n Е2. {Проверка на нуль} Если r = , алгоритм заканчивает работу и ответ n Е3. {Замена} Положить m n , n r и возврат к шагу Е1. Схема алгоритма Кузнецов И.Р. 17 начало m, n n := r r = 0 m := n r := m mod n n конец Алгоритм Евклида Кузнецов И.Р. 18 начало m, n n := r r = 0 m := n r := m mod n n конец НОД неотрицательных целых чисел основан на следующих свойствах : Пусть a и b – одновременно не равные нулю числа, причем a ≥ b . Тогда, если b = 0, то НОД (a , b) = a, а если b ≠ 0, то для чисел a , b и c , где c – остаток от деления a на b , выполняется равенство НОД (a , b) = НОД (b , c) . начало a, b b := c b > 0 a := b c := a mod b a конец Диаграмма Несси-Шнейдермана Кузнецов И.Р. 19 Открыть файл на чтение Прочитать первую строку файла Вывести прочитанное значение на экран Закрыть файл Последовательность Простое ветвление Повтор Алгоритмический язык Формальный язык, предназначенный для записи алгоритмов (грамматика, семантика) В каждом алгоритмическом языке должны быть средства для задания операторов, осуществляющих переработку информации, и операторов перехода (распознавателей), определяющих порядок выполнения этих операторов На практике служат теоретической основой для разработки языков программирования Кузнецов И.Р. 20 Классические системы Алгоритмические системы: ◦ нормальные алгоритмы Маркова ◦ рекурсивные функции ◦ машина Тьюринга ◦ машина Поста и др. Ориентированы на рассмотрение фундаментальных теоретических вопросов теории алгоритмов и не служат для описания алгоритмов при их реализации на ЭВМ Кузнецов И.Р. 21 Язык программирования Формальная знаковая система, служащая общению человека с ЭВМ Основное назначение языка программирования – быть средством программирования, т.е. представлять последовательность действий, подлежащих выполнению на ЭВМ Lisp – что делать Prolog – как делать Кузнецов И.Р. 22 Язык схем алгоритмов Предназначен для записи алгоритмов безотносительно к каким-либо вычислительным средствам (графическое изображение алгоритма, пояснения к алгоритму) Функциональный узел имеет один вход и один выход (оператор присваивания вида y := x ) [ y := 2 x + z ] комментарий Кузнецов И.Р. 23 f Язык схем алгоритмов (2) Выбор направления выполнения алгоритма (решение) Этот функциональный узел имеет один вход и два выхода, где P – предикат, т.е. выражение, принимающее в зависимости от значений входящих в него величин одно из двух возможных значений ( true / false, истина / ложь, да / нет ) (оператор выбора) [ P: x > 0 ] Кузнецов И.Р. 24 P да нет Язык схем алгоритмов (3) Кузнецов И.Р. 25 пуск/останов – начало и конец алгоритма ввод/вывод – преобразование данных из внешнего представления во внутреннее и наоборот документ – ввод/вывод данных на твердый носитель соединитель – узел слияния для двух потоков (последовательно при большом количестве потоков) Пример Кузнецов И.Р. 26 a x , y текст d<0 да нет a := b d d := x + c c := |y| 0,25 b := 2 -x a = 2 -x (x + |y| 1/4 ) 1/2 Пусть b = 2 -x c = |y| 1/4 d = x + c Тогда a = b d – результат декомпозиции Цикл лекций подготовлен в 2020/2021 уч. году Кузнецовым Игорем Ростиславовичем, профессором кафедры РЭС Санкт-Петербургского Государственного электротехнического университета «ЛЭТИ» Прочитан в дисциплине « Информатика » © Кузнецов И.Р. 27 Кузнецов И.Р. |