Презентация. Алгоритм. Программа. Этапы решения задач на компьютере

Скачать презентацию




1 Лекция 1. Алгоритм. Программа. Этапы решения задач на компьютере. В.В. Толасова
 


2 Алгоритм – основное понятие, не имеющее формального определения в терминах более простых понятий, оно абстрагируются непосредственно из опыта. Алгоритм – понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящую от исходных данных к конечному результату
 


3 Исполнитель алгоритма. Система команд исполнителя. Исполнитель алгоритма — это некоторая абстрактная или реальная (техническая, био-логическая или биотехническая) система, способная выполнить действия, предписыва- емые алгоритмом. Все действия, которые исполнитель умеет выполнять, составляют систему команд исполнителя (СКИ)
 


4 Свойства алгоритма: Понятность Точность Упорядоченность Конечность Дискретность Эффективность Массовость
 


5 Свойства алгоритма: Понятность – алгоритм должен состоять только из тех команд, которые входят в СКИ. Точность (определённость, детерминированность) – каждая команда должна быть истолкована исполнителем однозначно Упорядоченность – строго определённый порядок выполнения действий
 


6 Свойства алгоритма: Конечность (финитность, результативность) – выполнение алгоритма должно приводить к решению задачи за конечное число шагов или за конечное число шагов должно быть выдано сообщение, что задача решения не имеет. Дискретность –процесс решения задачи представляет последовательное выполнение простых (или ранее определенных) шагов.
 


7 Свойства алгоритма: Эффективность – решение задачи за приемлемое для разработчика время Массовость – означает, что алгоритм разработан в общем виде, для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные принадлежат некоторой области, которая называется областью применимости алгоритма. Массовость и эффективность, в отличие от остальных свойств, не являются необходимым свойством алгоритма, но определяют его качество.
 


8 Способы записи алгоритма: словесная – запись на естественном языке; графическая – с помощью блок-схем, диаграмм Насси-Шнейдермана, языка ДРАКОН; псевдокоды – полуформализованные описания на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.; программная – тексты на языках программирования.
 


9 Основные алгоритмические структуры следование ветвление цикл Это предположение высказано в 1965 г. Э. Дейкстрой, в том же году итальянские математики К. Бом и Д. Джакопини сформулировали теорему о структурности : Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур:
 


10 Линейный алгоритм Структура «следование» представляет собой ряд действий, следующих одно за другим:
 


11 Разветвляющийся алгоритм Разветвляющимся называют алгоритм, в котором в зависимости от истинности некоторого условия происходит переход на одну из двух возможных последовательностей действий. Ветвление бывает полным – каждая из ветвей содержит команды неполным – в случае истинности условия выполняется некоторая команда, в противном случае – команда пропускается
 


12 Разветвляющийся алгоритм Полное ветвление Неполное ветвление
 


13 Циклический алгоритм Обеспечивает многократное выполнение некоторой последовательности действий, которая называется телом цикла. «Многократно» – не значит «бесконечно», прекращение циклической последовательности происходит в результате проверки истинности некоторого условия
 


14 Циклический алгоритм В зависимости от того, когда происходит проверка, различают Цикл с предусловием Цикл с постусловием
 


15 Циклический алгоритм Проверка условия происходит перед выполнением тела цикла. Такой цикл может не выполниться ни разу, если изначально условие было ложным. Цикл с предусловием
 


16 Циклический алгоритм Цикл с постусловием Проверка условия происходит после выполнения тела цикла. Такой цикл обязательно выполнится хотя бы один раз.
 


17 Циклический алгоритм Используется, если заранее известно, сколько раз необходимо выполнить тело цикла. p – параметр, меняется от a до b с шагом с a – начальное значение b – конечное значение с – шаг изменения параметра Цикл с параметром (пересчёт, цикл с заданным количеством повторений)
 


18 Языки программирования Запись алгоритма в словесной форме, в виде блок-схемы или на псевдокоде позволяет человеку понять суть дела и исполнить алгоритм, однако допускает определенный произвол при изображении команд. Алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем. Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера.
 


19 Языки программирования 1 – есть электрический сигнал, 0 – сигнал отсутствует. Процессор может обрабатывать информацию, представленную в двоичной форме: Первые компьютеры программировались аппаратным путём: между элементами памяти и вычисляющими устройствами замыкался ряд выключателей в определённом порядке. Программы и языки программирования в то время отсутствовали.
 


20 Языки программирования В дальнейшем было предложено хранить программу так же, как и данные, в виде двоичных последовательностей (так называемый машинный код). Перевод алгоритма в двоичный код требовал от программиста внимания и очень высокой квалификации. Для облегчения этого процесса были созданы ассемблеры, позволяющие записывать программы не двоичными последовательностями, а символьными обозначениями, ведь человеку их легче запомнить. Такие языки называют языками низкого уровня (ЯНУ), поскольку они имеют дело непосредственно с аппаратной частью компьютера и сильно зависят от его архитектуры (у каждого семейства ЭВМ своя система команд процессора, свой язык)
 


