Сборник задач по УД "Теория алгоритмов"
учебно-методическое пособие по теме

Тема 1: Понятие алгоритма

Понятие алгоритма

Алгоритм – это строгая и четкая последовательность действий, выполнение которых приводит к определенному результату.

Требования к алгоритмам

1. Ориентированность на конкретного исполнителя.
2. Понятность для исполнителя (алгоритм составляется в соответствии с системой команд исполнителя).
3. Точность (каждая команда должна определять однозначное действие исполнителя).
4. Конечность (наличие конца алгоритма через конечное число шагов).
5. Результативность (получение нужного результата по окончанию алгоритма).
6. Массовость (применимость для широкого класса задач).
7. Формальность исполнения (во время исполнения алгоритма исполнитель не должен задумываться над сутью выполняемых действий).

Способы записи алгоритмов

1. Словесный (описание алгоритма с помощью слов русского языка).

Пример. Алгоритм включения компьютера.

Подойти к компьютеру.

Включить монитор.

Включить системный блок.

2. Запись на алгоритмическом языке

Пример. Алгоритм нахождения минимального из двух введенных чисел.

Начало

Ввод числа х

Ввод числа у

Если х<у

То Вывод х

Иначе Вывод у

Все

Конец

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

(будет рассмотрен ниже)

4. Программа (запись алгоритма на языке программирования)

Пример. Определение четности введенного числа.

Блок-схемы

Блок-схемы являются одним из графических способов представления алгоритмов. Блок-схема состоит из блоков, соединенных линиями. Чаще всего используются блоки следующих типов:

- выполнение операции;

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

- ввод/вывод данных;

- начало и конец алгоритма.

Алгоритмические конструкции

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

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

Конструкция ветвления в полной форме реализуется следующим образом. Если условие истинно, то выполняется действие 1, если условие ложно, то выполняется действие 2.

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

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

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

Различают два вида циклов: циклы с заранее известным числом повторений и циклы  с заранее неизвестным числом повторений. Цикл с заранее известным числом повторений называют циклом с параметром. Блок-схема цикла с параметром помещена на рис.4.

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

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

Различают циклы с проверкой условия перед выполнением очередной итерации и циклы с проверкой условия после выполнения очередной итерации. Первые называются циклами с предусловием (рис. 5), вторые – с постусловием (рис. 6).

Алгоритмическая конструкция называется вложенной, если она содержится внутри другой алгоритмической конструкции.  На рис. 7 команда ветвления вложена в цикл.

Примеры решения задач:

1.  (Задание А8 демоверсии 2004 г.)

Алгоритмическая конструкция какого типа изображена на фрагменте блок-схемы (см. рис. 8):

1. линейная;
2. циклическая;
3. разветвляющаяся;
4. вспомогательная.

Решение. На рис. 8 изображен ромб, внутри которого записано условие, и две исходящие из него стрелки. Фрагмент условия представляет собой блок ветвления в полной форме.

Ответ: №3.

2. (Задания А29 демоверсии 2005 г., А6 демоверсии 2006 г.)

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

1. 1;
2. 5;
3. 10;
4. 15.

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

Таблица 1.

Таким образом, переменная х после выполнения данного фрагмента программы приняла значение 5, что соответствует ответу под номером 2.

Ответ: 2.

Задачи для самостоятельного решения:

1. Определите значение переменной b после выполнения следующего фрагмента алгоритма (см. рис.10):
2. Определите значение переменной a после выполнения алгоритма (см. рис.11):

3. Определите значение переменной s после выполнения фрагмента алгоритма (см. рис. 12).

1. Составить циклический алгоритм с постусловием и блок-схему для определения в последовательности целых чисел количества четных чисел.
2. Постройте  блок-схему для решения задачи: для массива x1, x2,..,x20. Требуется расположить отрицательные элементы в порядке убывания.
3. Составить блок-схему для вычисления суммы элементов двумерного массива, расположенных на главной диагонали
4. Составит блок-схему для поиска максимального значения в двумерном массиве.
5. Построить блок-схему для вычисления суммы ряда:
6. Постройте блок-схему для решения задачи: На отрезке [-15; 15] получить значения функции
7. Постройте блок-схему для решения задачи: Ввести массив x1, x2,..,x20. Элементы, на нечетных местах, расположить в порядке возрастания, а на нечетных в порядке убывания
8. Постройте блок-схему для решения задачи: В числовой последовательности определить сумму положительных и произведение отрицательных чисел
9. Постройте блок-схему и дайте словесное описание решения задачи: Ввести два числа. Меньшее заменить полусуммой, а большее – удвоенным произведением
10. Составьте словесный алгоритм и постройте блок-схему для решения задачи: нахождения минимального значения трех чисел
11. Составить циклический алгоритм с постусловием для определения в последовательности целых чисел количества четных чисел.
12. Составить алгоритм  и блок-схему табулирования функции  y=cos(x+а) на отрезке [1;10] с шагом 1 определить сумму значений y больших P.
13. Составить алгоритм определения находиться ли точка М с координатами X и  Y, на окружности радиуса R.
14. Составить алгоритм определения корней уравнения:

