Archive for Сентябрь, 2012

Эйлеров и Гамильтонов графы

Гамильтонов граф

Эйлеров граф

Эйлеров путьв графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.

Эйлеров цикл — это эйлеров путь, являющийся циклом.

Эйлеров граф — граф, содержащий эйлеров цикл.

MST. Алгоритмы Прима и Крускала

Это минимальное остовное дерево не уникально

Итак, имеется n городов, которые нужно объединить в единую телефонную сеть. Для этого достаточно проложить (n-1) телефонных линий между городами. Как соединить города так, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна?

Дерево. Свойства дерева

Примеры обхода

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

Языки программирования. Компиляторы и интерпретаторы

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

Моделирование. Этапы решения задач

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

Математическая модель — замена объекта-оригинала или явления (процесса) соответствующим аналогом при помощи математических зависимостей.

Графы

Неориентированный, несвязный, невзвешенный граф

Графом называется множество точек (вершин), некоторые из которых соединены отрезками (ребрами).

Граф является ориентированным, если для каждого ребра задано направление, в котором возможно движение по этому ребру. Если движение возможно в обоих направлениях, то граф называется неориентированным.