Как называется алгоритм выраженный на языке программирования

Алгоритмы: структурированные программы

Первоначальной целью теории алгоритмов является классификация всех задач на алгоритмически разрешимые и неразрешимые, т.е. на те, для которых существуют решающие их алгоритмы , и те, для которых таких алгоритмов нет. Неформально под алгоритмом $\mathcal$ можно понимать выраженный в некотором языке набор правил (предписание, рецепт, способ), позволяющий применить к исходным (входным) данным x из некоторого множества допустимых данных X последовательность дискретных действий (операций, команд), приводящую к определенному результату — выходным данным $y= \mathcal<A(x)$ из некоторого множества Y . В этом случае говорят, что алгоритм $\mathcal$ вычисляет функцию $F(x)= \mathcal(x)$ типа X -> Y . Это нестрогое определение вполне подходит в тех случаях, когда для некоторой функции нам предъявляется » объект «, называемый алгоритмом ее вычисления (например, алгоритм Эвклида для вычисления наибольшего общего делителя двух целых чисел), и можно легко проверить, позволяет ли он действительно вычислить требуемую функцию. Однако оно совершенно не годится для доказательства того, что для заданной функции никакого алгоритма нет.

Начиная с тридцатых годов ХХ века, был предпринят ряд исследований для формализации понятия алгоритма . Перечислим некоторые из предложенных разными авторами в разное время формальных моделей: машины Тьюринга-Поста, частично-рекурсивные функции (Гедель, Клини), -исчисление (Черч, Клини), итеративные автоматы Неймана , нормальные алгорифмы Маркова, счетчиковые автоматы Минского, автоматы на графах Колмогорова-Барздиня и др. Заложенные в них идеи в значительной степени повлияли затем на архитектуру и языки программирования реальных компьютеров (например, на базе -исчисления построен широко применяемый в задачах искусственного интеллекта язык ЛИСП , а из нормальных алгорифмов Маркова произошел хорошо подходящий для текстовой обработки язык РЕФАЛ). Каждый из многочисленных языков программирования также задает некоторую формальную модель алгоритмов . Мы вначале рассмотрим один из простейших таких языков — простые структурированные программы . А затем сравним их с двумя другими моделями алгоритмов : описаниями частично рекурсивных функций и машинами Тьюринга.

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

Напомним, что через N обозначается множество натуральных чисел, т.е. N= . Для частичной n — местной арифметической функции f: N n -> N через $\Delta _<f>» /> обозначим область ее определения. Чтобы указать, что f не определена на некотором наборе чисел a1. an будем писать <img decoding=$ , а если f на этом наборе определена, то будем писать $f(a_,\dots , a_) < \infty$ . Таким образом, $\delta _<f>=\< (a_,\dots , a_) | f(a_,\dots , a_) < \infty \>» />. <h4>Структурированные программы</h4> В этом разделе рассмотрим в качестве средства описания алгоритмов структурированные программы . Они вычисляют функции, используя минимальные средства: элементарные присваивания , условные операторы и циклы . Определим вначале синтаксис структурированных программ . Зафиксируем для этого некоторое счетное множество имен переменных Var , которые будут использоваться в программах. Как обычно, будем считать, что оно включает имена x, x1,x2. , y, y1. z,z1. . и т.п. В последующих определениях x, y, z — это произвольные переменные из Var . Определение 7.1. Оператор присваивания . Присваивание — это выражение одного из следующих трех видов: <ul> <li>x := x+1</li> <li>x := 0</li> <li>x := y .</li> </ul> Определение 7.2. Условия. Условие — это выражение одного из двух видов: Структурированные программы определяются индуктивно. Определение 7.3. Структурированные программы . <ul> <li>Каждое присваивание — это структурированная программа .</li> <li>Если <img decoding=$ — структурированные программы , то и $\Pi = \Pi _<1>; \Pi _» /> — это структурированная программа .</li> <li>Если <img decoding=$ — структурированные программы , а $\Phi$ — это условие, то

$\Pi= \mbox< если > \Phi \mbox < то >\Pi_1 \mbox < иначе >\Pi_2 \mbox< конец >» /> является структурированной программой . Если <img decoding=$ — это условие, то