Тема 2: Виды алгоритмических процессов.

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

Примеры решения задач:

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

Решение:

В состоянии q1 машина ищет правый конец числа, в состоянии q2 — пропускает знак “+”, при достижении конца последовательности — останавливается. В состоянии q3 машина знак “+” заменяет на знак “–”, при достижении конца последовательности она останавливается.

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

Решение:

Задачи для самостоятельного решения:

1. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
2. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
3. Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “( )”.
   Например, дано “) ( ( ) ( ( )”, надо получить “) . . . ( ( ”.
   Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
4. Дана строка из букв “a” и “b”. Разработать машину Тьюринга, которая переместит все буквы “a” в левую, а буквы “b” — в правую части строки. Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
5. На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножить это число на 2. Автомат в состоянии q1 обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
6. Даны два натуральных числа m и n, представленные в унарной системе счисления. Соответствующие наборы символов “|” разделены пустой клеткой. Автомат в состоянии q1 обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит сумму чисел m и n. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
7. Даны два натуральных числа m и n, представленных в унарной системе счисления. Соответствующие наборы символов “|” разделены пустой клеткой. Автомат в состоянии q1 обозревает самый правый символ входной последовательности. Разработать машину Тьюринга, которая на ленте оставит разность чисел m и n. Известно, что m > n. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
8. На ленте машины Тьюринга находится десятичное число. Определить, делится ли это число на 5 без остатка. Если делится, то записать справа от числа слово “да”, иначе — “нет”. Автомат обозревает некую цифру входного числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
9. Даны два целых положительных числа в десятичной системе счисления. Сконструируйте машину Тьюринга, которая будет находить разность этих чисел, если известно, что первое число больше второго, а между ними стоит знак «минус». Каретка находится над левой крайней цифрой левого числа.
10. Сконструируйте машину Тьюринга, которая выступит в качестве двоично-восьмеричного дешифратора.
11. На ленте машина машины Тьюринга находится число, записанное в десятичной системе счисления. Умножьте это число на 2, если каретка находится над крайней левой цифрой числа.
12. На ленте машины Тьюринга находится целое положительное число, записанное в десятичной системе счисления. Найдите произведение этого числа на число 11. Каретка обозревает крайнюю правую цифру числа.
13. Построить машину Тьюринга для решения следующей задачи: во входном слове все буквы «а» заменить на буквы «б»
14. Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропусков. Необходимо разработать машину Тьюринга, которая будет записывать в десятичной системе счисления число этих меток.
15. На ленте машины Тьюринга записано число в десятичной системе счисления. Каретка находится над крайней правой цифрой. Запишите цифры этого числа в обратном порядке.
16. На информационной ленте машины Тьюринга находится десятичное число. Найдите результат целочисленного деления этого числа на 2.
17. На ленте машины Тьюринга находится массив 2N меток. Уменьшите этот массив в 2 раза.
18. Даны два натуральных числа m и n, представленные в унарной системе счисления. Между этими числами стоит знак «?». Выясните отношение m и n, т.е. знак «?» замените на один из подходящих знаков «<», «>», «=»
19. На ленте машины Тьюринга находится слово, состоящее из букв латинского алфавита {a, b, c, d}. Подсчитайте число букв «а» в данном слове и полученное значение запишите на ленту левее исходного слова через пробелю каретка обозревает крайнюю левую букву.
20. Найдите произведение двух натуральных чисел m и n, заданных в унврной системе счисления. Соответствующие наборы символов «|» разделены знаком «*», а справа от последнего символа правого члена стоит знак «=». Поместите результат умножения этих чисел вслед за знаком «=»

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

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

Машина Поста состоит из …

1. бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак),
2. головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку.

В каждый момент времени каретка указывает на одну из ячеек. В каждой ячейке ленты может быть либо ничего не записано, либо стоять метка V. Информация о том, какие ячейки пусты, а какие содержат метки, образует состояние ленты. Другими словами, состояние ленты — это распределение меток по ячейкам. Состояние ленты меняется в процессе работы машины. Наличие метки в ячейке можно интерпретировать как “1”, а отсутствие — “0”.

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

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

Примеры решения задач:

1. На ленте задан массив меток. Увеличить длину массива на 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. Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива.

Решение:

1. X2
2. 3
3. ?4;2
4. V5
5. 6
6. ?8;7
7. !
8. 9
9. ?10;8
10. 1

Задачи для самостоятельного решения:

1. На ленте заданы два массива — m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива.
2. Составить программу сложения двух целых неотрицательных чисел a и b, расположенных на ленте Поста. Каретка располагается над одной из меток, принадлежащих числу а. Число b находится правее числа а через несколько пустых секций.
3. Составьте программу сложения произвольного количества целых неотрицательных чисел, записанных на ленте машины Поста на расстоянии одной пустой секции друг от друга. Каретка находится над крайней левой меткой левого числа.
4. На ленте заданы два массива. Найти модуль разности длин массивов. Каретка располагается над первой ячейкой левого массива.
5. На ленте задан массив. Удвоить массив в два раза. Каретка располагается над первой ячейкой массива.
6. На ленте задан массив. Вычислить остаток от деления длины заданного массива на 3. Каретка располагается над первой ячейкой массива.
7. На ленте машины Поста расположен массив из n меток. Составить программу, действуя по которой машина выяснит, делится ли число n на 3. Если да, то после массива через одну пустую ячейку поставить метку.
8. На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками.
9. На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю левую метку. Справа от данного массива на расстоянии в m ячеек находится еще одна метка. Составьте для машины Поста программу, придвигающую данный массив к данной ячейке.
10. Известно, что на ленте машины Поста находится метка. Напишите программу, которая находит ее.
11. Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение.
12. Дано несколько массивов меток. Удалить четные массивы. Каретка находится над первым массивом.
13. Составьте программу умножения двух чисел а и в.
14. На ленте машины Поста расположены два массива. Составьте программу стирания того из массивов, который имеет большее количество меток.
15. На ленте машины Поста расположено n массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого массива. Определить количество массивов.
16. На ленте машины Поста расположен массив из 2n – 1 меток. Составить программу удаления средней метки массива.
17. На ленте машины Поста расположен массив в N отмеченных секциях. Необходимо справа от данного массива через одну пустую секцию разместить массив вдвое больший. При этом исходный массив должен быть стерт.

Нормальные алгоритмы Маркова.

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

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

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

1. Постройте алгоритм Маркова: A={a,b,c,d}. В слове Р требуется заменить первое вхождение подслова bb на ddd и удалить все вхождения символа c.
2. Постройте нормальный алгоритм Маркова: A={0,1,2,3}. Пусть Р – непустое слово. Трактуя его как запись неотрицательного целого числа в четверичной системе счисления, требуется получить запись этого числа в двоичной системе счисления.
3. Постройте нормальный алгоритм Маркова для решения задачи: A={a,b}. В слове Р заменить на аа последнее вхождение символа а, если такой есть.
4. Постройте нормальный алгоритм Маркова для решения задачи: A={0,1}. Считая непустое слово Р записью двоичного числа, получить это же число, но в четверичной системе счисления.
5. Составьте нормальный алгоритм Маркова для решения задачи: A={a,b,c}. Удвоить каждый символ в слове Р.
6. Составьте нормальный алгоритм Маркова для решения задачи: A={0,1,2}. Считая непустое слово Р записью троичного числа уменьшить это число на 1.

Оценка скорости работы алгоритмов

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

Примеры решения задач:.

1. Следующий фрагмент программы записывает в переменную Max максимальный элемент в двумерном массиве Dist размера N*N, наполненном неотрицательными числами:

For i:=1 to N Do

For j:=1 to N Do

If Dist[I,j]>Max Then Max:= Dist[I,j];

        На очень медленном компьютере эта программа при N=1000 работала 5 секунд. Определите время работу этой программе на том же компьютере при N=2000:

Решение.

В данном алгоритме два вложенных оператора цикла. При увеличении N  в два раза количество проверок (выполнений оператора If) возрастет в 22, т.е. в 4 раза, т.е. 5*4=20 сек

2. Стандартный алгоритм вычисления среднего арифметического элементов числового массива из миллиона элементов работает 0, 5 сек. Оцените время работы того же алгоритма на том же компьютере, если длина массива 3 миллиона.  

Решение.

Для вычисления среднего арифметического N чисел необходимо выполнить N операций сложения. При увеличении количества  элементов в 3 раза время выполнения алгоритма возрастает линейно -  так же в 3 раза. Следовательно, время будет равно 0,5*3=1,5(сек)

Задачи для самостоятельного решения:

1. Стандартный алгоритм вычисления среднего арифметического элементов числового массива из тысячи элементов работает 0,01 сек. Оцените время работы того же алгоритма на том же компьютере, если длина массива миллион элементов.
2. Подсчитайте сложность алгоритма перемножений двух натуральных чисел столбиком при условии, что одно из чисел состоит из n десятичных цифр, а второе – из m десятичных цифр.
3. Подсчитать сложность алгоритма умножения двух натуральных чисел «русским» методом при условии, что одно из чисел состоит из n  десятичных цифр, а второе из m  десятичных цифр.
4. Вычислите сложность алгоритма поиска минимального и максимального значения в неупорядоченном массиве.
5. Вычислите временную сложность поиска максимального и минимального элемента одновременно
6. Вычислите сложность алгоритма вычисления факториала числа.
7. Вычислите сложность алгоритма сортировки слиянием относительно операций сравнения.
8. Пусть для некоторого алгоритма T(n)=an2 +bn+d, где a>0, b,d – отличные от нуля константы. Докажите, что такой алгоритм имеет сложность O(n2). Для этого подберите неотрицательную константу c так, что, начиная с некоторого n0, T(n)<=cn2.
9. Требуется упорядочить по весу в возрастающем порядке N непрозрачных банок с чаем, имея в своем распоряжении только чашечные весы без гирь. Напишите наиболее эффективный алгоритм решения этой задачи.