Файл: информатика.doc

Динамическое распределение памяти

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

Для динамического распределения памяти необходимо применение функ­ций malloc и free, а также операции sizeof. Функция malloc принимает в ка­честве аргумента число байт, которое необходимо выделить, и возвращает ука­затель на выделенную память типа void*. Указатель void* можно присвоить любой переменной-указателю. Функция malloc обычно используется совмест­но с операцией sizeof. Например, оператор

newPtr = malloc(sizeof(struct node));

оценивает sizeof(struct node) для определения размера в байтах структуры типа struct node, выделяет новый блок памяти размером в sizeof(struct node) байт, и сохраняет указатель на выделенную память в переменной newPtr. Если необходимого количества памяти нет в наличии, malloc возвращает указатель NULL.

Функция free освобождает память, т.е. память возвращается системе, и в дальнейшем ее можно выделить снова. Для высвобождения памяти, динами­чески выделенной предыдущим вызовом оператора malloc, используется опе­ратор

free(newPtr);

Связанные списки

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

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

Стеки

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

Разница между стеком и свя­занными списками в том, что вставку и удаление в связанных списках можно выполнять в любом месте, а в стеке только сверху.

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

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

Очереди

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм как абстрактная машина

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

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

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

Как и в машине Поста, лента разбита на отдельные ячейки, однако, в машине Тьюринга неподвижной является головка, а лента передвигается относительно нее вправо или влево. Другим отличием является то, что она работает не в двоичном, а некотором произвольном конечном алфавите A={h, a_h ..., а_п} - этот алфавит называется внешним. В нем выделяется специальный символ - А, называемый пустым знаком - его посылка в какую-либо ячейку стирает тот знак, который до этого там находился, и оставляет ячейку пустой. В каждую ячейку ленты может быть записан лишь один символ. Информация, хранящаяся на ленте, изображается конечной последовательностью знаков внешнего алфавита, отличных от пустого знака.

Головка всегда расположена над одной из ячеек ленты. Работа происходит тактами (шагами). Система исполняемых головкой команд предельно проста: на каждом такте она производит замену знака в обозреваемой ячейке aj знаком а_;. При этом возможны сочетания:

• в обозреваемой ячейке знак не изменился;

• хранившийся в ячейке знак заменяется пустым, т.е. стирается;

• пустой знак заменяется непустым (с номером у в алфавите), т.е. производится вставка знака соответствует замене одного знака другим.

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

Слово - это любая конечная последовательность знаков алфавита.

Число символов в слове называется его длиной.

Слово, длина которого равна нулю, называется пустым.

Слово s называется подсловом слова q_t если q можно представить в виде q-rst_f где rut- любые слова в том лее алфавите (в том числе и пустые).

Теперь можно определить понятие алгоритма (не являющееся строгим):

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

В алгоритмах Маркова в качестве элементарного шага алгоритма принимается подстановка одного слова вместо другого. Пусть в алфавите А построено исходное слово Р, которое содержит подслово Р_г (в общем случае таких подслов в исходном слове может быть несколько), а также имеется некоторое слово Р_к в том же алфавите.

Подстановкой называется замена первого по порядку подслова Р_г исходного слова Р на слово Р_к. Обозначается подстановка P_r-^P_k.

Алгоритм в данной форме представления задается системой подстановок, которая представляет собой последовательность (список) подстановок. Если в этом списке имеются подстановки с левыми частями, которые входят в Р, то первая из них применяется к Р, в результате чего оно переходит в другое слово Pj. К нему вновь применяется схема подстановок и т.д. Процесс прекращается в двух случаях: либо в списке не нашлось подстановки с левой частью, входящей в Р_п, либо при получении Р_п была применена последняя подстановка.