21 Языки программирования В 1954 году был создан первый язык высокого уровня (ЯВУ) – FORTRAN . Язык высокого уровня не зависит от аппаратной части компьютера, понятен человеку, поскольку представляет собой набор нескольких ключевых слов, взятых из английского языка и его предложения (выражения и операторы) строятся по небольшому количеству чётко определённых правил.
 


22 Языки программирования Машинно-ориентированные (языки низкого уровня, ЯНУ) – позволяют создавать компактные и эффективные программы, но требуют высокой квалификации от программиста, знания архитектуры данного процессора, для переноса на компьютер другого семейства программу необходимо полностью переписывать Машинно-независимые (языки высокого уровня, ЯВУ) – легче осваиваются человеком, позволяют создавать большие по объёму программы, легко переносятся с компьютера на компьютер при условии, что на компьютере установлено специальное программное обеспечение – транслятор с данного языка
 


23 Языки программирования Трансляторы по принципу работы подразделяются на Компиляторы – переводят в двоичный код всю программу сразу, и только потом программа выполняется. Интерпретаторы – выполняют программу непосредственно, выбирая очередную команду и тут же её исполняя.
 


24 Языки программирования Для создания программ требуется специальное программное обеспечение –включающее в себя редактор для набора текста программ, транслятор, отладчик и ряд других модулей. В настоящее время для этих целей созданы интегрированные среды разработки (Integrated Development Environment, IDE).
 


25 Языки программирования Языки высокого уровня делятся на: процедурные (алгоритмические) (Basic, Pascal, C и др.), которые предназначены для однозначного описания алгоритмов; для решения задачи процедурные языки требуют в той или иной форме явно записать процедуру ее решения; объектно-ориентированные (Object Pascal, C++, Java Visual Basic и др.), в основе которых лежит понятие объекта, сочетающего в себе данные и действия над нами. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути описывает часть мира, относящуюся к этой задаче. Описание действительности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур; прочие - декларативные, функциональные, логические.
 


26 Языки программирования алфавит – набор символов, используемый для кодирования информации; синтаксис – правила, по которым из символов алфавита собираются конструкции языка; семантику – правила, согласно которым происходит истолкование языковых конструкций. Язык программирования, как и любой другой, естественный или искусственный язык, имеет
 


27 Этапы решения задач с использованием компьютера. Постановка задачи Создание математической модели Выбор метода решения и создание алгоритма Создание программы и её отладка Анализ результатов (при необходимости – уточнение модели)
 


28 Этапы решения задач с использованием компьютера. Постановка задачи Четкая формулировка задачи, выделение исходных данных для ее решения и точные указания относительно того, какие результаты и в каком виде должны быть получены. Постановка задачи должна давать ответ на следующие вопросы: что дано? что требуется? какие данные допустимы?
 


29 Этапы решения задач с использованием компьютера. Создание математической модели Моделирование – замена рассматриваемого объекта другим, отражающим наиболее существенные параметры в контексте решаемой задачи, исключая из рассмотрения несущественные в данном случае моменты. Математическая модель – описание объекта на языке математики: с помощью формул, уравнений, неравенств.
 


30 Этапы решения задач с использованием компьютера. Выбор метода решения и создание алгоритма В зависимости от модели и условий задачи. При выборе алгоритма следует учитывать такие свойства, как эффективность и массовость
 


31 Этапы решения задач с использованием компьютера. Создание программы и её отладка Наиболее трудоёмким является процесс отладки (локализация и устранение ошибок в программе). Для обнаружения ошибок используют тестирование программы – выполнение с набором исходных данных, ответ для которых заранее известен. Тесты следует составлять так, чтобы проверялась работа программы для допустимых значений данных, для пограничных для явно недопустимых. Следует отметить, что правильно выполненный тест не гарантирует правильной работы программы.
 


32 Этапы решения задач с использованием компьютера. Создание программы и её отладка Ошибки бывают Синтаксические –обнаруживаются транслятором и поэтому достаточно легко устраняются. Ошибки выполнения – деление на ноль или корень из отрицательного числа, следует внимательно относиться к области допустимости данных. Логические – ошибки в алгоритме, требуют наибольших затрат по обнаружению и устранению.
 


33 Этапы решения задач с использованием компьютера. Анализ результатов (при необходимости – уточнение модели) Если программа работает верно, то можно пользоваться ею в практических целях Если же, несмотря на то, что ошибки устранены, результаты не соответствуют реальному положению, следует уточнить модель, возможно, что-то не было учтено и повторить весь цикл, начиная со второго пункта.
 

< <       > >