Сложность строгого определения алгоритма

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

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

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

Идея о существовании алгоритмически неразрешимых проблем оказалась верной, но для того, чтобы ее обосновать, необходимо было дать точное формальное определение алгоритма. Попытки выработать такое определение привели к возникновению теории алгоритмов, в которую вошли труды многих известных математиков – К.Гедель, А.Тьюринг, А.Колмогоров и многие другие.

Точное определение понятия алгоритма дало возможность доказать алгоритмическую неразрешимость многих математических проблем.

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

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

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

Машина Поста как уточнение понятия алгоритма

Алгоритм (по Посту) — программа для ма­шины Поста, приводящая к решению поставленной за­дачи.

Тезис Поста. Всякий алгоритм представим в форме машины Поста.

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

Кроме ленты в машине Поста имеется каретка (головка чтения/записи), которая:

• умеет двигаться вперед, назад и стоять на месте;

• умеет читать содержимое, стирать и записывать 0 или 1;

• управляется программой.

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

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

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

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

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

5. Останов.

6. Если 0, то перейти к i-й строке программы, иначе перейти к 7-й строке программы.

Состояние машины — это состояние ленты и положение каретки. Список недопустимых действий, ведущих к аварийной остановке машины:

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

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

• уход каретки в бесконечность.

«Машиной» эта математическая конструкция называется потому, что в ней используются некоторые понятия реальных машин — память, команда и пр.

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

-> а — шаг вправо, перейти к строке с номером а;

<— а — шаг влево, перейти к строке с номером а;

V а — записать отметку,  перейти к строке с номером а;

X а — стереть отметку, перейти к строке с номером а;

? a; b — просмотреть ячейку; если в ячейке находится 0, то перейти к строке с номером а, иначе — к строке с номером b;

 !   — останов.

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

В машине Поста состояние описывает местонахождение каретки и состояние ленты.

Билет №15. Алгоритмическая сложность. Алгоритмы поиска.

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

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

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

Находится средний элемент последовательности. Для этого первый и последний элементы связываются с переменными, а средний вычисляется.

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

Одна из границ исследуемой последовательности становится равной предыдущему или последующему среднему элементу из п.2.

Снова находится средний элемент, теперь уже в «выбранной» половине. Описанный выше алгоритм повторяется уже для данной последовательности.

Билет № 16. Алгоритмическая сложность. Алгоритмы сортировки.

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

Анализ алгоритмов сортировки.

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

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

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

· Время

· Память

· Оптимальность и эффективность

Сортировка простыми обменами, сортиро́вкапузырько́м (англ. bubblesort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов.

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

Билет №17. Понятие информации. Количество информации. Единицы измерения информации. Формула Хартли и алфавитный подход к измерению информации.

Понятие информации

С точки зрения человека информация – сведения, обладающие такими характеристиками: понятность, достоверность, новизна, актуальность(ценность).

Информация – это энергия.

Согласно американскому ученому и инженеру Шеннону, информация – это снятая неопределенность.

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

Количество информации

Количество информации в теории информации – это количество информации в одном случайном объекте относительно другого.

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