Файл: Энциклопедия учителя информатики. Выпуск 5 Е. В. Андреева, И. Н. Фалина Окончание. Начало см в 142007 10. Операторы языка программирования Оператор.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 713
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
скобки не сбалансированы”. Конец алгоритма.7. Если i-й символ равен “]”, то проверяем вершину стека: если в вершине стека находится “[”, то извлекаем ее из стека; переход на п. (2), иначе выдаем сообщение “скобки не сбалансированы”. Конец алгоритма.Очередь — частный случай линейного односвязного списка, для которого разрешены только две операции: добавление элемента в конец (хвост) очереди и удаление элемента из начала (головы) очереди.Понятие очереди действительно очень близко к бытовому термину “очередь”. Очередь покупателей в магазине хорошо описывается в терминах этой структуры данных.ДеревьяДерево — это совокупность элементов, называемых узлами, в которой выделен один элемент (корень), а остальные элементы разбиты на непересекающиеся множества (поддеревья), каждое из которых является деревом, при этом корень каждого поддерева является потомком корня дерева, т.е. все элементы связаны между собой отношением (предок–потомок). В результате образуется иерархическая структура узлов. Узлы, которые не имеют ни одного потомка, называются листьями. Над деревом определены следующие операции: добавление элемента в дерево, удаление элемента из дерева, обход дерева, поиск элемента в дереве.Пример 4. Дерево является наиболее удобной структурой данных для представления генеалогического дерева, с помощью которого можно решать задачи определения степени родства между двумя людьми.Используются деревья и для определения выигрышной стратегии в играх (см. статью “Игры. Выигрышные стратегии”), и для построения различных информационных моделей (см. “Информационные модели”).Особенно важную роль в информатике играют так называемые бинарные деревья.Двоичное (бинарное) дерево — частный случай дерева, в котором каждый узел может иметь не более двух потомков, являющихся корнями левого и правого поддерева.Если дополнительно для узлов дерева выполняется условие, что все значения элементов левого поддерева меньше значения корня дерева, а все значения элементов правого поддерева больше значения корня, то такое дерево называется деревом бинарного поиска и предназначено для быстрого поиска элементов. Алгоритм поиска в таком дереве работает так: искомое значение сравнивается со значением корня дерева, и в зависимости от результата сравнения поиск либо заканчивается, либо продолжается только в левом или только в правом поддереве соответственно. Общее количество операций сравнения не будет превосходить так называемую
высоту дерева — максимальное количество элементов на пути от корня дерева к одному из листьев. Так, высота изображенного на рисунке дерева равна 4.ГрафыГраф — это множество элементов, называемых вершинами графа вместе с набором отношений между этими вершинами, называемых ребрами графа. Графической интерпретацией этой структуры данных является множество точек, соответствующих вершинам, некоторые пары из которых соединены линиями или стрелками, которые соответствуют ребрам. В последнем случае граф называется ориентированным (см. также статьи “Графические модели” и “Табличные модели”).В силу того, что с помощью графов можно описывать объекты произвольной структуры, графы являются основным средством для описания структур сложных объектов и функционирования систем. Например, для описания вычислительной сети, транспортной системы, иерархической структуры (дерево является одной из разновидностей графа). Блок-схемы алгоритмов (см. “Способы записи алгоритмов”) также представляют собой графы.Если каждому ребру к тому же приписано некоторое число (вес), то такой граф называют взвешенным. Например, при описании с помощью графа системы дорог России важным является длина дороги (вес ребра графа), соединяющей те или иные населенные пункты (вершины графа). При этом на рисунке длины соответствующих ребер не обязаны соответствовать приписанным им весам, в отличие от карты дорог. Пример 5. В терминах взвешенного графа удобно решать следующую задачу. Правительство России составляет план строительства современных автомагистралей, соединяющих города, население которых превышает миллион человек. Какие именно дороги следует построить, чтобы из любого такого города можно было добраться в любой другой по новым автомагистралям, а общая длина дорог была бы минимальной?Эта задача в теории графов имеет простое и точное решение. Мы можем начать планирование сети дорог, начиная с любого города, например, Санкт-Петербурга. Соединим его с ближайшим городом-миллионником. Далее на каждом шаге к имеющейся сети добавляется кратчайшая дорога, которой можно соединить город, еще не присоединенный к сети, с одним из городов, уже включенных в сеть. Количество дорог будет, таким образом, на единицу меньше, чем число городов.Абстрактную структуру данных — граф — в программе можно представить несколькими способами, т.е. используя разные типы данных. Например, граф можно описывать с помощью списка ребер, задавая каждое ребро парой вершин и, при необходимости, весом. Наибольшее распространение получило табличное хранение графа (см. “
Табличные модели”), называемое также матрицей смежности, т.е. двухмерного массива, скажем, A, где для невзвешенного графа (или 1), если ребро между вершинами i и j существует, и (или 0) в противном случае. Для взвешенного графа A[i][j] равно весу соответствующего ребра, а отсутствие ребра в ряде задач удобно обозначать бесконечностью. Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали (i = j). C помощью матрицы смежности легко проверить, существует ли в графе ребро, соединяющее вершину i с вершиной j. Основной же ее недостаток заключается в том, что матрица смежности требует, чтобы объем памяти был достаточен для хранения N2 значений для графа, содержащего N вершин, даже если ребер в графе существенно меньше, чем N2.Методические рекомендацииПри объяснении понятия структуры данных можно воспользоваться следующей иллюстрацией.При решении любой задачи возникает необходимость работы с данными и выполнения операций над ними. Набор этих операций для каждой задачи, вообще говоря, свой. Однако, если некоторый набор операций часто используется при решении различных задач, то полезно придумать способ организации данных, позволяющий выполнять именно эти операции как можно эффективнее. После того, как такой способ придуман, при решении конкретной задачи можно считать, что у нас в наличии имеется “черный ящик” (его мы и будем называть структурой данных), про который известно, что в нем хранятся данные некоторого рода, и который умеет выполнять некоторые операции над этими данными. Это позволяет отвлечься от деталей и сосредоточиться на характерных особенностях задачи. Внутри (т.е. в компьютере) этот “черный ящик” может быть реализован различным образом, при этом следует стремиться к как можно более эффективной (быстрой и экономично расходующей память) реализации.Государственный образовательный стандарт предусматривает изучение различных структур данных как в базовом курсе основной школы, так и в старших классах. В курсе программирования основной школы в Примерной программе упоминаются в качестве обрабатываемых объектов цепочки символов (строки), числа, списки, деревья, графы. Однако в практических работах из данных сложной структуры упоминается только массив (см. статью “Операции с массивами
16. Теория алгоритмовТеория алгоритмов как раздел математики возникла в начале 30-х годов XX столетия в связи с необходимостью уточнения понятия алгоритма. Ранее, решая различные задачи, математики использовали интуитивное понятие алгоритма (см. статью “Алгоритм”). Но в связи с усложнением ставящихся задач у математиков стала возникать мысль, что не для всех задач можно найти процедуру решения, которая являлась бы алгоритмом, что впоследствии подтвердилось получением результатов о существовании алгоритмически неразрешимых проблем. Для доказательства факта отсутствия алгоритма необходимо было дать точное определение алгоритма. Ведь одно дело найти разрешающий алгоритм — это можно сделать, используя интуитивное понятие алгоритма. Другое дело — доказать несуществование алгоритма, для этого нужно знать точно, отсутствие чего мы доказываем. Попытки сформулировать такое определение привели в рамках математической логики к возникновению теории алгоритмов.В теории алгоритмов используются различные подходы к формализации понятий алгоритма и вычислимой функции. Поиск таких подходов проходил в трех направлениях. В первом всякий алгоритм вычисляет значение некоторой числовой функции, а его элементарные шаги — это арифметические операции. Последовательность шагов определяется с помощью суперпозиции — подстановки функций в функции, рекурсии — определения значения функции через ранее вычисленные значения этой же функции, и оператора минимизации, благодаря которому из всюду определенной функции можно получить не всюду определенную вычислимую функцию. Класс функций, порождаемый этими тремя операторами, называется классом частично-рекурсивных функций. Второе направление основано на определении алгоритмического процесса как процесса, осуществимого на конкретной теоретической машине. Примерами таких алгоритмических моделей являются “машина Тьюринга” и “машина Поста”. Третье направление отвлекается от конкретных машин (т.е. в этих моделях отсутствуют понятия “память”, “состояние машины” и т.п.). Наиболее известная алгоритмическая модель этого типа — нормальные алгоритмы Маркова.Все эти подходы привели к одному и тому же классу алгоритмически вычислимых функций. Указанные результаты составляют основу так называемой дескриптивной теории алгоритмов, основным содержанием которой является классификация задач по признаку алгоритмической разрешимости, т.е. получение высказываний типа “Задача П алгоритмически разрешима” или “Задача П алгоритмически неразрешима” (см. статью “
высоту дерева — максимальное количество элементов на пути от корня дерева к одному из листьев. Так, высота изображенного на рисунке дерева равна 4.ГрафыГраф — это множество элементов, называемых вершинами графа вместе с набором отношений между этими вершинами, называемых ребрами графа. Графической интерпретацией этой структуры данных является множество точек, соответствующих вершинам, некоторые пары из которых соединены линиями или стрелками, которые соответствуют ребрам. В последнем случае граф называется ориентированным (см. также статьи “Графические модели” и “Табличные модели”).В силу того, что с помощью графов можно описывать объекты произвольной структуры, графы являются основным средством для описания структур сложных объектов и функционирования систем. Например, для описания вычислительной сети, транспортной системы, иерархической структуры (дерево является одной из разновидностей графа). Блок-схемы алгоритмов (см. “Способы записи алгоритмов”) также представляют собой графы.Если каждому ребру к тому же приписано некоторое число (вес), то такой граф называют взвешенным. Например, при описании с помощью графа системы дорог России важным является длина дороги (вес ребра графа), соединяющей те или иные населенные пункты (вершины графа). При этом на рисунке длины соответствующих ребер не обязаны соответствовать приписанным им весам, в отличие от карты дорог. Пример 5. В терминах взвешенного графа удобно решать следующую задачу. Правительство России составляет план строительства современных автомагистралей, соединяющих города, население которых превышает миллион человек. Какие именно дороги следует построить, чтобы из любого такого города можно было добраться в любой другой по новым автомагистралям, а общая длина дорог была бы минимальной?Эта задача в теории графов имеет простое и точное решение. Мы можем начать планирование сети дорог, начиная с любого города, например, Санкт-Петербурга. Соединим его с ближайшим городом-миллионником. Далее на каждом шаге к имеющейся сети добавляется кратчайшая дорога, которой можно соединить город, еще не присоединенный к сети, с одним из городов, уже включенных в сеть. Количество дорог будет, таким образом, на единицу меньше, чем число городов.Абстрактную структуру данных — граф — в программе можно представить несколькими способами, т.е. используя разные типы данных. Например, граф можно описывать с помощью списка ребер, задавая каждое ребро парой вершин и, при необходимости, весом. Наибольшее распространение получило табличное хранение графа (см. “
Табличные модели”), называемое также матрицей смежности, т.е. двухмерного массива, скажем, A, где для невзвешенного графа (или 1), если ребро между вершинами i и j существует, и (или 0) в противном случае. Для взвешенного графа A[i][j] равно весу соответствующего ребра, а отсутствие ребра в ряде задач удобно обозначать бесконечностью. Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали (i = j). C помощью матрицы смежности легко проверить, существует ли в графе ребро, соединяющее вершину i с вершиной j. Основной же ее недостаток заключается в том, что матрица смежности требует, чтобы объем памяти был достаточен для хранения N2 значений для графа, содержащего N вершин, даже если ребер в графе существенно меньше, чем N2.Методические рекомендацииПри объяснении понятия структуры данных можно воспользоваться следующей иллюстрацией.При решении любой задачи возникает необходимость работы с данными и выполнения операций над ними. Набор этих операций для каждой задачи, вообще говоря, свой. Однако, если некоторый набор операций часто используется при решении различных задач, то полезно придумать способ организации данных, позволяющий выполнять именно эти операции как можно эффективнее. После того, как такой способ придуман, при решении конкретной задачи можно считать, что у нас в наличии имеется “черный ящик” (его мы и будем называть структурой данных), про который известно, что в нем хранятся данные некоторого рода, и который умеет выполнять некоторые операции над этими данными. Это позволяет отвлечься от деталей и сосредоточиться на характерных особенностях задачи. Внутри (т.е. в компьютере) этот “черный ящик” может быть реализован различным образом, при этом следует стремиться к как можно более эффективной (быстрой и экономично расходующей память) реализации.Государственный образовательный стандарт предусматривает изучение различных структур данных как в базовом курсе основной школы, так и в старших классах. В курсе программирования основной школы в Примерной программе упоминаются в качестве обрабатываемых объектов цепочки символов (строки), числа, списки, деревья, графы. Однако в практических работах из данных сложной структуры упоминается только массив (см. статью “Операции с массивами
”). В основной школе остальные структуры, видимо, имеет смысл изучать в первую очередь при построении графических и других моделей (см. раздел IV энциклопедии).
Примерная программа для профильной школы предполагает работу с числами, матрицами, строками, списками, деревьями. В качестве простой иллюстрации работы со списками можно выбрать организацию стека с помощью одномерного массива и целочисленной переменной, указывающей на вершину стека (“дно” стека при этом всегда находится в первом элементе массива). Помимо приведенной в статье задачи проверки скобок на сбалансированность, можно изучить работу стекового калькулятора на примере алгоритма перевода арифметического выражения в обратную польскую запись (постфиксную запись) из привычной нам инфиксной записи и дальнейшее вычисление значения арифметического выражения.
Бинарное дерево также легко представить в памяти компьютера с помощью одномерного массива, при этом в первом элементе массива будет храниться корень дерева, а потомки узла дерева, хранящегося в i-м элементе массива, будут располагаться в 2i-м и (2i + 1)-м элементах соответственно. Если потомок у узла отсутствует, то соответствующий элемент будет равен, например, 0. Рекурсивная процедура обхода дерева t и печати его элементов в этом случае будет выглядеть так:
procedure order(i:integer);
begin
if t[i] <> 0 then
begin
writeln(t[i]);
order(2*i);
order(2*i + 1)
end
end;
О реализации списков и массивов с помощью динамических переменных можно прочитать, например, в классической книге Н.Вирта “Алгоритмы и структуры данных”.
В программу для профильной школы включены и алгоритмы на графах. В частности, упоминается поиск кратчайшего пути в графе. Для невзвешенного графа решать эту задачу можно, например, с использованием алгоритма “поиска в ширину”, когда сначала помечаются вершины графа, соединенные ребром с исходной вершиной, затем все вершины, соединенные с помеченными, и т.д. Для взвешенного графа чаще всего используют алгоритм Дийкстры (см., например, статью Е.В. Андреевой “Олимпиады по информатике. Пути к вершине”, “Информатика” № 8/2002). Знание таких алгоритмов необходимо для успешного решения олимпиадных задач по информатике. Так, на IV федеральном окружном этапе Всероссийской олимпиады по информатике 2007 г. предлагалась задача “Окопы и траншеи”, решение которой как раз и сводилось к поиску кратчайшего пути во взвешенном графе.
16. Теория алгоритмовТеория алгоритмов как раздел математики возникла в начале 30-х годов XX столетия в связи с необходимостью уточнения понятия алгоритма. Ранее, решая различные задачи, математики использовали интуитивное понятие алгоритма (см. статью “Алгоритм”). Но в связи с усложнением ставящихся задач у математиков стала возникать мысль, что не для всех задач можно найти процедуру решения, которая являлась бы алгоритмом, что впоследствии подтвердилось получением результатов о существовании алгоритмически неразрешимых проблем. Для доказательства факта отсутствия алгоритма необходимо было дать точное определение алгоритма. Ведь одно дело найти разрешающий алгоритм — это можно сделать, используя интуитивное понятие алгоритма. Другое дело — доказать несуществование алгоритма, для этого нужно знать точно, отсутствие чего мы доказываем. Попытки сформулировать такое определение привели в рамках математической логики к возникновению теории алгоритмов.В теории алгоритмов используются различные подходы к формализации понятий алгоритма и вычислимой функции. Поиск таких подходов проходил в трех направлениях. В первом всякий алгоритм вычисляет значение некоторой числовой функции, а его элементарные шаги — это арифметические операции. Последовательность шагов определяется с помощью суперпозиции — подстановки функций в функции, рекурсии — определения значения функции через ранее вычисленные значения этой же функции, и оператора минимизации, благодаря которому из всюду определенной функции можно получить не всюду определенную вычислимую функцию. Класс функций, порождаемый этими тремя операторами, называется классом частично-рекурсивных функций. Второе направление основано на определении алгоритмического процесса как процесса, осуществимого на конкретной теоретической машине. Примерами таких алгоритмических моделей являются “машина Тьюринга” и “машина Поста”. Третье направление отвлекается от конкретных машин (т.е. в этих моделях отсутствуют понятия “память”, “состояние машины” и т.п.). Наиболее известная алгоритмическая модель этого типа — нормальные алгоритмы Маркова.Все эти подходы привели к одному и тому же классу алгоритмически вычислимых функций. Указанные результаты составляют основу так называемой дескриптивной теории алгоритмов, основным содержанием которой является классификация задач по признаку алгоритмической разрешимости, т.е. получение высказываний типа “Задача П алгоритмически разрешима” или “Задача П алгоритмически неразрешима” (см. статью “