$\Pi= \mbox< пока > \Phi \mbox< делай >\Pi_1″ /> все является структурированной программой . Конструкция в п. (б) называется последовательным применением или композицией программ <img decoding=$ — условие цикла , а $\Pi _<1>» /> — тело цикла . С помощью структурированных программ (далее называемых просто программами) вычисляются (частичные) функции от натуральных аргументов, принимающие натуральные значения. С каждой программой <img decoding=$ свяжем естественным образом множество входящих в нее переменных $Var_<\Pi >» /> (определите это множество индукцией по построению программы). В процессе работы программа изменяет значения этих переменных . Операционная семантика задает правила такого изменения. Определение 7.4. Состояние — это отображение <img decoding=$ из множества переменных Var во множество N . Для $x \in Var$ через $\sigma (x)$ обозначим значение переменной x в состоянии $\sigma.$ Через S обозначим множество всех состояний.

Разумеется, при рассмотрении конкретной программы $\Pi$ нас будут интересовать значения переменных из $Var_<\Pi >» />. Определение 7.5. Операционная семантика программы <img decoding=$ — это отбражение (вообще говоря, частичное) типа S -> S , которое программа $\Pi$ индуцирует на множестве всех состояний . Через $\Pi (\sigma )$ обозначим состояние — результат применения программы $\Pi$ к состоянию $\sigma$ . Оно определяется индукцией по построению программы.

$( x := x+1)(\sigma ) = \sigma _$ , где $\sigma _(y)=\sigma (y)$ при $y \ne x$ , и $\sigma _(x)=\sigma (x)+1$ .
$( x := 0)(\sigma ) = \sigma _$ , где $\sigma _(y)=\sigma (y)$ при $y \ne x$ , и $\sigma _(x)=0$ .
$( x := y)(\sigma ) = \sigma _$ , где $\sigma _(z)=\sigma (z)$ при $z \ne x$ , и $\sigma _(x)=\sigma (y)$
Пусть $\Pi =\Pi _;\Pi _$ . Тогда $\Pi (\sigma )=(\Pi _;\Pi _)(\sigma )=\Pi _(\Pi _(\sigma ))$ , при этом, если $\Pi _(\sigma )=\infty$ или $\sigma _=\Pi _(\sigma )$ и $\Pi _(\sigma _)=\infty$ , то и $\Pi (\sigma )=\infty$ .
Пусть $\Pi =$ если x = y то $\Pi _$ иначе $\Pi _$ конец. Тогда

$\Pi(\sigma)= \left\<\begin \Pi_1(\sigma), & \textit\ \Pi_1(\sigma)< \infty \ \textit< и >\ \sigma(x)=\sigma(y)\\ \Pi_2(\sigma), & \textit\ \Pi_2(\sigma)< \infty \ \textit< и >\ \sigma(x)\neq \sigma(y)\\ \infty & \textit \end \right.» /> Пусть <img decoding=$ если x < y то $\Pi _<1>» />иначе<img decoding=$ пока x = y делай $\Pi _$ все. Тогда при $\sigma (x) \ne \sigma (y)$ $\Pi (\sigma )= \sigma$ , а при $\sigma (x) = \sigma (y) \Pi (\sigma )$ — это первое такое состояние $\sigma _$ в последовательности состояний $\sigma _=\sigma , \sigma _=\Pi (\sigma _),\dots , \sigma _=\Pi (\sigma _).$ ., что при i состояния $\sigma _$ определены, при i , и $\sigma _(x) \ne \sigma _(y)$ .

Семантику для цикла с условием x < y определите самостоятельно (см. задачу 7.1).

Пусть $\Pi$ — программа , $Var_<\Pi >» /> — множество ее переменных . Выделим среди эти переменных некоторое подмножество входных переменных x1. xn и одну результирующую (выходную) переменную y (она может быть одной из входных). Переменные из <img decoding=$ Обозначение Описание Примечания Начало и конец алгоритма Ввод и вывод данных. Вывод данных иногда обозначают иначе:

Приведем пример описания алгоритма суммирования двух величин в виде блок-схемы:

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

