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

• 1 слайд

  Алгоритм
  
  

• 2 слайд

  Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.
  Ранее в русском языке писали «алгорифм», сейчас такое написание используется редко, но, тем не менее, имеет место исключение (нормальный алгорифм Маркова).
  
  

• 3 слайд

• 4 слайд

  История термина
  Современное формальное определение вычислительного алгоритма было дано в 30—50-е годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.
  Само слово «алгоритм» происходит от имени хорезмского учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми (алгоритм — аль-Хорезми). Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, персидский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»).
  

• 5 слайд

• 6 слайд

  Например, существует версия происхождения слова algorism из греческих algiros (больной) и arithmos (число). Из такого объяснения не очень ясно, почему числа именно «больные». Энциклопедический словарь Брокгауза и Ефрона предлагает такую трактовку: алгорифм (кстати, до революции использовалось написание алгориѳм, через фиту) производится «от арабского слова Аль-Горетм, то есть корень».
  Упомянутый выше перевод сочинения аль-Хорезми стал первой ласточкой, и в течение нескольких следующих столетий появилось множество других трудов, посвящённых всё тому же вопросу — обучению искусству счёта с помощью цифр. И все они в названии имели слово algoritmi или algorismi.
  
  

• 7 слайд

• 8 слайд

  Свойства алгоритма
  Массовость - алгоритм должен быть применен для класса подобных задач.
  Дискретность - алгоритм состоит из ряда шагов.
  Определенность - каждый шаг алгоритма должен пониматься однозначно и не допускать произвола.
  Результативность - алгоритм должен приводить к решению поставленной задачи за конечное число шагов
  
  

• 9 слайд

• 10 слайд

  Виды алгоритма
  Линейный - алгоритм, в котором все предписания (шаги) выполняются так, как записаны, без изменения порядка следования, строго друг за другом.
  Разветвляющийся - алгоритм, в котором выполнение того или иного действия (шага) зависит от выполнения или не выполнения какого-либо условия.
  Циклический - алгоритм, в котором некоторая последовательность действий повторяется несколько раз.
  
  

• 11 слайд

• 12 слайд

  Блок-схема алгоритма — графическое изображение алгоритма в виде связанных между собой с помощью стрелок (линий перехода) и блоков — графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия. Для записи алгоритмов в школьном курсе часто используется два языка – псевдокод и язык блок-схем. Блок-схемы – это способ графического представления алгоритма, в котором шаги изображаются в виде блоковразличной формы, соединенных между собой стрелками.
  

• 13 слайд

• 14 слайд

  Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой строны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.
  В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя.
  Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются.
  Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
  
  

• 15 слайд

• 16 слайд

  Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами  нач  и  кон  — телом алгоритма.
  В предложении алг после названия алгоритма в круглых скобках указываются характеристики (арг, рез) и тип значения (цел, вещ, сим, лит или лог) всех входных (аргументы) и выходных(результаты) переменных. При описании массивов (таблиц) используется служебное  слово таб, дополненное граничными парами по каждому индексу элементов массива.
  Примеры предложений алг: 
    
                    алг Объем и площадь цилиндра ( арг вещ 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 — сопротивление схемы
  Здесь в предложениях дано и надо после знака "|" записаны комментарии. Комментарии можно помещать в конце любой строки. Они не обрабатываются транслятором, но существенно облегчают понимание алгоритма.
  
  

• 17 слайд

• 18 слайд

  Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т.е. основных) элементов. Естественно, что при таком подходе к алгоритмам изучение основных принципов их конструирования должно начинаться с изучения этих базовых элементов. Для их описания будем использовать язык схем алгоритмов и школьный алгоритмический язык.
  Логическая структура любого алгоритма может быть 
  представлена комбинацией трех базовых структур: 
  следование,   ветвление,   цикл.Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.
  1. Базовая структура  "следование". Образуется последовательностью действий, следующих одно за другим:Школьный алгоритмический языкЯзык блок-схемдействие 1
  действие 2
  . . . . . . . . .
  действие n
  
  2. Базовая структура  "ветвление". Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует в четырех основных вариантах:
  
  

• 19 слайд

• 20 слайд

  На каждом шаге вычислений происходит последовательное приближение к искомому результату и проверка условия достижения последнего.
  Пример. Составить алгоритм вычисления бесконечной суммы 
   
  
  с заданной точностью    (для данной знакочередующейся бесконечной суммы требуемая точность будет достигнута, когда очередное слагаемое станет по абсолютной величине меньше ).Вычисление сумм — типичная циклическая задача. Особенностью же нашей конкретной задачи является то, что число слагаемых (а, следовательно, и число повторений тела цикла) заранее неизвестно. Поэтому выполнение цикла должно завершиться в момент достижения требуемой точности.
  При составлении алгоритма нужно учесть, что знаки слагаемых чередуются и степень числа  х  в числителях слагаемых возрастает.
  Решая эту задачу "в лоб" путем вычисления на каждом  i-ом шаге частичной суммы 
   
  S:=S + ((-1)**(i-1)) * (x**i) / i ,
  мы получим очень неэффективный алгоритм, требующий выполнения большого числа операций. Гораздо лучше организовать вычисления следующим образом: если обозначить числитель какого-либо слагаемого буквой  р , то у следующего слагаемого числитель будет равен  —р*х   (знак минус обеспечивает чередование знаков слагаемых), а само слагаемое  m  будет равно  p/i , где  i  — номер слагаемого.
  

• 21 слайд

• 22 слайд

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

• 23 слайд

• 24 слайд

  Язык ассемблера позволяет программисту пользоваться текстовыми мнемоническими (то есть легко запоминаемыми человеком) кодами, по своему усмотрению присваивать символические имена регистрам компьютера и памяти, а также задавать удобные для себя способы адресации. Кроме того, он позволяет использовать различные системы счисления (например, десятичную или шестнадцатеричную) для представления числовых констант, использовать в программе комментарии и др.
  Программы, написанные на языке ассемблера, требуют значительно меньшего объема памяти и времени выполнения. Знание программистом языка ассемблера и машинного кода дает ему понимание архитектуры машины. Несмотря на то, что большинство специалистов в области программного обеспечения разрабатывают программы на языках высокого уровня, таких, как Object Pascal или C, наиболее мощное и эффективное программное обеспечение полностью или частично написано на языке ассемблера.
  Языки высокого уровня были разработаны для того, чтобы освободить программиста от учета технических особенностей конкретных компьютеров, их архитектуры. В противоположность этому, язык ассемблера разработан с целью учесть конкретную специфику процессора. Сдедовательно, для того, чтобы написать программу на языке ассемблера для конкретного компьютера, важно знать его архитектуру [57].
  В качестве примера приведем программу на языке ассемблера для IBM PC. Программа вычисляет значение a = b + c для целых a, b и c:
  
  

• 25 слайд