Алгоритмы_Программирование_1. Понятие об алгоритмах и протоколах
 Скачать 1.32 Mb.
|
|
Понятие об алгоритмах и протоколах Алгоритм — это точный набор инструкций, описывающих последовательность действий исполнителя для достижения результата решения задачи за конечное время. • Современное формальное определение алгоритма было дано в 30—50-х годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова. • Само слово «алгоритм» происходит от имени учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. Переводчик дал ей название Algoritmi de numero Indorum («Алгоритми о счёте индийском»). По-арабски же книга именовалась Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово Алгебра. Формы представления алгоритмов • словесная (записи на естественном языке); • графическая (изображения из графических символов); • псевдокоды • программная (тексты на языках программирования). Псевдокод – это полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и пр. Пример алгоритма нахождения НОД 1. задать два числа; 2. если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма; 3. определить большее из чисел; 4. заменить большее из чисел разностью большего и меньшего из чисел; 5. повторить алгоритм с шага 2. Особенности словесного способа описания - Не формализуемы - Многословны - Неоднозначны Особенности графического способа - Компактность - Наглядность, алгоритм представлен связанными между собой функциональными блоками Особенности псевдокода - Близок к естественному языку - Могут использоваться формальные конструкции - Широкий, не специфицированный набор команд - Присутствуют служебные слова Блок-схемы Блок-схемой называют графическое представление алгоритма, в котором он изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. - Каждому типу действий сопоставлена определенная геометрическая фигура. - Блоки соединяются линиями переходов, определяющими очередность выполнения действий или направление потоков информации. таблица наиболее часто встречающихся обозначений с расшифровкой • Блок "решение" используется для обозначения переходов управления по условию. В каждом блоке "решение" должны быть указаны вопрос, условие или сравнение, которые он определяет. • Блок "модификация" используется для организации циклических конструкций. (Слово модификация означает видоизменение, преобразование). Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения. • Блок "предопределенный процесс" используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращений к библиотечным подпрограммам. Пример блок-схемы определения высот треугольника со сторонами a, b, c Базовые структуры алгоритмов Базовая структура следование. Образуется из последовательности действий, следующих одно за другим: Базовая структура ветвление. Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Виды структур ветвления: - если-то; - если-то-иначе; - множественный выбор; - выбор-иначе. Пример блок-схемы вычисления функции Базовая структура цикл. Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Цикл типа для. Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне. цикл для i от i1 до i2 шаг i3 тело цикла (последовательность действий) конец цикла Цикл типа пока. Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока. цикл пока (условие) тело цикла (последовательность действий) конец цикла Цикл типа делать - пока. Выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока. Условие проверяется после выполнения тела цикла. цикл выполнять тело цикла (последовательность действий) пока (условие) конец цикла Пример. Составить алгоритм вычисления суммы ряда с заданной точностью Решая эту задачу "в лоб" путем вычисления на каждом i-ом шаге частичной суммы S := S + (-1) (i-1) * (x i ) / i, мы получим очень неэффективный алгоритм, требующий постоянного на каждом этапе выполнения большого числа операций возведения в степень (x^i). Гораздо лучше оптимизировать вычисления, введя величину p 0 = -1, а последующие величины p n вычислять как p n = - (p n-1 * х). Тогда знак произведения будет меняться автоматически, а вместо вычисления все увеличивающейся степени х можно будет просто производить перемножение двух чисел, а само слагаемое получать вычислением m = p/i, где i - номер слагаемого. Алгоритм, в состав которого входит итерационный цикл, называется итерационным алгоритмом. В итерационных алгоритмах необходимо обеспечить обязательное достижение условия выхода из цикла (сходимость итерационного процесса). В противном случае произойдет зацикливание алгоритма, т.е. не будет выполняться основное свойство алгоритма - результативность. Вложенные циклы Используются в случае, когда внутри главного цикла необходимо организовать вспомогательный цикл. При использовании такой структуры для экономии машинного времени необходимо выносить из внутреннего цикла во внешний все операторы, которые не зависят от параметра внутреннего цикла. Пример вложенных циклов для. Вычислить сумму элементов заданной матрицы А(5,3). Пример вложенных циклов пока. Вычислить произведение тех элементов заданной матрицы A(10,10), которые расположены на пересечении четных строк и четных столбцов. Пара слов о данных Данные – это некоторые сообщения, слова в некотором заданном алфавите. Пример. Число 123 – данное, представляющее собой слово в алфавите из десяти натуральных цифр; число 12,34 – данное, представляющее собой слово в алфавите из десяти натуральных цифр и десятичной запятой; текст "математика и информатика – нужные дисциплины", – данное в алфавите из символов русского языка и знаков препинания, включая пробел. До разработки алгоритма (программы) необходимо выбрать оптимальную для реализации задачи структуру данных и оптимальный алгоритм реализации. Пример. При решении системы линейных алгебраических уравнений можно воспользоваться методом Крамера (с помощью определителей) или методом Гаусса (с помощью последовательных исключений неизвестных). Метод Крамера потребует при реализации примерно в 3 раза больше операций, чем метод Гаусса, и поэтому им никогда не пользуются при расчетах на ЭВМ. Простой тип данных – это переменные с определенным именем, например a = 1. В языках есть служебные слова для определения этих типов данных, например, integer, real, char, boolean. Сложный тип данных это переменные, которые внутри себя содержат наборы разнородных данных. Это обычно объекты, строки и массивы. Пример : Person = { “name” = “Vasia”, “age” = 15, “gender” = “m” } Понятие конечного автомата состояний Конечные автоматы – это устройства, каждый отдельный момент времени пребывающие в одном из конечного замкнутого набора состояний. Любой конечный автомат реализует некий непустой класс алгоритмов и состоит из совокупности управляющего автомата, который определяет порядок выполнения действий, и операционного автомата, реализующего сами действия, выполняемые автоматом. Пример конечного автомата – автомат для продажи газированной воды. Его функционирование можно изобразить графом, если ввести следующие множества и события: X = {1, 3, Г, Ø} – входное множество, Y = {В, С, О} – выходное множество, S = {s 0 , s 1 , s 2 , s 3 } – множество состояний, 1 – входной сигнал "опустить 1 руб.", 3 – входной сигнал "опустить 3 руб.", Г – входной сигнал "опустить гнутую монету", Ø– входной сигнал "монета не опущена", В – выходной сигнал "выдача воды газированной без сиропа", С – выходной сигнал "выдача газированной воды с сиропом", О – выходной сигнал "отказ выдать воду", s 0 – первое состояние – "начальное состояние", s 1 – второе состояние – "обработка 1 руб.", s 2 – третье состояние – "обработка 3 руб.", s 3 – четвертое состояние – "состояние неисправности". Различие между алгоритмом и протоколом Алгоритм всегда выполняется только одной стороной, поэтому в теории алгоритмов есть такое специальное понятие как «исполнитель алгоритма», а протокол всегда выполняется двумя и более сторонами. Протокол – это последовательность шагов, которые предпринимают две или большее количество сторон для совместного решения задачи. Все шаги следуют в порядке строгой очередности, и ни один из них не может быть сделан прежде, чем закончится предыдущий. - каждый участник протокола должен быть заранее оповещен о шагах, которые ему предстоит предпринять. - все участники протокола должны следовать его правилам добровольно, и без принуждения. - необходимо, чтобы протокол допускал только однозначное толкование, а его шаги были совершенно четко определены и не допускали возможности их неправильного понимания. - протокол должен содержать описание реакции его участников на любые ситуации, возникающие в ходе реализации этого протокола, иными словами, недопустимым является положение, когда для возникшей ситуации протоколом не определено соответствующее действие. Критерии отбора протоколов и алгоритмов: - Скорость работы - Безопасность Алгоритмы и протоколы является безопасными, если они работают по принципу конечного автомата. Или очень близки к конечному автомату. То есть, в них не должно быть непредусмотренных состояний. Чем ближе алгоритм или протокол к конечному автомату, тем он безопаснее для исполнителя. |