Программист имеет возможность конструировать и использовать нетипичные алгоритмические структуры, однако, в этом нет необходимости. Любой сколь угодно сложный алгоритм может быть разработан на основе трёх типовых структур: следования, ветвления и повторения. При этом структуры могут располагаться последовательно друг за другом или вкладываться друг в друга.

Линейная структура (следование).

Наиболее простой алгоритмической структурой является линейная. В ней все операции выполняются один раз в том порядке, в котором они записаны.

В полном ветвлении предусмотрено два варианта действий исполнителя в зависимости от значения логического выражения (условия). Если условие истинно, то выполняться будет только первая ветвь, иначе только вторая ветвь.

Вторая ветвь может быть пустой. Такая структура называется неполным ветвлением или обходом.

Из нескольких ветвлений можно сконструировать структуру «выбор» (множественное ветвление), которая будет выбирать не из двух, а из большего количества вариантов действий исполнителя, зависящих от нескольких условий . Существенно, что выполняется только одна ветвь — в такой структуре важное значение приобретает порядок следования условий: если выполняются несколько условий, то сработает только одно из них — первое сверху.

Цикл (повторение).

Цикл позволяет организовать многократное повторение одной и той же последовательности команд — она называется телом цикла. В различных видах циклических алгоритмов количество повторений может зависеть от значения логического выражения (условия) или может быть жестко задано в самой структуре. Различают циклы : « д о» , « п ока» , циклы со счётчиком . В циклах « д о» и « п ока» логическое выражение (условие) может предшествовать телу цикла (цикл с предусловием) или завершать цикл (цикл с послеусловием).

Ц иклы « д о» — повторение тела цикла до выполнения условия :

Ц иклы « п ока» — повторение тела цикла пока условие выполняется ( истинно ):

Ц иклы со счётчиком (с параметром) – повторение тела цикла заданное число раз :

Вспомогательный алгоритм (подпрограмма, процедура).

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

Методы разработки сложных алгоритмов.

Существует два метода разработки сложных алгоритмов:

Метод последовательной детализации задачи («сверху-вниз») состоит в том, что исходная сложная задача разбивается на подзадачи. Каждая из подзадач рассматривается и решается отдельно. Если какие-либо из подзадач сложны, они также разбиваются на подзадачи. Процесс продолжается до тех пор, пока подзадачи не сведутся к элементарным. Решения отдельных подзадач затем собираются в единый алгоритм решения исходной задачи. Метод широко используется, так как позволяет вести разработку общего алгоритма одновременно нескольким программистам, решающим локальные подзадачи. Это необходимое условие быстрой разработки программных продуктов.

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

Управление — целенаправленное взаимодействие объектов, одни из которых являются управляющими, другие — управляемыми.

В простейшем случае таких объектов два:

С точки зрения информатики управляющие воздействия можно рассматривать как управляющую информацию. Информация может передаваться в форме команд. Последовательность команд по управлению объектом, приводящая к заранее поставленной цели, называется алгоритмом управления. Следовательно, объект управления можно назвать исполнителем управляющего алгоритма. В рассмотренном примере, управляющий объект работает «не глядя» на то, что происходит с управляющим объектом (управление без обратной связи). Такая схема управления называется незамкнутой. Другая схема управления может учитывать информацию о процессах, происходящих в объекте управления:

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

Более подробно процессы управления изучаются рассматриваются кибернетикой. Эта наука утверждает, что самые разнообразные процессы управления в обществе, природе и технике происходят сходным образом, подчиняются одним и тем же принципам.

Языки программирования

Язык программирования – набор правил записи алгоритмических структур и данных.

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

В 60 – 70-е годы прошлого века стали появляться языки высокого уровня – формальные языки, позволяющие записывать алгоритмы в привычном для человека виде. Такие языки строились на основе использования определённого набора символов – алфавита и строгих правил построения команд – синтаксиса. Широкое распространение получили процедурные языки высоко уровня. Самые известные процедурные языки — Basic и Pascal . Они развивались длительное время, и последние версии этих языков используются и сейчас ( Qbasic , TurboPascal ). В них широко используются команды (операторы), реализующие типовые алгоритмические структуры. Для ввода и редактирования такой программы используется подобие текстового редактора. Для исполнения такой программы компьютер с помощью специальной программы – транслятора (компилятора или интерпретатора) осуществляет перевод программы с языка высокого уровня в язык машинных команд, при этом компьютер должен проверять программу на наличие ошибок и сообщать о них программисту. Таким образом, для создания компьютерной программы нужны другие компьютерные программы!

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

В настоящее время наибольшей популярностью пользуются системы объектно-ориентированного визуального программирования ( Visual Basic , Delphi ). Разработка программы с помощью такой системы программирования состоит из двух этапов:

создание в визуальном режиме элементов графического интерфейса программы;
разработка программного кода.

Такой подход существенно облегчает создание программ, так как разработка графического интерфейса вручную (в процедурных языках) сложный и трудоёмкий процесс.

Алгоритмы и структуры данных. Лекция 1. Общие представления о алгоритмах и структурах данных

2. Лекция 1. Общие представления о алгоритмах и структурах данных

3. Что такое алгоритм

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

4. Формы записи вычислительных алгоритмов

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

5. Формы записи вычислительных алгоритмов

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

6. Структурная классификация алгоритмов

Алгоритмы с линейной структурой (или просто
— линейные алгоритмы).
Характерной особенностью алгоритмов этого
типа является то, что все операции в них
выполняются строго последовательно, без
пропусков или повторений.

7. Структурная классификация алгоритмов 2

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

8. Структурная классификация алгоритмов 3

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

9. Структурная классификация алгоритмов 4

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

10. Общая классификация алгоритмов 5

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

11. Свойства алгоритмов

Конечность
Алгоритм должен всегда заканчиваться после выполнения конечного числа
шагов
Число шагов может очень большим, например миллионы или миллиарды, но
обязательно конечным
Определенность
Каждый шаг алгоритма должен быть точно определен.
Действия, которые нужно выполнить, должны быть строго и недвусмысленно
определены для каждого возможного случая.
На практике алгоритмы могут описываться и на обычном языке, и на
формализованных псевдоязыках так и на языках программирования. Метод
вычислений, выраженный на языке программирования, называется
программой.
Ввод
Алгоритм имеет конечное возможно, равное нулю) число входных данных,
которые задаются до начала его работы или определяются динамически во
время его работы. Эти входные данные берутся из определенного набора
объектов. Например, из множества целых положительных чисел.

12. Свойства алгоритмов 2

Вывод
У алгоритма есть одно или несколько выходных данных,
т. е. величин, имеющих вполне определенную связь с входными данными.
У алгоритма Евклида имеется только одно выходное значение, а
именно – наибольший общий делитель двух входных значений.
Эффективность
Алгоритм обычно считается эффективным, если все его операторы
достаточно просты для того, чтобы их можно было точно выполнить в
течение конечного промежутка времени с помощью карандаша и бумаги. В
алгоритме Евклида используются только следующие операции: деление
одного целого положительного числа на другое, сравнение с нулем и
присвоение одной переменной значения другой. Эти операции являются
эффективными, так как целые числа можно представить на бумаге с
помощью конечного числа знаков и так как существует по меньшей мере
один способ деления одного целого числа на другое («алгоритм деления»). Но
те же самые операции были бы неэффективными, если бы они
выполнялись над действительными числами, представляющими собой
бесконечные десятичные дроби, либо над величинами, выражающими длины
физических отрезков прямой, которые нельзя измерить абсолютно точно.

13. Анализ алгоритмов 1

Мера эффективности — определение затрат времени,
действительное время, затраченное на выполнение
алгоритма в каждом отдельном случае запуска с
различными исходными данными.
Измерения должны проводиться с достаточной точностью
с помощью системных вызовов, встроенных в язык или
операционную систему, для которой написан данный
алгоритм
Для решения этой задачи можно провести ряд
экспериментов, в которых будет использовано различное
количество исходных данных. Далее полученные
результаты наглядно представляются с помощью
графика, где каждый случай выполнения алгоритма
обозначается с помощью точки, координата х которой
равна размеру исходных данных n, а координата у –
времени выполнения алгоритма t.

14. Анализ алгоритмов 2

15. Анализ алгоритмов 3

Три основных ограничения в экспериментальных
исследованиях:
• эксперименты могут проводиться лишь с использованием
ограниченного набора исходных данных; результаты,
полученные с использованием другого набора, не
учитываются;
• для сравнения эффективности двух алгоритмов необходимо,
чтобы эксперименты по определению времени их выполнения
проводились на одинаковом аппаратном и программном
обеспечении;
• для экспериментального изучения времени выполнения
алгоритма необходимо провести его реализацию и
выполнение.

16. Анализ алгоритмов 4

Общая методология анализа времени выполнения
алгоритмов
• учитывает различные типы входных данных;
• позволяет производить оценку относительной
эффективности любых двух алгоритмов независимо от
аппаратного и программного обеспечения;
• может проводиться по описанию алгоритма без его –
непосредственной реализации или экспериментов.
Сущность такой методологии состоит в том, что
каждому алгоритму соответствует функция, которая
представляет время выполнения алгоритма как функцию
размера исходных данных n. Наиболее распространенными
являются функции n и n2. Например, можно записать
следующее утверждение: «Время выполнения алгоритма А
пропорционально n».

17. Псевдокод

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

18. Лекция 2. Алгоритм и способ его описания

19. Этапы решения задачи

Постановка (формулировка) задачи;
• построение модели, выбор метода решения задачи;
• разработка алгоритма;
• проверка правильности алгоритма;
• реализация алгоритма;
• анализ алгоритма и его сложности;
• отладка программы, обнаружение, локализация и
устранение
возможных ошибок;
• получение результата;
• составление документации.
19

20. Что такое алгоритм

Алгоритм – строгая и четкая система правил,
определяющая последовательность действий над
некоторыми объектами и после конечного числа шагов
приводящая к достижению поставленной цели
Реализация алгоритма – процесс корректного
преобразования алгоритма в машинную программу.
Требует также построения целой системы структур
данных для представления модели.
Задача анализа алгоритма и его сложности –
получение оценок или границ для объема памяти или
времени работы алгоритма. Полный анализ способен
выявить узкие места в программах.
20

21. Свойства алгоритма

Определенность (детерминированность)
алгоритма предполагает такое составление
предписания, которое не оставляет места для
различных толкований или искажений
результата, т.е. последовательность
действий алгоритма строго и точно
определена.
21

22. Свойства алгоритма 2

Массовость определяет возможность
использования любых исходных данных из
некоторого допустимого множества.
Правило, сформулированное только для
данного случая, не является алгоритмом
(например, таблица умножения не является
алгоритмом, а правило умножения
«столбиком» есть алгоритм).
22

23. Свойства алгоритма 3

Результативность (конечность)
алгоритма означает, что при любом
допустимом исходном наборе данных
алгоритм закончит свою работу за конечное
число шагов
23

24. Классификация алгоритмов

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

25. Классификация алгоритмов

Линейные алгоритмы описывают линейный
вычислительный процесс, этапы которого
выполняются однократно и последовательно
один за другим..
25

26. Классификация алгоритмов

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

27. Классификация алгоритмов

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

28. Способы описания алгоритмов

Существуют следующие способы описания алгоритмов:
1) запись на естественном языке (словесное описание);
2) изображение в виде схемы (графическое описание);
3) запись на алгоритмическом языке (составление программы).
Способы словесного описания алгоритмов отличаются применяемыми
метаязыками (языки, предназначенные для описания языка
программирования).
Например, словесное описание алгоритма решения квадратного
уравнения a · x2 + b · x + c = 0 будет выглядеть следующим образом:
1) D := b2 – 4 a c;
2) если D < 0, идти к 4;
3)
x1 := (–b + (D)1/2 ) / (2 a);
x2 := (–b – D1/2 ) / (2 a);
4) Останов
Недостаток описания на естественном языке – плохая наглядность
28

29. Графическое описание алгоритма

30. Блок-схема алгоритма нахождения максимального из трех заданных чисел

31. Блок-схема алгоритма вычисления графика функции в заданном интервале

32. Вычисление значения функции с переменным количеством шагов

Y = sin x = x – x3 / 3! + x5 / 5! – x7 / 7! + … .
32

33. Основные понятия

Абстрактный тип данных АТД (формально введен в
1974 г. Б.Лисков.)
Но фактически использовалось Кнутом начиная с 1968.
АТД – класс абстрактных объектов, которые
полностью характеризуется операциями, которые
можно производить с этим объектами.
Полезность для программиста: не использует ничего
кроме операций с объектами
33

34. Основные понятия

Линейно связанный список (linked list) – набор
элементов, последовательно связанных друг с другом
так, как будто они находятся на одной линии.
Линейная связь — для каждого элемента списка, кроме
первого и последнего можно определить свойство
следует или предшествует, причем предшественник
или последующий элемент может быть один и только
один.
Массив – частный случай списка (порядок через индекс)
34

35. Операции со списком

1) Доступ к элементам:
n = first(L)
n = last(L)
n = next(L,n)
n = prev(L,n)
2) Изменение списка:
L = insert_first(L,n) — вставка в начало
insert_last(L,n) — вставка в конец
insert_after(L,p,n) — вставка до p
insert_before(L,p,n) — вставка после p
n = remove(L,n) — удаление n из списка
3) Поиск элемента:
n = search(L,k) — поиск по ключу k
35

36. Операции со списком

Что нового по сравнению с массивами?
У массива есть размер и произвольный доступ.
Операция
insert_
время выполнения O(N) для массива.
У списков есть реализация, в которой операции вставки имеют
время выполнения O(1).
36

37. Операции со списком

Пример
[ ann, tennis, tom, skiing ]
[ ]
Элемент ann – голова списка (head)
Список – [tennis, tom, skiing] – хвост (tail)
Хвост – всегда список.
37

38. Операции со списком

Пример
[ ann, tennis, tom, skiing ]
[ ]
Элемент ann – голова списка (head)
Список – [tennis, tom, skiing] – хвост (tail)
Хвост – всегда список.
38

39. Реализация списка

На С
typedef struct list_tag int data; // здесь может быть, что угодно
struct list_tag *next;
> list;
Для последнего элемента next == NULL.
Инициализация списка
list * L = 0;
39

40. Реализация списка

1) Операции rst и next
list * first(list*L) < return L; >
list * next(list*L) < return L->next; >
2) Операция last
list * last(list*L)
while( L->next ) L = L->next;
return L;
>
Алгоритм прохода по списку. Операция prev требует того
же.
40

41. Алгоритмы и структуры

3) Операция вставка n после p
void insert_after(list*L,list*p,list*n)
n->next = p->next;
p->next = n;
>
4) Операция вставка n до p
void insert_before(list*L, list*p, list*n)
insert_after(L,p,n);
int tmp = p->data; p->data = n->data;
n->data = tmp;
>
Исключение: если n->next != NULL. Или n == L.
41

42. Реализация списка

5) Операция remove
list* remove(list*L, list*n)
list * r = n->next;
// меняем данные со следующим
int data = r->data; r->data = n->data; n->data = data;
// удаляем после n
n->next = r->next; r->next = NULL;
return r;
>
Исключение: что будет, если n == L. Или n – последний. 42

43. Реализация списка. Важные выводы

Все рассмотренные выше операции имеют сложность
О(1). Кроме особых случаев. При этом считаем, что обмен
стоит меньше, чем О(N). Иначе нужна реализация класса
О(N), чтобы не было обмена. Операция добавления в конец
тоже класса О(N)

44. Реализация списка. Продолжение 6

6) Операция search
list* search(list*L, int key)
do if( L->data == key ) return L;
L = L->next;
> while( L->next );
return 0;
>
Сложность операции О(N).

45. Реализация списка. Продолжение 7 и 8

Вспомогательные операции – создание и уничтожение списков
Конструкторы и деструкторы
7) Операция создания элемента (= одноэлементного списка)
list* create(int data)
list *n = malloc(sizeof(list));
n->next = 0;
n->data = data;
return n;
>
8) Операция удаления списка
list* destroy(list*L)
while( L != NULL ) list * n = L->next;
free(n);
L = n;
>
return 0;
>
Сложность операции О(N).

46. Реализация двусвязного списка

47. Реализация двусвязного списка

Определение списка
typedef struct list_tag int data; // здесь может быть, что угодно
struct list_tag *next,*prev;
> list;
Инициализация списка (создание списка)
list* create(void)
list *head = malloc(sizeof(list));
head->next=head->prev=head;
return head;
>

48. Реализация двусвязного списка

1) Операции rst и next
int isempty(list*L)
return L->next == L ? 1 : 0;
>
list * first(list*L)
return isempty(L) ? 0 : head->next;
>
list * next(list*L) < >
list * prev(list*L) < >
Исключения: если next для последнего или prev для первого
2) Операция last
list * last(list*L)
return isempty(L) ? 0 : head->prev;
>
Не нужен алгоритм прохода по списку.

49. Реализация двусвязного списка

3) Операция вставка n после p
void insert_after(list*L,list*p,list*n)
n->next = p->next; n->prev = p;
p->next = n->next->prev = n;
>
4) Операция вставка n до p
void insert_before(list*L, list*p, list*n)
n->next = p; n->prev = p->prev;
n->prev->next = p->prev = n;
>

50. Реализация двусвязного списка

5) Операция remove
void remove(list*L, list*n)
n->prev->next = n->next;
n->next->prev = n->prev;
n->prev = n->next = 0;
>
Исключение: что будет, если n == L. Или n == NULL.

51. Реализация двусвязного списка

Вспомогательные операции – создание и уничтожение списков
Конструкторы и деструкторы
7) Операция создания элемента (не списка )
list* create_elem(int data)
list *n = malloc(sizeof(list));
n->next = n->prev = 0;
n->data = data;
return n;
>
8) Операция удаления списка
void destroy(list*L)
while( !isempty(L)) list * n = first(L);
remove(n);
free(n);
>
free(L);
>
Сложность операции О(N).
.

52. Реализация двусвязного списка

Пример
int main(void)
list *head = list_create(0),*n;
int i,N = 6;
for(i=0;i printf(«%d\n»,n->data);
list_insert_after(head,n);
>
for(n = head; n; n = n->next) printf(«%d\n»,n->data);
>
>.

53. Стеки

Определение стека
Стек – это специальный вид списка, для которого все операции
выполняются исключительно с первым элементом списка. Вершина
стека (top).
Стек также может называться как LIFO (Last Input First Output).
Абстракция стека имеет большое значение в информатике.
Стековая память программы, стековая виртуальная машина,
стековая архитектры ЭВМ, вычисление арифметиченских
выражений.
Достоинство стека — это простота операций и скорость их
выполнений.

54. Стек подобен железнодорожному депо

55. Операции со стеком

Операции со стеком
Доступ к элементам и изменение стека:
n = pop(S) — извлечение элемента n из стека S
push(S, n) — вставка элемента n в стек S
Остальные операции вспомогательные и зависят от
реализации

56. Реализация стека

Реализация стека
Можно просто использовать односвязный список. Сделаем через
свою реализацию.
typedef struct stack_tag stack_t;
struct stack_tag void* data;
stack_t * next;
>;
Пример использования (вывод чисел в обратном порядке)
stack_t *s = 0;
for(i=0;i <21;i++) a = i*i;
PUSH(s,&a,sizeof(int));
>
while( !EMPTY(s) ) POP(s,&a,sizeof(int));
printf(» a = %d\n»,a);
>

57. Реализация стека 2

Реализация стека
void PUSH(stack_t*S,void*data,int size)
stack_t*n=malloc(sizeof(stack_t)+size);
n->data = n + sizeof(stack_t);
memcpy(n->data, data, size);
n->next = S; S = n;
>
void POP(stack_t*S,void*data,int size)
stack_t *n = S;
S = S->next;
memcpy(data, n->data,size);
free(n);
>
int EMPTY(stack_t*s) < return !s; >
В первой функции две ошибки – с распределением памяти и
возвратом. Во второй – ошибка с возвратом.

58. Реализация стека 3

Реализация стека
1) Память под данные должна распределяться так
n->data = n + 1;
а не так
n->data = n + sizeof(stack_t);
2) Изменение головы стека требует его возврата. Итого правильный
вариант
stack_t *PUSH(stack_t*S,void*data,int size)
stack_t*n=malloc(sizeof(stack_t)+size);
n->data = n + 1;
memcpy(n->data, data, size);
n->next = S;
return n;
>
s = PUSH(s,&a,sizeof(int));
то же с POP

59. Реализация стека 4

Реализация стека
Используем макросы
#define PUSH(S,d,size) do < \
STACK*n=malloc(sizeof(STACK)+size); \
n->data = n + 1; \
memcpy(n->data, (d), size); \
n->next = S; S = n; \
> while(0)
#define POP(S,d,size) do < \
STACK *n = S; \
S = S->next; \
memcpy((d), n->data,size); \
free(n); \
> while(0)
#define EMPTY(S) (S==0 ? 1 : 0)

60. Очереди

Определение очереди
Очередь – это специальный вид списка, для которого добавление
элемента осуществляется в конец списка, а извлечение – с начала
списка.
Очередь также может называться как FIFO (First Input First Output).
Абстракция очереди имеет большое значение в информатике.
Очередь заданий (процессов) в операционных системах, очередь
сообщений в программах или устройствах (буфер клавиатуры)

61. Реализация очереди

Реализация очереди
Можно просто использовать односвязный список. Но операция
добавления в конец будет О(N).
Можно через двусвязный список с фиктивным первым узлом (как
выше). Но проход из конца в начало не используется в очереди.
Указатель prev – лишний и лишние операции.

62. Реализация очереди 2

Реализация очереди
Сделаем через свою реализацию.
typedef struct queue_link_tag queue_link;
struct queue_link void* data;
queue_link * next;
>;
typedef struct queue_tag queue_t;
struct queue_t int size;
queue_link * head,*tail;
>;
Пример использования (вывод чисел в том же порядке)
queue_t *q = create_queue(sizeof(int));
for(i=0;i <21;i++) a = i*i;
ADD(q,&a);
>
while( !EMPTY(q) ) REMOVE(q,&a);
printf(» a = %d\n»,a);
>

63. Реализация очереди 3

Реализация очереди
void ADD(queue_t*q,void*data)
queue_link*n=malloc(sizeof(queue_link)+q->size);
n->data = n + 1;
memcpy(n->data, data, q->size);
q->tail->next = n;
n->next = 0;
q->tail = n;
>
void REMOVE(queue_t*q,void*data)
stack_link *n = q->head;
q->head = q->head->next;
memcpy(data, n->data,q->size);
free(n);
>

64. Деки

Определение дека
Дек (deque — double ended queue) – это специальный вид списка, для
которого как добавление элемента, так и извлечение могут
осуществляться и с конца, и с начала списка. (Двусторонняя
очередь)
Четыре операции — аналогичные стеку и очереди

65. Задание. Деки

1) Реализовать все операции для списка и двусвзяного списка в
данных выше реализациях
2) Реализовать абстрактный тип дек.

66. Метод пузырька

#include
int main() int n, i, j;
scanf_s(«%d», &n);
int a[n];
// считываем количество чисел n
// формируем массив n чисел
for(i = 0 ; i < n; i++) scanf_s("%d", &a[i]);
>
for(i = 0 ; i < n - 1; i++) // сравниваем два соседних элемента.
for(j = 0 ; j < n - i - 1 ; j++) if(a[j] > a[j+1]) // если они идут в неправильном порядке, то
// меняем их местами.
int tmp = a[j];
a[j] = a[j+1] ;
a[j+1] = tmp;
>
>
>
>
Понятно, что после первого «пробега» самый большой элемент массива окажется на последнем месте. После
второго пробега мы будем уверены, что второй по величине элемент находится на предпоследнем месте .

67. Метод вставки

#include
int main() int n, i, j;
scanf_s(«%d», &n);
int a[n];
// считываем количество чисел n
// формируем массив n чисел
for(i = 0 ; i < n; i++) scanf_s("%d", &a[i]);
>
.