1) если номер позиции большего из элементов больше номера позиции меньшего элемента, то меняем их местами

2) если номер позиции меньшего из элементов больше номера позиции большего элемента, то не меняем их местами

3) если номер позиции меньшего из элементов больше номера позиции большего элемента, то оставляем их на месте

4) если номер позиции меньшего из элементов больше номера позиции большего элемента, то меняем их местами

Теоретические вопросы

Ответ на вопрос должен содержать от 2 до 5 страниц текста

1. Неформальное понятие алгоритма. Алгоритм как формальная математи­ческая система. Основные требования к алгоритмам. Формы представления алгоритмов.

2.  Эффективность, сходимость, сложность, надежность алгоритмов.

3. Абстрактные машины. Система команд. Примеры схем машины Поста и Тьюринга.  Вычислимые по Тьюрингу функции. Основная гипотеза теории алгоритмов

4. Рекурсивные функции, примитивно-рекурсивные функции и операторы, схемная интерпретация примитивной рекурсии, частично рекурсивные и общерекурсивные функции. Тезис Черча.

5. Нормальные алгоритмы Маркова. Способы композиции нормальных алгоритмов Маркова;

6. Основные понятия структурного программирования. Использование метода пошаговой детализации при проектировании структуры программного обеспечения

7. Понятие рекурсии. Глубина рекурсии. Рекурсивные методы.

8. Задачи поиска по критерию. Полный перебор. Перебор с возвратом.

Понятие эвристики. Эвристические методы в программировании.

9. Сортировка данных.  Алгоритмы сортировки элементов массива.

10. Сложность алгоритмов. Временная сложность алгоритма. Объемная сложность алгоритма. Оценка порядка. Определение сложности алгоритмов.

Практические задания

    Разработать алгоритм задачи в виде блок-схемы. Указать описание входных и выходных данных. Выполнить трассировку.

1. Сформировать массив А[1..10], элементы которого выбираются случайным образом из интервала [10,90]. Определить методом последовательного поиска, содержит он заданное число. Если элемент найден, то удалить его из массива.

2. Сформировать массив А[1..18], элементы которого выбираются случайным образом из интервала [-20, 40]. Определить методом последовательного поиска, содержит он заданное число. Если элемент не найден, то вставить его на последнее место.

3. Сформировать массив А[1..12], упорядоченный по возрастанию. Методом бинарного поиска определить, содержит ли он заданное число. Если элемент найден, то удалить его из массива.

4.  Сформировать массив А[1..10], упорядоченный по убыванию. Методом бинарного поиска определить, содержит ли он заданное число. Если элемент не найден, то вставить его в массив на второе место.

5. Задан массив В[1..20]. Отсортировать все элементы, стоящие на нечетных местах по невозрастанию.

6. Задан массив B[1..30]. Отсортировать все элементы с n-го по k-ый по неубыванию.

7. Задан массив B[1..20] , элементы которого выбираются случайным образом из отрезка [30, 100]. Отсортировать элементы с 1-го по 10-ый по невозрастанию, а с 11-го по 20-й - по. неубыванию.

8. Сформировать массив А[1..12], упорядоченный по возрастанию. Методом бинарного поиска определить, содержит ли он заданное число. Если элемент найден, то удалить его и следующий за ним элемент из массива.

9. Задан массив X[1..20], элементы которого выбираются случайным образом из отрезка [-30, 80]. Отсортировать все элементы с 5-го по 15-й по невозрастанию.

10. Сформировать массив а[1..10], упорядоченный по возрастанию. Методом бинарного поиска определить, содержит ли он заданное число. Если элемент не найден, то вставить его в массив на первое место.

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

по дисциплине «Теория алгоритмов»

1. Неформальное понятие алгоритма. Алгоритм как формальная математи­ческая система.

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

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

4.  Эффективность, сходимость, сложность, надежность алгоритмов

5. Машина Поста. Примеры схем машины Поста. 

6. Рекурсивные функции, примитивно-рекурсивные функции и операторы.

7. Нормальные алгорифмы Маркова. Способы композиции нормальных алгорифмов Маркова;

8. Основные понятия структурного программирования. Использование метода пошаговой детализации при проектировании структуры программного обеспечения

9. Понятие рекурсии. Глубина рекурсии. Рекурсивные методы.

10. Задачи поиска по критерию. Полный перебор. Перебор с возвратом.

11. Базовые алгоритмические структуры.

12. Сортировка данных Алгоритмы сортировки.

13. Сложность алгоритмов. Временная сложность алгоритма. Объемная сложность алгоритма.

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

Список рекомендуемой литературы

Основные источники:

1. Кормен, Т. Х. Алгоритмы: построение и анализ / Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн — М.: Вильямс, 2012. – 1296 с..

2. Кнут, Д. Э. Искусство программирования, том 1. Основные алгоритмы / Д. Э. Кнут. — М.:, «Вильямс», 2010. – 720 с.

3. Семакин, И. Г. Основы программирования / И. Г. Семакин, А. П. Шестаков. – М.: Издательский центр «Академия», 2006. – 432 с.

4. Игошин В.И. Теория алгоритмов: учеб.пособие для студентов учреждений СПО / В.И.Игошин. – М.:Издательский центр «Академия», 2013 – 320с.

Дополнительные источники:

1. Андреева, Е. В. Математические основы информатики. Элективный курс: учебное пособие / Е. Л. Андреева, Л. Л. Босова, И. Н. Фалина. – М.: БИНОМ. Лаборатория знаний, 2012. – 312 с..

2. Грэхем, Р. Л., Конкретная математика. Математические основы информатики / Р. Л. Грэхем, Д. Э. Кнут, О. Паташник. – М.: Вильямс, 2010. – 784 с.