Графы и деревья

Дерево (структура данных)

Дерево — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связанным графом, не содержащим циклы. Большинство источников также добавляют условие на то, что рёбра графа не должны быть ориентированными. В дополнение к этим трём ограничениям, в некоторых источниках указываются, что рёбра графа не должны быть взвешенными.

Определения

· Корневой узел — самый верхний узел дерева.

· Корень — одна из вершин, по желанию наблюдателя.

· лист, листовой или терминальный узел — узел, не имеющий дочерних элементов.

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

Дерево считается ориентированным, если в корень не заходит ни одно ребро.

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин.

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.

Лекция №3. Конечные автоматы. Машина Тьюринга и машина Поста.

План лекций

1. Конечные автоматы.

2. Машина Тьюринга и машина Поста.

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

Иллюстративный материал: Таблица, схема.