Очереди

Другой распространенной структурой данных является очередь В очереди узлы удаляются только с головы, а добавляются только в хвост очереди. По этой причине очереди часто называют структура­ми данных типа первым пришел - первым ушел (FIFO). Операции постановки в очередь и удаления из очереди носят названия enqueue (поставить в очередь) и dequeue (исключить из очереди).

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

Очереди также используются при организации буфера печати.

4.Нестрогое понятие алгоритма. Свойства алгоритмов. Уточнение понятия алгоритма. Алгоритм как абстрактная машина: алгоритмическая машина Поста, Тьюринга, тезис Тьюринга и его обоснование. Нормальные алгоритмы Маркова. Сопоставление алгоритмических моделей. Проблема алгоритмической разрешимости.

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

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

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

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

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

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

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

5. Массовость алгоритма: начальная система величин может выбираться из некоторого множества.

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

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

Дата добавления: 2015-07-16