Презентация по информатике на темуАлгоритм

Алгоритм Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.Ранее в русском языке писали «алгорифм», сейчас такое написание используется редко, но, тем не менее, имеет место исключение (нормальный алгорифм Маркова). История терминаСовременное формальное определение вычислительного алгоритма было дано в 30—50-е годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.Само слово «алгоритм» происходит от имени хорезмского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми (алгоритм — аль-Хорезми). Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, персидский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Например, существует версия происхождения слова algorism из греческих algiros (больной) и arithmos (число). Из такого объяснения не очень ясно, почему числа именно «больные». Энциклопедический словарь Брокгауза и Ефрона предлагает такую трактовку: алгорифм (кстати, до революции использовалось написание алгориѳм, через фиту) производится «от арабского слова Аль-Горетм, то есть корень».Упомянутый выше перевод сочинения аль-Хорезми стал первой ласточкой, и в течение нескольких следующих столетий появилось множество других трудов, посвящённых всё тому же вопросу — обучению искусству счёта с помощью цифр. И все они в названии имели слово algoritmi или algorismi. Свойства алгоритмаМассовость - алгоритм должен быть применен для класса подобных задач.Дискретность - алгоритм состоит из ряда шагов.Определенность - каждый шаг алгоритма должен пониматься однозначно и не допускать произвола.Результативность - алгоритм должен приводить к решению поставленной задачи за конечное число шагов Виды алгоритмаЛинейный - алгоритм, в котором все предписания (шаги) выполняются так, как записаны, без изменения порядка следования, строго друг за другом.Разветвляющийся - алгоритм, в котором выполнение того или иного действия (шага) зависит от выполнения или не выполнения какого-либо условия.Циклический - алгоритм, в котором некоторая последовательность действий повторяется несколько раз. Блок-схема алгоритма — графическое изображение алгоритма в виде связанных между собой с помощью стрелок (линий перехода) и блоков — графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия. Для записи алгоритмов в школьном курсе часто используется два языка – псевдокод и язык блок-схем. Блок-схемы – это способ графического представления алгоритма, в котором шаги изображаются в виде блоковразличной формы, соединенных между собой стрелками. Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой строны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя.Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются.Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций. Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами  нач  и  кон  — телом алгоритма.В предложении алг после названия алгоритма в круглых скобках указываются характеристики (арг, рез) и тип значения (цел, вещ, сим, лит или лог) всех входных (аргументы) и выходных(результаты) переменных. При описании массивов (таблиц) используется служебное  слово таб, дополненное граничными парами по каждому индексу элементов массива.Примеры предложений алг:                     алг Объем и площадь цилиндра ( арг вещ R, H,  рез вещ V, S )                   алг Корни КвУр ( арг вещ а, b, c,  рез вещ x1, x2,  рез лит t )                   алг Исключить элемент ( арг цел N,  арг рез вещ таб А[1:N] )                   алг Диагональ ( арг цел N,  арг цел таб A[1:N,  1:N],  рез лит Otvet )Предложения дано и надо не обязательны. В них рекомендуется записывать утверждения, описывающие состояние среды исполнителя алгоритма, например:алг Замена (арг лит Str1, Str2, арг рез лит Text)     дано | длины подстрок Str1 и Str2 совпадают     надо | всюду в строке Text подстрока Str1 заменена на Str2 алг Число максимумов (арг цел N, арг вещ таб A[1:N], рез цел K)     дано | N>0     надо | К — число максимальных элементов в таблице А алг Сопротивление (арг вещ R1, R2, арг цел N, рез вещ R)     дано | N>5, R1>0, R2>0     надо | R — сопротивление схемы Здесь в предложениях дано и надо после знака "|" записаны комментарии. Комментарии можно помещать в конце любой строки. Они не обрабатываются транслятором, но существенно облегчают понимание алгоритма. Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т.е. основных) элементов. Естественно, что при таком подходе к алгоритмам изучение основных принципов их конструирования должно начинаться с изучения этих базовых элементов. Для их описания будем использовать язык схем алгоритмов и школьный алгоритмический язык.Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование,   ветвление,   цикл.Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.1. Базовая структура  "следование". Образуется последовательностью действий, следующих одно за другим:Школьный алгоритмический языкЯзык блок-схемдействие 1действие 2. . . . . . . . .действие n2. Базовая структура  "ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует в четырех основных вариантах: На каждом шаге вычислений происходит последовательное приближение к искомому результату и проверка условия достижения последнего.Пример. Составить алгоритм вычисления бесконечной суммы  с заданной точностью    (для данной знакочередующейся бесконечной суммы требуемая точность будет достигнута, когда очередное слагаемое станет по абсолютной величине меньше ).Вычисление сумм — типичная циклическая задача. Особенностью же нашей конкретной задачи является то, что число слагаемых (а, следовательно, и число повторений тела цикла) заранее неизвестно. Поэтому выполнение цикла должно завершиться в момент достижения требуемой точности.При составлении алгоритма нужно учесть, что знаки слагаемых чередуются и степень числа  х  в числителях слагаемых возрастает.Решая эту задачу "в лоб" путем вычисления на каждом  i-ом шаге частичной суммы  S:=S + ((-1)**(i-1)) * (x**i) / i ,мы получим очень неэффективный алгоритм, требующий выполнения большого числа операций. Гораздо лучше организовать вычисления следующим образом: если обозначить числитель какого-либо слагаемого буквой  р , то у следующего слагаемого числитель будет равен  —р*х   (знак минус обеспечивает чередование знаков слагаемых), а само слагаемое  m  будет равно  p/i , где  i  — номер слагаемого. При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается определенный произвол при изображении команд. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить алгоритм.Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы — компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем.Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера. Язык ассемблера позволяет программисту пользоваться текстовыми мнемоническими (то есть легко запоминаемыми человеком) кодами, по своему усмотрению присваивать символические имена регистрам компьютера и памяти, а также задавать удобные для себя способы адресации. Кроме того, он позволяет использовать различные системы счисления (например, десятичную или шестнадцатеричную) для представления числовых констант, использовать в программе комментарии и др.Программы, написанные на языке ассемблера, требуют значительно меньшего объема памяти и времени выполнения. Знание программистом языка ассемблера и машинного кода дает ему понимание архитектуры машины. Несмотря на то, что большинство специалистов в области программного обеспечения разрабатывают программы на языках высокого уровня, таких, как Object Pascal или C, наиболее мощное и эффективное программное обеспечение полностью или частично написано на языке ассемблера.Языки высокого уровня были разработаны для того, чтобы освободить программиста от учета технических особенностей конкретных компьютеров, их архитектуры. В противоположность этому, язык ассемблера разработан с целью учесть конкретную специфику процессора. Сдедовательно, для того, чтобы написать программу на языке ассемблера для конкретного компьютера, важно знать его архитектуру [57].В качестве примера приведем программу на языке ассемблера для IBM PC. Программа вычисляет значение a = b + c для целых a, b и c: