Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Новгородский государственный университет имени Ярослава Мудрого»

Великий Новгород

Политехнический колледж

УЧЕБНОЕ ПОСОБИЕ

«ТЕОРИЯ АЛГОРИТМОВ»

Разработал:

преподаватель информатики

ПТК НовГУ

Ю.В. Алексеева

2015 г.

АННОТАЦИЯ

Учебное пособие по дисциплине «Теория алгоритмов» предназначено для студентов Политехнического колледжа НовГУ, обучающихся по специальности 230115 «Программирование в компьютерных системах».

Учебное пособие включает введение, два раздела, заключение, список литературы. В разделе 1 рассматриваются понятия алгоритма и вспомогательного алгоритма, основные алгоритмические структуры, формализация понятия «алгоритм» на примерах виртуальных машин Поста и Тьюринга. Раздел 2 посвящен методам построения алгоритмов, таким как рекурсивный метод, методы сортировки данных. Раскрыты идеи линейного и бинарного поиска, а так же методы вычисления сложности алгоритмов.

Каждый из разделов пособия содержит теоретический материал с подробно разобранными примерами. Алгоритмы решения задач представлены в виде блок-схем. Для закрепления материала в конце каждого раздела предложены задачи для самостоятельного решения.

В конце учебного пособия в Приложении представлена рабочая программа дисциплины «Теория алгоритмов» и тексты программ разобранных примеров.

Количество страниц - 77

Количество иллюстраций - 19

Количество таблиц - 3

Количество приложений - 1

Количество библиографических источников - 13

Оглавление

ВВЕДЕНИЕ

Моделирование является одним из способов познания мира. Для различных явлений и процессов могут быть использованы разные способы моделирования. Объект, который получается в результате моделирования, называется моделью. Видов моделей достаточно много, например:

Математические модели - знаковые модели, описывающие определенные числовые соотношения.

Графические модели - визуальное представление объектов. Здесь наглядность модели выходит на первый план.

Имитационные модели - модели, позволяющие наблюдать изменение поведения элементов системы, проводить эксперименты, изменять отдельные параметры модели.

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

Компьютерное моделирование - это моделирование, реализуемое с помощью компьютерной техники.

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

На сегодняшний день выбор научной и учебной литературы по теории алгоритмов очень многообразен, однако, достаточно трудно найти учебные пособия, которые были бы рассчитаны на небольшое количество часов курса и в то же время могли раскрыть основные идеи и методы теории алгоритмов. Этим и обусловлена актуальность разработки данного учебного пособия по дисциплине «Теория алгоритмов».

Учебное пособие «Теория алгоритмов» разработано в соответствии с:

• Федеральным государственным образовательным стандартом по специальности 230115 «Программирование в компьютерных системах»;

• Рабочей программой дисциплины «Теория алгоритмов».

В результате изучения дисциплины «Теория алгоритмов» студент должен:

Уметь:

- разрабатывать алгоритмы для конкретных задач;

- определять сложность работы алгоритмов.

Знать:

- основные модели алгоритмов;

- методы построения алгоритмов;

- методы вычисления сложности работы алгоритмов.

Целью данного учебного пособия является изучение и применение в дальнейшей профессиональной деятельности основ и методов теории алгоритмов.

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

1 ОСНОВЫ АЛГОРИТМИЗАЦИИ

1.1 АЛГОРИТМЫ И ВЕЛИЧИНЫ

Слово "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса аль-Хорезми (Alhorithmi), жившего в 783-850 гг. В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними "столбиком", знакомые теперь каждому школьнику. В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.

В течение длительного времени термин «алгоритм» употребляли преимущественно математики. При этом они пользовались так называемым интуитивным понятием алгоритма - заранее заданное, понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов.[1]

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

Основные результаты теории алгоритмов были получены в 30-60 годах 20 века Э.Черчем, А. Тьюрингом, А. Постом, А. Колмогоровым, А. Марковым. Введенные в рассмотренные алгоритмические модели, машины Тьюринга, Поста дали возможность устанавливать алгоритмическую разрешимость проблемы путём построения соответствующих машин логического действия.

В настоящее время понятие алгоритма является не только одним из главных понятий математики, но одним из главных понятий современной науки. Более того, с наступлением эры информатики алгоритмы становятся одним из важнейших факторов цивилизации. [1]

Определение 1. Алгоритм - конечная последовательность детерминированных арифметических и логических действий над исходными и промежуточными данными задачи обработки информации, выполнение которых приводит к правильному ее решению, т.е. получению требуемых выходных данных. [2]

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

1. Понятность. Исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как надо действовать для выполнения этого алгоритма.

2. Дискретность (прерывность, раздельность). Алгоритм должен состоять из отдельных элементарных шагов. Количество шагов должно быть конечным, т.е. после выполнения этих шагов исполнитель должен остановиться. Если действия повторяются бесконечно, говорят, что алгоритм зациклился.

3. Определённость. Последовательность шагов алгоритма должна быть детерминированной (определённой). После каждого шага либо указывается, какой шаг выполнить дальше, либо даётся команда остановки, после этого действия алгоритма считаются законченными.

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

5. Массовость. Алгоритм решения задачи должен разрабатываться в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, так называемой области применимости алгоритма.[2]

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

1. Графический (в виде блок-схемы).

2. Словесный, текстовый (в виде последовательности шагов, описывающих действия естественным языком).

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

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

Таблица 1 - Символы блок-схем алгоритмов

Линия потока

Указание последовательности связей между символами

Соединитель

Указание связи между прерванными линиями потока, связывающими символы

Пуск-остановка

Начало, конец, прерывание процесса обработки данных или выполнения программы

Комментарий

Связь между элементом схемы и пояснением

Межстраничный соединитель

Указание связи между разъединительными частями схем алгоритмов и программ, расположенных на разных листах.

Продолжение таблицы 1

Размеры символов должны удовлетворять соотношению b=1,5a, рис. 1. На этом же рисунке продемонстрирован пример использования символа «комментарий».

Функции спроса на автомобиль

Q = 0.3882-0.23*P

Рис. 1 Фрагмент блок-схемы алгоритма

Таблица 2 - Унифицированные структуры

Продолжение таблицы 2

конец

Тело цикла

условие

начало

Цикл с предусловием

Тело цикла

условие

конец

начало

Цикл с постусловием

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

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

1. Постановка задачи

2. Анализ и исследование задачи, модели

3. Разработка алгоритма

4. Программирование

5. Тестирование и отладка

6. Анализ результатов решения задачи и уточнение в случае необходимости математической модели с повторным выполнением этапов 2-5

7. Сопровождение программы

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

Задача 1.

1. Составить алгоритм приближенного вычисления квадратного корня с заданной точностью методом Ньютона.

2. Очередное значение корня вычисляется по формуле n=1, 2, …при условии, что задано начальное значение корня Первое значение корня будет равно , второе - и т.д. Корень можно считать вычисленным с заданной точностью , если модуль очередного уточнения корня |.

3. Блок-схема алгоритма на рис. 2.

Конец

Вывод

|v|

(,
x= u + v

Ввод

Начало

Рис. 2 Алгоритм вычисления квадратного корня методом Ньютона.

1.2 ЛИНЕЙНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ

Определение 2. Линейный алгоритм - это алгоритм, содержащий алгоритмическую структуру «следование.

Общий вид блок-схемы линейного алгоритма представлен в таблице 2. Рассмотрим 1-3 этапы решения задачи на ЭВМ с помощью линейного алгоритма.[2]

Задача 2.

1. Даны два действительных положительных числа a и b. Найти среднее арифметическое и среднее геометрическое этих чисел.

2. Среднее арифметическое чисел a и b определяется как
   , а среднее геометрическое как .

Блок-схема алгоритма представлена на рис.3. Начало

Конец

Ввести

Вывести

Рис. 3 Алгоритм вычисления среднего арифметического и среднего геометрического двух чисел.

1.3 ВЕТВЛЕНИЕ В ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМАХ

Определение 3. Конструкция ветвления - это часть алгоритма, в которой в зависимости от выполнения или невыполнения некоторого условия выполняется либо одна, либо другая последовательность действий. Алгоритм, в котором используется конструкция ветвления, называется алгоритмом с ветвлением.

Общий вид блок-схем алгоритма ветвления представлен в таблице 2.

Для реализации алгоритмов с разветвленной структурой в языках программирования используются условные операторы.

Рассмотрим пример решения задачи с помощью алгоритма ветвления.

Задача 3.

1. Составить алгоритм вычисления корней квадратного уравнения с действительными коэффициентами , когда .

2. Дискриминант квадратного уравнения может иметь три типа корней: разные действительные корни, если , равные действительные корни, если , и комплексные сопряженные корни, если . Разные действительные корни вычисляются по формулам . Равные корни определяются так:. Комплексные сопряженные корни вычисляются так же, как и действительные, только представляются двойкой чисел , где знак указывает на то, что - мнимая часть значения корня. В алгоритме вычисления корней на первом этапе должно быть предусмотрено вычисление значения дискриминанта и дальнейшая проверка его знака.

3. Блок-схема алгоритма вычисления корней квадратного уравнения представлена на рис.4.

4. Код программы для реализации данного алгоритма (Приложение 1, Program2.pas).

Начало

конец

Вывести корни равные x

Вывести корни дейст. x₁,x₂

Вывести корни комплекс. x₁,x₂

=k-r

=k-ir

нет

нет

да

даРис. 4 Алгоритм вычисления корней квадратного уравнения.

1.4 ЦИКЛЫ В ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМАХ

Определение 4. Циклические алгоритмы - алгоритмы, содержащие фрагменты повторения вычислений.

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

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

В итерационных циклах число повторений неизвестно, выход из цикла осуществляется при выполнении некоторого условия. В случае, когда условие проверяется до начала повторений, циклы называются с предусловием, когда же проверка происходит после очередной итерации, циклы называются с постусловием. Все арифметические циклы - это циклы с предусловием. [2]

Общий вид блок-схем циклических алгоритмов представлен в таблице 2.

Рассмотрим примеры решения задач с помощью циклических алгоритмов. В Приложении 1 представлены программы на языке Pascal, соответствующие данным задачам.

Задача 4.

1. Составить алгоритм вычисления функции .

2. . - произведение натуральных чисел 1*2*3…n, . Вычисление значения факториала можно рассматривать как последовательное повторение операции умножения предшествующего значения факториала F на очередное натуральное число.

3. схема алгоритма вычисления факториала на рис.5.

Начало

Нет

Да

Рис. 5 Алгоритм вычисления функции n!

Задача 5.

1. Составить алгоритм вычисления выражения

2. Если взять начальное значение суммы , то повторяющимся действием будет

3. схема алгоритма представлена на рис.6.

Задача 6.

1. Составить алгоритм нахождения наибольшего общего делителя двух целых чисел a и b. [6]

2. Наибольший общий делитель (НОД) двух целых чисел a и b - это наибольшее целое число, которое делит нацело оба числа. Рассмотрим способ, который называется алгоритмом Евклида. Пусть a и b одновременно не равные нулю целые неотрицательные числа и a b. Если b = 0, то НОД(a, b) =a, а если b 0, то для чисел a,b и r, где r - остаток от деления a на b, выполняется равенство НОД (a, b) = НОД(b, r). Действительно, r:=a Mod b, r:= a -(a Div b) * b. Если какое-то число делит нацело и a, и b, то из приведенного равенства следует, что оно делит нацело и число r.

3. Блок-схема алгоритма Евклида нахождения НОД и НОК двух целых чисел на рис.7.

4. Программная реализация алгоритма Евклида (Приложение 1, Evclid.pas).

Задача 7.

1. Дано натуральное число n. Требуется подсчитать количество цифр данного числа.

2. Количество цифр в числе n неизвестно, поэтому необходимо использовать цикл с предусловием. Подсчёт количества цифр можно начать с последней цифры числа, далее увеличить изначально нулевой счётчик цифр на единицу. Повторять уменьшение числа в 10 раз, пока оно не станет равным 0.

3. Блок-схема на рис.8.

Начало

Нет

Да

Рис. 6 Алгоритм вычисления выражения

Вывести

a, b, НОД,

НОК

Начало

Ввести

a, b

Да

Нет

Нет

Конец

Рис.7 Алгоритм Евклида нахождения НОД и НОК двух целых чисел

Начало

Конец

m,n,k

k

K=0

K=k+1

m=m div 10

m<>0

Рис.8 Алгоритм подсчета количества цифр в натуральном числе.

4. Программа для решения задачи 7 (подсчет количества цифр в числе) представлена в Приложении 1, Program7.pas.

1.5 МАШИНА ПОСТА

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

В теории алгоритмов существует так называемый "тезис Поста": "Всякий алгоритм представим в форме машины Поста". Этот тезис одновременно является формальным определением алгоритма. Алгоритм (по Посту) - программа для машины Поста, приводящая к решению поставленной задачи.

Тезис Поста является гипотезой. Его невозможно строго доказать (так же, как и тезис Тьюринга), потому что в нем фигурируют, с одной стороны, интуитивное понятие "всякий алгоритм", а с другой стороны - точное понятие "машина Поста". Для того чтобы опровергнуть гипотезу Поста, необходимо придумать алгоритм, который невозможно записать в виде программы для машины Поста. На сегодняшний день такого алгоритма не существует. [12]

Состав машины Поста.

Машина Поста состоит из ленты и каретки. Лента бесконечна и разделена на секции одинакового размера - ячейки.

Рис. 9. Состав машины Поста

В каждой ячейке ленты может стоять метка V либо ничего не записано.. Состояние ленты - это распределение меток по ячейкам. Состояние ленты меняется в процессе работы машины.

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

Команды машины Поста:

1. записать 1 (метку), перейти к i-й строке программы;

2. записать 0 (стереть метку), перейти к i-й строке программы;

3. сдвиг влево, перейти к i-й строке программы;

4. сдвиг вправо, перейти к i-й строке программы;

5. останов;

6. если 0, то перейти к i, иначе перейти к j.

Недопустимые действия, ведущих к аварийной остановке машины:

• попытка записать 1 (метку) в заполненную ячейку;

• попытка стереть метку в пустой ячейке;

• бесконечное выполнение (зацикливание).

Команды машины обозначают следующим образом (рис.10):

Рис. 10 Команды машины Поста

Рассмотрим несколько арифметических задач для машины Поста и их решение.[12]

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

1. На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива. (увеличение числа на 2).

Решение:

1. ? 2; 3 (команды 1 и 2 - передвигаем каретку к массиву)

2. → 1

3. → 4 (команды 3 и 4 - передвигаем каретку к концу массива)

4. ? 5; 3

5. V 6 (команды 5-7 - ставим 2 метки в конце массива)

6. → 7

7. V 8

8. !

2. Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива. (сложение двух чисел)

Решение.

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

Решение.

4. На ленте заданы два массива - m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива.

Решение:

1. → 2 (команды 1-3: ищем левую метку массива m)

2. ? 3; 1

3. ← 4

4. X 5 (стираем левую метку массива m)

5. ? 6; 7

6. → 5

7. X 8 (стираем левую метку массива n)

8. → 9

9. ? 12; 10 (стерли последнюю метку в массиве n?)

10. ←11 (ищем левый край массива m)

11. ? 10; 4

12. !

5. На ленте задан массив. Удвоить массив в два раза. Каретка располагается над первой ячейкой массива.

Решение.

В результате работы программы справа от исходного массива будет сформирован новый массив удвоенной длины, исходный массив будет стерт.

1.6 МАШИНА ТЬЮРИНГА

Абстрактная вычислительная машина, предложенная в 1936 году А. Тьюрингом для уточнения понятия алгоритма. Доказано, что машина Тьюринга по своим возможностям эквивалентна машине Поста.

Состав Машины Тьюринга.

Машина Тьюринга состоит из каретки и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может содержать символ из некоторого алфавита A={a₀,a₁,…,a_N}. Любой алфавит содержит символ «пробел», который обозначается как a₀ или Λ. При вводе команд пробел заменяется знаком подчеркивания «_».

Машина Тьюринга - это автомат, управляемый таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы - состояниям автомата Q={q₀,q₁,…,q_M}. В начале работы машина Тьюринга находится в состоянии q₁. Состояние q₀ - это конечное состояние: попав в него, автомат заканчивает работу.[11]

В каждой клетке таблицы, соответствующей некоторому символу a_i и некоторому состоянию q_j, находится команда, состоящая из трех частей:

1. символ из алфавита A;

2. направление перемещения: > (вправо), < (влево) или . (на месте);

3. новое состояние автомата.

Примеры решения задач с помощью машины Тьюринга рассмотрим далее.

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

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

Здесь q₁ - состояние изменения цифры, q₀ - остановка. Если в q₁ автомат фиксирует элемент из ряда 0..8, то он замещает ее на один из 1..9 соответственно и затем переключается в состояние q₀, то есть устройство останавливается. В случае если же каретка фиксирует число 9, то замещает ее на 0, затем перемещается влево, останавливаясь в состоянии q₁. Такое движение продолжается до того момента, пока устройство не зафиксирует цифру, меньшую 9. Если все символы оказались равными 9, они замещаются нулями, на месте старшего элемента запишется 0, каретка переместится влево и запишет 1 в пустую клетку. Следующим шагом будет переход в состояние q₀- остановка.

2. Дан ряд из символов, обозначающих открывающие и закрывающие скобки. Требуется создать программу для машины Тьюринга, которая выполняла бы удаление пары взаимных скобок, то есть элементов, расположенных подряд - "( )". Например, исходные данные: ") ( ( ) ( ( )", ответ должен быть таким: ") . . . ( (".

Решение. Механизм, находясь в q₁, анализирует крайний слева элемент в строке.

Состояние q₁: если встречен символ "(", то совершить сдвиг вправо и переход в положение q₂; если определен "a₀", то остановка.

Состояние q₂: проводится анализ скобки "(" на наличие парности, в случае совпадения должно получиться ")". Если элемент парный, то сделать возврат каретки влево и перейти в q₃.

Состояние q₃: осуществить удаление сначала символа "(", а затем ")" и перейти в q₁.

Для проверки и отладки программ для машины Поста и машины Тьюринга можно использовать тренажёр «Машина Поста» и «Машина Тьюринга». В Интернет можно найти свободно распространяемые имитаторы как машины Поста, так и машины Тьюринга. [9]

1.7 ВСПОМОГАТЕЛЬНЫЕ АЛГОРИТМЫ

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

Реализация вспомогательных алгоритмов осуществляется посредством подпрограмм.

Определение 5. Подпрограмма - обособленная, оформленная в виде отдельной синтаксической конструкции и снабженная именем часть программы. Использование подпрограмм позволяет, сосредоточив в них подробное описание некоторых операций, в остальной программе указывать только имена подпрограмм, чтобы выполнить эти операции. [7]

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

Определение 6. Процедура - независимая именованная часть программы, которую можно вызвать по имени для выполнения определенных действий.

Определение 7. Функция - подпрограмма, которая передает в точку вызова скалярное значение.

Рассмотрим технологию создания и использования процедур и функций, руководствуясь учебником Окулова С.М. «Основы программирования».

Процедуры.

Структура процедуры схожа со структурой программы.

Вызов процедуры

Для наглядности объяснения, обратимся к примеру:

В данном фрагменте программы вызывается процедура вычисления суммы двух целых чисел. Процедура вызывается по имени.

При вызове процедуры Sum(a,b,c) из основной программы значение переменной присваивается переменной процедуры Sum, а значение переменной - переменной .

.

Рис. 11. Соответствие параметров процедуры

В любой программе все переменные делятся на глобальные и локальные.

В данном фрагменте программы переменные k, p - глобальные, a d,f - локальные. Глобальные переменные описываются в разделе описаний основной части программы, а локальные - только в том, где описываются переменные. Локальные переменные существуют только во временя работы процедуры, определяются (создаются) при её вызове и «исчезают» после завершения работы процедуры.

При описании процедуры указывается список формальных параметров. Каждый параметр является локальным, к нему можно обращаться только в пределах данной процедуры (в примере x,y,z - формальные параметры, рис.11). Фактические параметры - это параметры, которые передаются процедуре при обращении к ней. (a,b,c - фактические параметры, рис.11). Количество и типы формальных и фактических параметров должны совпадать.

Параметры-значения, т.е. передача параметров по значению. При таком способе передачи параметров значение фактического параметра становится значением соответствующего формального параметра. Внутри процедуры можно производить любые действия с данным формальным параметров (допустимые для его типа), но эти изменения никак не отражаются на значении фактического параметра, т. е. каким он был до вызова процедуры, таким же и останется после завершения её работы (x,y - формальные параметры-значения).
Параметры-переменные - формальные параметры, перед которыми стоит служебное слово Var. При таком способе передачи параметров в процедуру передаётся не значение, а адрес фактического параметра (обязательно переменной). Любые операции с формальным параметром выполняются непосредственно над фактическим параметром. [6]

Функции.

Структура функции.

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

В качестве примера приведем алгоритм вычисления выражения

Z=(A⁵+A^-3)/2*A^M, в котором возведение в степень выполняется функцией Step.[7] На рис.12 представлена блок-схема основного алгоритма.

Рис.12 Алгоритм вычисления выражения Z=(A⁵+A^-3)/2*A^M

В первом разделе «Основы алгоритмизации» рассмотрены понятия алгоритм, свойства алгоритма, способы представления алгоритмов. Виртуальные машины Поста и Тьюринга иллюстрируют формализацию алгоритмов, а так же описаны вспомогательные алгоритмы на примерах процедур и функций.

Для успешного усвоения материала рекомендуется выполнить задания для самостоятельной работы в соответствии с номером своего варианта. В подборке заданий для данного пособия использованы материалы следующих источников [3], [7],[8].

1.8 ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Ветвление в вычислительных алгоритмах

Вариант 1.

1. Написать программу, которая по паролю будет определять уровень доступа сотрудника к секретной информации в базе данных. Доступ к базе имеют только шесть человек, разбитых на три группы по степени доступа. Они имеют следующие пароли: 9583, 1747 - доступны модули баз А, В, С; 3331, 7922 - доступны модули баз В, С; 9455, 8997 - доступен модуль базы С.

2. Пользователь вводит с клавиатуры три целых числа a,b,c. Необходимо вывести на экран наибольшее из этих чисел.

Вариант 2

1. Вычислить значение функции:

2. Дано трехзначное число. Написать программу, определяющую кратна ли шести сумма его цифр.

Вариант 3

1. В ЭВМ поступают результаты соревнований по плаванию для трех спортсменов. Составить программу, которая выбирает лучший результат и выводит его на экран с сообщением, что это результат победителя заплыва.

2. Пользователь вводит с клавиатуры три целых числа a,b,c. Необходимо вывести на экран наибольшее из этих чисел.

Вариант 4

1. Даны три положительных числа. Определить, можно ли построить треугольник со сторонами, длины которых равны этим числам. Если возможно, то ответить на вопрос, является ли он прямоугольным.

2. Напишите программу, запрашивающую три вещественных числа и выводящую их на экран в упорядоченном по возрастанию виде.

Вариант 5.

1. Составьте программу, которая уменьшает первое число в пять раз, если оно больше второго по абсолютной величине.

2. Даны три числа a, b, c. Определить, какое из них равно d. Если ни одно не равно d, то найти max (d-a, d-b, d-c).

Вариант 6.

1. Вычислить значение функции:

2. Дано четырехзначное число. Написать программу определения больше ли цифра сотен цифры единиц.

Вариант 7

1. Определить, является ли номер автобусного билета счастливым числом. Номер задается шестизначным числом.

2. Даны три вещественных числа a,b,c. Напишите программу, определяющую, могут ли данные числа являться длинами сторон равностороннего треугольника.

Вариант 8.

1. Даны три вещественных числа a,b,c. Напишите программу, определяющую, могут ли данные числа являться длинами сторон любого треугольника.

2. Дана точка с координатами (x,y), требуется определить принадлежность точки отрезку (a,b).

Вариант 9.

1. Даны три вещественных числа a,b,c. Напишите программу, определяющую, могут ли данные числа являться длинами сторон прямоугольного треугольника.

2. В точке (x0,y0) находится центр круга радиусом R. Напишите программу, определяющую, находится ли точка с заданными координатами (x,y) внутри или за пределами круга.

Вариант 10.

1. Дана точка с координатами (x,y), определите, принадлежит ли точка осям координат.

2. Напишите программу, запрашивающую три вещественных числа и выводящую их на экран в упорядоченном по убыванию виде.

2. Циклические алгоритмы

Все задачи требуется решить, используя цикл с параметром.

Вариант 1.

1. Найти сумму всех n-значных чисел (1 < n < 4).

2. Даны два целых числа A и B (A < B). Найти сумму всех целых чисел от A до B включительно.

Вариант 2.

1. Дано действительное число а, натуральное число n. Вычислить:

P = a(a - n)(a - 2n) x … x (a - n2).

2. Даны два целых числа A и B (A < B). Найти произведение всех целых чисел от A до B включительно.

Вариант 3.

1. Дано натуральное число n. Вычислить:

S = 1! + 2! + 3! + … + n! (n>1).

2. Даны два целых числа A и B (A < B). Найти сумму квадратов всех целых чисел от A до B включительно.

Вариант 4.

1. Дано натуральное число n. Вычислить:

S = 1/3² + 1/5² + 1/7² + … + 1/(2n + 1)².

2. Даны два целых числа A и B (A < B). Найти частное, получаемое при делении А на все делители из диапазона целых чисел от A до B включительно.

Вариант 5.

1. Написать программу, которая вычисляет сумму n- первых членов ряда 1+1/2+1/3+1/4+… Количество суммируемых членов ряда задается во время работы программы.

2. Дано целое число N (> 0). Найти произведение

N! = 1·2·…·N

Чтобы избежать целочисленного переполнения, вычислять это произведение с помощью вещественной переменной и вывести его как вещественное число.

Вариант 6.

1. Написать программу, которая вводит с клавиатуры последовательность из пяти дробных чисел и после ввода каждого числа выводит среднее арифметическое полученной части последовательности.

2. Дано целое число N (> 0). Найти сумму

N² + (N + 1)² + (N + 2)² + … + (2·N)²

Вариант 7.

1. Написать программу, которая генерирует три последовательности из десяти случайных чисел в диапазоне от 1 до 10, выводит каждую последовательность на экран и вычисляет среднее арифметическое каждой последовательности.

2. Дано целое число N (> 0). Найти сумму

1 + 1/2 + 1/3 + … + 1/N

Вариант 8.

1. Составить программу, которая печатает таблицу умножения и сложения натуральных чисел в десятичной системе счисления.

2. Дано вещественное число - цена 1 кг яблок. Вывести стоимость 1.2, 1.4, …, 2 кг конфет.

Вариант 9.

1. Даны целые числа K и N (N > 0). Вывести N раз число K.

2. Выполнить табулирование функции y = cos(x + a) на отрезке [1, 10] c шагом h=1.

Варbант 10.

1. Дано вещественное число - цена 1 кг конфет. Вывести стоимость 1, 2, …, 10 кг конфет.

2. Вычислить сумму значений функции у = x2 на отрезке [1, 5] c шагом 1.

Составить алгоритмы для следующих задач, используя циклы с предусловием и постусловием.

Вариант 1.

1. Начав тренировки, спортсмен в первый день пробежал 10 км. Каждый день он увеличивал дневную норму на 10% нормы предыдущего дня. Какой суммарный путь пробежит спортсмен за 7 дней?

2. Определить, какие различные цифры входят в заданное целое число.

Вариант 2.

1. Одноклеточная амеба каждые 3 часа делится на 2 клетки. Определить, сколько амеб будет 3, 6, 9, 12, …, 24 часа.

2. Вывести все квадраты натуральных чисел, не превосходящие данного числа N.

Вариант 3.

1. Написать программу, вычисляющую сумму и среднее арифметическое последовательности положительных чисел, которые вводятся с клавиатуры.

2. Вычислить НОД двух чисел А и В.

Вариант 4.

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

2. Дано число. Найти сумму и произведение его цифр.

Вариант 5.

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

2. Написать программу для решения следующей задачи: рост ребенка на начало года - 120 см. За месяц он подрастает на 2%. Через сколько месяцев его рост станет больше или равным 150 см.?

Вариант 6.

1. Составьте программу для нахождения всех автоморфных чисел в отрезке [m,n]. Автоморфным называется целое число, которое равно последним числам своего квадрата. Например: 52=25, 62=36, 252=625.

2. Начальный вклад в банке равен 1000 руб. Через каждый месяц размер вклада увеличивается на P процентов от имеющейся суммы (P - вещественное число, 0 < P < 25). По данному P определить, через сколько месяцев размер вклада превысит 1100 руб., и вывести найденное количество месяцев K (целое число) и итоговый размер вклада S (вещественное число).

Вариант 7.

1. Написать программу, которая вычисляет НОК двух целых чисел.

2. Дано целое число N (> 0). Используя операции деления нацело и взятия остатка от деления, вывести все его цифры, начиная с самой правой (разряда единиц).

Вариант 8.

1. Написать программу, вычисляющую произведение положительных четных чисел до 10.

2. Дано целое число N (> 0). С помощью операций деления нацело и взятия остатка от деления определить, имеется ли в записи числа N цифра «2». Если имеется, то вывести True, если нет - вывести False.

Вариант 9.

1. Написать программу, вычисляющую значение выражения y= для k=1,3,5,7,9.

2. Дано целое число N (> 0). С помощью операций деления нацело и взятия остатка от деления определить, имеются ли в записи числа N нечетные цифры. Если имеются, то вывести True, если нет - вывести False.

Вариант 10.

1. Натуральные числа а, b, с называются числами Пифагора, если выполняется условие а2 + b2 = с2. Напечатать все числа Пифагора меньшие N.

2. Дано n вещественных чисел. Найти их среднее арифметическое.

3. Машина Поста

Вариант 1. На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.

Вариант 2. На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю левую метку. Справа от данного массива на расстоянии в m ячеек находится еще одна метка. Составьте для машины Поста программу, придвигающую данный массив к данной ячейке.

Вариант 3. Известно, что на ленте машины Поста находится метка. Напишите программу, которая находит ее.

Вариант 4. Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение.

Вариант 5. На ленте машины Поста расположено n массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определить количество массивов.

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

Вариант 7. На ленте машины Поста находятся два массива в m и n меток. Составить программу выяснения, одинаковы ли массивы по длине.

Вариант 8. Дано N массивов меток. Массивы разделены тремя пустыми ячейками. Количество меток в массиве не меньше двух. Если количество меток в массиве кратно трем, то стереть метки в этом массиве через одну, в противном случае стереть весь массив. Каретка находится над крайней левой меткой первого массива.

Вариант 9. На ленте машины Поста расположен массив из n меток. Составить программу, действуя по которой машина выяснит, делится ли число n на 3. Если да, то после массива через одну пустую ячейку поставить метку.

Вариант 10. Дано несколько массивов меток. Удалить четные массивы. Каретка находится над первым массивом.

4. Машина Тьюринга

Вариант 1. На ленте машины Тьюринга содержится последовательность символов "+". Напишите программу для машины Тьюринга, которая каждый второй символ "+" заменит на "-". Замена начинается с правого конца последовательности. Автомат в состоянии q₁ обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 2. Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q₁ обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 3. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q₁ обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 4. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было "100", то выходным словом должно быть "99", а не "099". Автомат в состоянии q₁ обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 5. Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд "( )". Например, дано ") ( ( ) ( ( )", надо получить ") . . . ( ( ". Автомат в состоянии q₁ обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 6. Дана строка из букв "a" и "b". Разработать машину Тьюринга, которая переместит все буквы "a" в левую, а буквы "b" - в правую части строки. Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 7. На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 2. Автомат в состоянии q₁ обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 8. Даны два натуральных числа m и n, представленные в унарной системе счисления. Соответствующие наборы символов "|" разделены пустой клеткой. Автомат в состоянии q₁обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит сумму чисел m и n. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 9. Даны два натуральных числа m и n, представленных в унарной системе счисления. Соответствующие наборы символов "|" разделены пустой клеткой. Автомат в состоянии q₁ обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит разность чисел m и n. Известно, что m > n. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

Вариант 10. На ленте машины Тьюринга находится десятичное число. Определить, делится ли это число на 5 без остатка. Если делится, то записать справа от числа слово "да", иначе - "нет". Автомат обозревает некую цифру входного числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.

5. Вспомогательные алгоритмы. Процедуры и функции.

Вариант 1. В квадратной матрице размером 5х5, заполненной случайными целыми числами из диапазона (-45,+45) найти количество положительных элементов.

Вариант 2. В квадратной матрице размером 5х5, заполненной случайными целыми числами из диапазона (-40,+40) найти соответственно максимальный отрицательный и минимальный положительный элементы.

Вариант 3. Описать процедуру Minmax(X, Y), записывающую в переменную X минимальное из значений X и Y, а в переменную Y - максимальное из этих значений (X и Y - вещественные параметры, являющиеся одновременно входными и выходными). Используя четыре вызова этой процедуры, найти минимальное и максимальное из данных чисел A, B, C, D.

Вариант 4. Даны три квадратных матрицы А, В, С n-го порядка. Вывести на печать ту из них, норма которой наименьшая. Пояснение. Нормой матрицы назовем максимум из абсолютных величин ее элементов.

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

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

Вариант 7. Описать процедуру Mean(X, Y, AMean, GMean), вычисляющую среднее арифметическое AMean = (X + Y)/2 и среднее геометрическое GMean = sqrt(XY) двух положительных чисел X и Y (X и Y - входные, AMean и GMean - выходные параметры вещественного типа). С помощью этой процедуры найти среднее арифметическое и среднее геометрическое для пар (A, B), (A, C), (A, D), если даны A, B, C, D.

Вариант 8. Описать процедуру TrianglePS (a, P, S), вычисляющую по стороне a равностороннего треугольника его периметр P и площадь S. (a - входной, P и S - выходные параметры; все параметры являются вещественными). С помощью этой процедуры найти периметры и площади трех равносторонних треугольников с данными сторонами.

Вариант 9. Описать процедуру DigitCountSum(K, C, S), находящую количество C цифр целого положительного числа K, а также их сумму S (K - входной, C и S - выходные параметры целого типа). С помощью этой процедуры найти количество и сумму цифр для каждого из пяти данных целых чисел.

Вариант 10. Описать процедуру Swap(X, Y), меняющую содержимое переменных X и Y (X и Y - вещественные параметры, являющиеся одновременно входными и выходными). С ее помощью для данных переменных A, B, C, D последовательно поменять содержимое следующих пар: A и B, C и D, B и C и вывести новые значения A, B, C, D.

2. МЕТОДЫ ПОСТРОЕНИЯ АЛГОРИТМОВ

2.1 РЕКУРСИВНЫЕ МЕТОДЫ ПОСТРОЕНИЯ АЛГОРИТМОВ

Определение 6. Рекурсия - способ организации вычислительного процесса, при котором функция в ходе выполнения составляющих ее операторов обращается сама к себе.[7]

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

Вид рекурсивной процедуры:

Рассмотрим типовой пример задачи вычисления факториала числа.

На рис. 13 показаны прямой и обратный ход рекурсии. [6] В любой рекурсивной подпрограмме обязательно должна быть не рекурсивная ветвь:

Пусть переменной a присваивается значение 5!:

Рис. 13. Прямой и обратный ход рекурсии.

Рассмотрим некоторые примеры использования рекурсии.[6]

1. Сложение двух чисел a + b. Рекурсивное определение операции сложения двух чисел:

a + b =

2. Каждое число Фибоначчи равно сумме двух предыдущих чисел при условии, что первые два равны 1 (1, 1, 2, 3, 5, 8, 13, 21,…).В общем виде n-e число Фибоначчи можно определить так:
Ф(n)=

3. «Ханойские башни». В конце XIX века в Европе появилась игра под названием «Ханойские башни». Реквизит игры состоит из 3 игл, на которых размещается башня из колец. Цель игры - перенести башню с левой иглы (1) на правую (3), причем за один раз можно перенести только одно кольцо. Кроме того, запрещается помещать большее кольцо над меньшим.

Программа, которая печатает последовательность переноса колец посредством рекурсивной процедуры, представлена в Приложении 1, Hanoy.pas.

Данная задача своим происхождением обязана легенде, в которой рассказывается, что в большом храме Бенареса на бронзовой плите установлены три алмазных стержня, на один из которых бог нанизал во время сотворение мира 64 золотых диска. С тех пор день и ночь монахи, сменяя друг друга каждую секунду, перекладывают по одному диску согласно описанным выше правилам. Конец мира наступит тогда, когда все 64 диска будут перемещены, на что потребуется чуть больше 58 млрд. лет.

2.2 МЕТОДЫ СОРТИРОВКИ ДАННЫХ

По методам сортировки, а также по методам поиска данных существует очень много публикаций. Рассмотрим основные методы сортировки данных ссылаясь на классическую книгу по программированию Кнут Д. «Искусство программирования», в которой методам сортировки посвящен третий том.

Сортировка простым выбором

Рассмотрим идею на примере. Пусть исходный массив А состоит из 10 элементов: 5 13 7 9 1 8 16 4 10 2. После сортировки массив должен выглядеть так: 1 2 4 5 7 8 9 10 13 16.

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

1-й шаг. Рассмотрим весь массив и найдем в нем максимальный элемент - 16 (на седьмом месте), поменяем его местами с последним элементом - с числом 2.

5 13 7 9 1 8 16 4 10 2

Максимальный элемент записан на свое место.

2-й шаг. Рассмотрим часть массива - с первого до девятого элемента. Максимальный элемент этой части - 13 (на втором месте). Поменяем его местами с последним элементом этой части - с числом 10.

5 13 7 9 1 8 2 4 10 16

Отсортированная часть массива имеет два элемента.

3-й шаг. Уменьшим рассматриваемую часть массива на один элемент. Здесь нужно поменять местами второй элемент (его значение - 10) и последний элемент этой части - число 4.

5 10 7 9 1 8 2 4 13 16

В отсортированной части массива - 3 элемента.

4-й шаг.

5 4 7 9 1 8 2 10 13 16

5-й шаг. Максимальный элемент этой части массива является последним в ней, поэтому его нужно оставить на старом месте.

5 4 7 2 1 8 9 10 13 16

6-й шаг.

5 4 7 2 1 8 9 10 13 16

7-й шаг.

5 4 1 2 7 8 9 10 13 16

8-й шаг.

2 4 1 5 7 8 9 10 13 16

9-й шаг.

2 1 4 5 7 8 9 10 13 16

На рис. 14. представлена блок-схема алгоритма сортировки простым выбором. Программа - Приложение 1, Vibor.pas.

Рис. 14. Алгоритм сортировки методом выбора

2. Сортировка простым обменом. Метод «пузырька»

Рассмотрим идею метода на примере. Отсортируем по возрастанию массив из 5 элементов: 5 4 8 2 9. Длина текущей части массива - N-k+1, где k - номер просмотра, I - номер первого элемента проверяемой пары, номер последней пары - N-k.

Первый просмотр: рассматривается весь массив.

I=1 5 4 8 2 9

> меняем

I=2 4 5 8 2 9

< не меняем

I=3 4 5 8 2 9

> меняем

I=4 4 5 2 8 9

< не меняем

Цифра 9 находится на своем месте.

Второй просмотр: рассматриваем часть массива с первого до предпоследнего элемента.

I=1 4 5 2 8 9

< не меняем

I=2 4 5 2 8 9

> меняем

I=3 4 2 5 8 9

< не меняем

Цифра 8 на своем месте.

Третий просмотр: рассматриваемая часть массива содержит три первых элемента.

I=1 4 2 5 8 9

> меняем

I=2 2 4 5 8 9

< не меняем

Цифра 5 на своем месте.

Четвертый просмотр: рассматриваем последнюю пару элементов.

I=1 2 4 5 8 9

< не меняем

Цифра 4 на своем месте. Наименьший элемент - 2 оказывается на первом месте. Количество просмотров элементов массива равно N-1.

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

На рис. 15. представлена блок-схема алгоритма сортировки методом «пузырька». Программа - Приложение 1, Puz.pas.

Сортировка простыми вставками.

Сортировка этим методом производится последовательно шаг за шагом. На шаге считается, что часть массива, содержащая первые элементов, уже упорядочена, то есть. Далее следует взять элемент, и для него найти место в отсортированной части массива, такое, что после его вставки упорядоченность не нарушится, то есть требуется найти такое , что , (при происходит только одно сравнение). Затем выполняется вставка элемента на место . На каждом шаге отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить шаг.

Рассмотрим этот процесс на примере. Таблица 3. Пусть требуется отсортировать массив из 10 элементов по возрастанию.

Рис. 15. Алгоритм сортировки методом «пузырька»

Таблица 3. Сортировка вставками

Блок-схема алгоритма сортировки массива вставками на рис.16. Программа сортировки вставками представлена в Приложении 1, Vstavka.pas.

Ввести

k=

Нет

Начало

Конец

Вывести

Рис.16 Алгоритм сортировки элементов массива вставками

Методы быстрой сортировки.

Метод сортировки слиянием.

Прежде, чем обсуждать метод, рассмотрим следующую задачу. Объединить («слить») упорядоченные фрагменты массива А A[k],…,A[m] и A[m+1],…,A[q] в один A[k],…,A[q], естественно, тоже упорядоченный (kmq). Основная идея решения состоит в сравнении очередных элементов каждого фрагмента, выяснении, какой из элементов меньше, переносе его во вспомогательный массив D (для простоты) и продвижении по тому фрагменту массива, из которого взят элемент. При этом следует не забывать записать в D оставшуюся часть этого фрагмента, который не успел себя «исчерпать».

Рассмотрим сортировку массива методом слияния на примере.

Пример. Пусть первый фрагмент состоит из 5 элементов: 3 5 8 11 16, а второй - из 8: 1 5 7 9 12 13 18 20. Рисунок иллюстрирует логику объединения фрагментов.

Рис. 17. Метод сортировки элементов массива слиянием

Программная реализация метода сортировки слиянием - Приложение 1, Slianie.pas.

Метод слияний - один из первых в теории алгоритмов сортировки. Он предложен Дж. фон Нейманом в 1945 году. Недостатком сортировки слиянием является использование дополнительной памяти. Но при работе с файлами или списками, доступ к которым осуществляется только последовательно, очень удобно применение этого метода.[6, 10]

Метод быстрой сортировки. Сортировка Хоара.

Метод предложен Ч. Э. Р. Хоаром в 1962 году. Эффективность метода достаточно высокая, поэтому автор назвал его «быстрой сортировкой».

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

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

Рассмотрим сортировку массива методом Хоара на примере.[6,10]

Пример. Исходный массив состоит из 8 элементов: 8 12 3 7 19 11 4 16. В качестве барьерного элемента возьмем средний элемент массива (7).

Произведя необходимые перестановки, получим: (4 3) 7 (12 19 11 8 16), элемент 7 находится на своем месте. Продолжим сортировку.

Левая часть: (3) 4 7 (12 19 11 8 16)

3 4 7 (12 19 11 8 16)

Правая часть:

3 4 7 (8) 11 (19 12 16)

3 4 7 8 11 (19 12 16)

3 4 7 8 11 12 (19 16)

3 4 7 8 11 12 (16) 19

3 4 7 8 11 12 16 19

Из вышеизложенного описания явно просматривается рекурсивная схема реализации, параметрами которой являются нижняя и верхняя границы изменения индексов сортируемой части исходного массива. Приведем процедуру быстрой сортировки. [7]

Procedure QuickSort (m, t : Integer); {*m- начало массива, t - конец массива.*}

Var i, j, x, w : Integer;

Begin

I:=m; j:=t; x:=A [(m+t) Div 2];

Repeat

While A[i] < x Do Inc (i);

While A[j] > x Do Dec (j);

If i<=j Then Begin w:=A[i]; A[i]:=A[j]; A[j]:=w;

Inc (i); Dec (j); End

Until i>j;

If m

If i

End;

2.3 МЕТОДЫ ПЕРЕБОРА В ЗАДАЧАХ ПОИСКА

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

Линейный поиск.

Поиск наибольшего и наименьшего элемента в массиве.

Дан ряд чисел , , …, , …, . Разработать алгоритм поиска наибольшего и наименьшего числа в этом ряду с указанием номера (индекса) его расположения.

Очевидный способ поиска наибольшего (наименьшего) числа в заданном ряду n чисел включает следующие действия. Взять первое число ряда и сказать, что оно наибольшее (наименьшее), а индекс его равен 1. Затем взять второе число ряда и сравнить с предполагаемым максимальным (минимальным) первым числом. Если второе число больше предполагаемого (максимального) первого числа, взять третье число ряда и сравнить с первым. Так следует действовать до тех пор, пока не будет выбрано последнее число. В результате на месте первого числа окажется наибольшее (наименьшее) число с указанным его номером в ряду чисел. [2]

Блок - схема алгоритма поиска наибольшего и наименьшего элемента на рис.18.

Начало

Конец

Ввести

A

A

Вывести

да

да

да

нет

нет

Рис. 18 Алгоритм нахождения наибольшего и наименьшего элемента в линейном массиве

Программа на языке Pascal представлена в Приложении 1, MaxMin.pas.

Бинарный поиск.

Метод бинарного поиска можно применять уже в отсортированном массиве. Допустим, что массив А отсортирован в порядке не убывания. Это позволяет по результату сравнения со средним элементом массива исключить из рассмотрения одну из половин. С оставшейся частью процедура повторяется. И так до тех пор, пока не будет найден искомый элемент или не будет построен весь массив. [6,7]

Рассмотрим алгоритм бинарного поиска на примере.

Пример. Пусть X = 6, а массив А состоит из 10 элементов:

3 5 6 8 12 15 17 18 20 25.

1-й шаг. Найдем номер среднего элемента среднего элементов: m = = 5.

Так как 6 < А[5], то далее рассматриваются только элементы, индексы которых меньше 5.

3 5 6 8 12 15 17 18 20 25.

2-й шаг. Рассматриваем лишь первые 4 элемента массива, находим индекс среднего элемента этой части : m = = 2.

6 > А[2], следовательно, первый и второй элементы из рассмотрения исключаются:

3 5 6 8 12 15 17 18 20 25;

3-й шаг. Рассматриваем два элемента, значение m = = 3.

3 5 6 8 12 15 17 18 20 25;

А[3] = 6. Элемент найден, его номер - 3.

Блок - схема алгоритма бинарного поиска на рис.19:

Рис. 19 Алгоритм бинарного поиска в упорядоченном массиве

A

да

нет

Вывести: «элемент не найден"

A

Вывести: «элемент найден», j=

Ввести

нет

Конец

Начало

нет

Программная реализация бинарного поиска представлена в Приложении 1, Binar.pas.

Случайный поиск.

Организация поиска k-го элемента в неупорядоченном массиве X возможна следующим образом. Выбирается случайным образом элемент с номером q. Массив X разбивается на три части: элементы, меньшие X[q], равные X[q] и большие X[q]. А затем, в зависимости от количества элементов в каждой части, выбирается одна из частей для дальнейшего поиска. Теоретическая оценка числа сравнений имеет порядок k*N, т. е. для худшего случая N², но на практике он значительно быстрее.

2.4 СЛОЖНОСТЬ АЛГОРИТМОВ

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

Таким образом, t есть характеристика алгоритма, не зависящая от особенностей исполнителя, и потому математическая характеристика сложности алгоритма. Память S, используемая алгоритмом, также зависит от особенностей исполнителя. Если на каждом шаге алгоритма используется не более µ единиц памяти, то S ≤ µ · . Эта оценка очень грубая, так как t может значительно превосходить S. В большинстве случаев в качестве характеристики сложности алгоритма применяется характеристика t - число шагов выполнения алгоритма.

Трудоемкость алгоритмов.

Итак, зависит от исходных данных задачи. Зависимость эту не всегда возможно анализировать непосредственно. Вследствие этого целесообразно будет определить временные рамки выполнения алгоритма (максимальное и минимальное время), сколько в среднем будет выполняться алгоритм (среднее время). Но для любых вариантов задачи время (число шагов) ничем не ограничено. Так, при сортировке массива время, как правило, зависит от длины массива и растет с ростом числа элементов массива. Принято входные данные алгоритма характеризовать одним параметром или несколькими параметрами. Одной из таких характеристик является объем входных данных - число элементов входных данных. Эта характеристика объективно характеризует входные данные так же, как и число шагов объективно характеризует исполнение алгоритма. В свою очередь, устанавливают зависимость объема входных данных от одного или нескольких параметров, характеризующих задачу. Так, в задаче сортировки массива таким параметром является длина n массива.

Так как число шагов алгоритма зависит не только от выбранных в задаче параметров, характеризующих объем входных данных но и от других характеристик входных данных
, то можно ввести оценку по всем этим характеристикам. Оценка наибольшего числа шагов, необходимых для выполнения алгоритма, в зависимости от параметров P:

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

и оценку среднего числа шагов, которую называют средней трудоемкостью:

где k - число вариантов других характеристик входных данных.

Трудоемкость алгоритма позволяет оценить время выполнения алгоритма при решении той или иной задачи:

При этом коэффициент статистически определяется для исполнителя или оценивается некоторой константой. Однако точный вид зависимости T(n) от аргумента n часто очень трудно установить. Поэтому вместо установления вида функции для трудоемкости оценивается быстрота роста этой функции при помощи некоторой простой функции f(n).

Говорят, что T(n) = O(f(n)), если |T(n)| ≤ C|f(n)| для всех значений n > n₀. Такая оценка роста функции T(n) является односторонней, так как функция f(n) может расти быстрее. Лучше оценивать рост трудоемкости функцией f(n), имеющей тот же порядок роста, т. е. также |T(n)| ≥ C1|f(n)|. В этом случае пишут

T(n) = Θ(f(n)) и говорят, что рост T(n) оценивается ростом f(n). Наиболее простыми функциями, оценивающими рост трудоемкости, являются полиномы

В случае T(n) = Θ(p(n)), учитывая, что p(n) = Θ(n k ), получаем T(n) = Θ(n k). Говорят, что в этом случае трудоемкость полиномиальна или алгоритм имеет полиномиальную трудоемкость. При k = 1 T(n) = Θ(n) и алгоритмы принято называть алгоритмами с линейной трудоемкостью.

Если есть два алгоритма A1 и A2 решения некоторой задачи и оба имеют полиномиальную трудоемкость, причем k1 < k2, то говорят, что первый алгоритм имеет меньшую трудоемкость. Но меньшая трудоемкость не означает, что время решения задачи первым алгоритмом будет меньше, чем вторым. Так, пусть

Тогда при n < 10 оказывается, что время решения задачи для первого алгоритма больше, чем для второго. Однако, из определения ясно, что найдется такое n₀ (в примере n₀ = 10), что время решения задачи при n > n0 будет всегда меньше для первого алгоритма.

Трудоемкость алгоритма может иметь скорость роста меньшую, чем линейная. Например, или .

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

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

При нескольких параметрах входных данных трудоемкость полиномиального алгоритма растет как полином от нескольких аргументов. Например,

Оценивание трудоемкости алгоритмов.

Процесс получения оценки трудоемкости называется оцениванием трудоемкости. Для этого следует анализировать алгоритм с точки зрения быстроты роста числа его шагов, при изменении параметров задачи (параметров входных данных). Прежде всего, в алгоритме следует выделить циклы. Если циклов нет, то число шагов линейной структуры алгоритма не зависит от параметров задачи и, следовательно, трудоемкость является константной, т. е. оценивается как Θ (1).

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

Если цикл B с числом повторений n(B) вложен в цикл A с числом повторений n(A) и циклы независимы (число повторений цикла B не зависит от выполнения цикла A), то общее число повторений цикла B с учетом повторений цикла A составляет n(A) · n(B).

Отсюда правило: для вложенных независимых циклов их трудоемкости перемножаются Θ(AB) = Θ(A) · Θ(B).

Если вложенные циклы не являются независимыми, т. е. число повторений внутреннего цикла n_i(B) зависит от номера i повторения при выполнении внешнего цикла, то нужно проанализировать, как зависит общее число повторений внутреннего цикла от параметров задачи.

Если циклы не являются вложенными, то трудоемкость определяется наибольшей из трудоемкостей циклов

Θ(A + B) = Θ(A) + Θ(B) = max{Θ(A), Θ(B)}.

При оценке максимальной трудоемкости следует подбирать такие примеры входных данных для тех или иных параметров задачи, на которых реализуется максимальное число шагов алгоритма. При оценке минимальной трудоемкости следует подбирать примеры, на которых реализуется минимальное число шагов алгоритма. Ввиду сложности некоторых алгоритмов такие примеры не всегда удается построить, но в таких случаях для оценки трудоемкости бывает достаточно примеров и близких по числу операций к максимальному или соответственно к минимальному числу.[11]

Рассмотрим примеры оценивания трудоемкости на примере алгоритма сортировки массива методом «пузырька». Блок - схема алгоритма сортировки методом «пузырька» см. рис. 15

Алгоритм содержит вложенные циклы. Внешний цикл, в случае массива входных данных, упорядоченного по убыванию, будет выполняться максимальное число раз: n − 1, а в случае входного массива, упорядоченного по возрастанию, будет выполняться только 1 раз. Внутренний цикл во втором случае выполняется n − 1 раз, а в первом случае циклы зависимы, но, внутренний цикл в среднем выполняется n/2 раз. Поэтому максимальная трудоемкость (входные данные первого случая) оценивается как

Θ(n) · Θ(n) = Θ(n²),

а минимальная трудоемкость (входные данные второго случая) - как

Θ(1) · Θ(n) = Θ(n).

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

2.5 ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Рекурсивные методы построения алгоритмов

Вариант 1. Описать рекурсивную функцию DigitSum(K) целого типа, которая находит сумму цифр целого числа K без использования оператора цикла.

Вариант 2. Вычислить сумму: , используюя функцию вычисления факториала числа

Вариант 3. Описать рекурсивную функцию SqrtK(X, K, N) вещественного типа, находящую приближенное значение корня k-й степени из числа X по формуле:

где Yn обозначает SqrtK(X, K, N) при фиксированных X и K. Параметры функции: X > 0 - вещественное число, K > 1 и N > 0 - целыt/

Вариант 4. Описать рекурсивную функцию NOD(A, B) целого типа, находящую наибольший общий делитель (НОД) двух целых положительных чисел A и B, используя алгоритм Евклида: NOD(A, B) = NOD(B mod A,B), если A <> 0; НОД(0, B) = B.

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

Вариант 6. Описать рекурсивную функцию Fact2(N) вещественного типа, вычисляющую значение двойного факториала N!! = N·(N-2)·(N-4)·. . . ., где N > 0 - параметр целого типа; последний сомножитель в произведении равен 2, если N - четное число, и 1, если N - нечетное.

Вариант 7. Напишите рекурсивную функцию SumTo(n), которая для данного n вычисляет сумму чисел от 1 до n.

Методы сортировки данных

Реализуйте все простые сортировки линейного массива, используя процедуры, и оцените трудоемкость каждого алгоритма.

Вариант 1. Дан массив целых чисел осуществить сортировку четных элементов массива.

Вариант 2. Дан массив целых чисел осуществить сортировку элементов массива записанных на нечетных местах.

Вариант 3. Дан массив целых чисел осуществить сортировку отрицательных элементов массива.

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

Вариант 6. Задан массив М, состоящий из N целочисленных элементов. Упорядочить элементы таким образом, чтобы вначале располагались все нечетные аргументы, а после них все четные.

Вариант 7. Задан массив М, состоящий из N целочисленных элементов. Упорядочить элементы таким образом, чтобы вначале располагались все четные аргументы, а после них все нечетные.

Вариант8. Задан массив М, состоящий из N целочисленных элементов. Упорядочить элементы таким образом, чтобы вначале располагались все положительные аргументы, а после них все отрицательные.

Вариант 9. Задан массив М, состоящий из N целочисленных элементов. Упорядочить элементы таким образом, чтобы вначале располагались все отрицательные аргументы, а после них все положительные.

Вариант 10. Массив М, состоящий из 30 элементов, переформировать так, чтобы вначале стояли все положительные элементы в порядке убывания их значений, а затем все отрицательные элементы в порядке возрастания их значений.

Метод перебора в задачах поиска

Вариант 1. Дана вещественная матрица А(N,M). Составить программу замены всех положительных элементов матрицы на элемент, имеющий минимальное значение.

Вариант 2. Дана вещественная матрица А(N,M). Составить программу нахождения максимального отрицательного элемента матрицы и нахождения его местоположения.

Вариант 3. Дана вещественная матрица А(N,M). Составить программу замены всех отрицательных элементов матрицы на элемент, имеющий максимальное значение.

Вариант 4. Составить программу замены всех отрицательных элементов матрицы А(N,N) на элемент этой матрицы, имеющий минимальное значение. Скорректированную матрицу напечатать.

Вариант 5. Дана вещественная матрица А(N,M).Составить программу нахождения минимального положительного элемента матрицы и нахождения его местоположения.

Вариант 6. Составить программу замены всех отрицательных элементов матрицы А(6,6) на 0, если сумма минимального и максимального элементов этой матрицы окажется меньше Р.

ЗАКЛЮЧЕНИЕ

В результате проделанной работы создано учебное пособие по дисциплине «Теория алгоритмов» для студентов Политехнического колледжа НовГУ обучающихся по специальности 230115 «Программирование в компьютерных системах».

Учебное пособие разработано в соответствии с рабочей программой дисциплины «Теория алгоритмов» и отвечает всем требованиям к результатам освоения студентами данной дисциплины.

Учебное пособие состоит из двух разделов. В ходе работы был проведен анализ научных и литературных источников, на основе которых в первом разделе раскрыты понятия алгоритма и вспомогательного алгоритма, основные алгоритмические структуры, рассмотрена формализация понятия «алгоритм» на примерах виртуальных машин Поста и Тьюринга. В результате работы над вторым разделом пособия изучены и систематизированы основные методы сортировки данных и поиска заданных элементов в массивах, а так же рассмотрено понятие сложности алгоритма. В каждом разделе пособия рассмотрены примеры решения типовых задач, представлены блох-схемы алгоритмов.

В Приложении 1, прилагаемом к учебному пособию, представлены программы на языке Pascal для разобранных примеров.

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

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

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

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Игошин В.И.Теория алгоритмов: Учебное пособие. - М.:ИНФРА-М, 2013.- 318 с.

2. Канцедал С.А. Алгоритмизация и программирование: учебное пособие. - М.: ИД «ФОРУМ»: ИНФРА-М, 2014. - 352 с.

3. Колдаев В.Д., Павлова Е.Ю. Сборник задач и упражнений по информатике. - М.: ИД «ФОРУМ»: ИНФРА-М, 2010. - 256 с.

4. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0. - К.: ВЕК+, 1999. - 464 с.

5. Немцова Т.И., Голова С.Ю., Абрамова И.В. Программирование на языке высокого уровня. Программирование на языке Object Pascal. - М.: ИД «ФОРУМ»: ИНФРА-М, 2012. - 496 с.

6. Окулов С.М. Основы программирования. - М.: БИНОМ. Лаборатория знаний, 2010. - 440 с.

7. Попов В. Б. Turbo Pascal для школьников. - М.: Финансы и статистика, 2000. - 528 с.

8. Цымбалюк Л.Н. Основы алгоритмизации и программирования: Практикум «Работа в программе Borland Pascal». - П.-К.: Камчатский кооперативный техникум, 2009. - 111 с.

9. Методические материалы и программное обеспечение: [Электронный ресурс], kpolyakov.narod.ru/, (Дата обращения 24.02 2015).

10. Кнут Д. Искусство программирования. Т.3. [Электронный документ], eknigi.org. (Дата обращения 15.04.2015).

11. Рублев В.С. Основы теории алгоритмов: учебное пособие. - Ярославль, 2005. [Электронный документ], ivt.corp7.uniyar.ac.ru. (Дата обращения 24.03.2015)

12. Фалина И.Н., Радченко Е.Л. «Изучение машины Поста в школьном курсе информатики». [Электронный документ], inf.1september.ru. (Дата обращения 30.03.2015)

13. Рабочая программа дисциплины «Теория алгоритмов».

ПИЛОЖЕНИЕ 1. КОМПАКТ-ДИСК С ПРОГРАММАМИ РАССМОТРЕННЫХ В ПОСОБИИ ПРИМЕРОВ

77