(см. раздел 1.1, 1.2 ULLDSA)
Моделирование проблемы как дискретной математической структуры
Имея проблему, которую необходимо решить, мы можем моделировать определенные аспекты проблемы, переводя ее в одну или несколько дискретных математических структур (ДМС). Например. проблема светофора может быть смоделирована с использованием структуры графа.
Представление дискретной математической структуры в виде абстрактного типа данных
Математическая модель может быть представлена на языке программирования путем объявления абстрактного типа данных (ADT).
АТД — это объявление интерфейса математической модели, которую он представляет. Например. математическая структура «граф» может быть представлена на языке программирования, таком как Python, как класс с именем Graph с общедоступными методами add_vertex, add_edge, remove_edge, и т. д. вместе с другим классом ADT с именем Vertex с общедоступными методами get_neighbors, is_neighbor, set_property и т. д.
Дискретная математическая концепция графа предоставляет множество операций/методов, которые должны выполняться на графе (перечисление ребер вершины, поиск в глубину, поиск в ширину и т. д.). С точки зрения проблемы, мы начинаем думать о графе как о части модели и представляем его как АТД графа и вершины только с соответствующими общедоступными методами. Интерфейс для этих АТД остается неизменным, так что программы (клиентский код) могут быть написаны с учетом этого интерфейса/контракта. Базовая реализация может измениться, не затрагивая клиента. Поля данных АТД реализуются с помощью структур данных, а методы интерфейса реализуются с помощью алгоритмов, работающих с этими структурами данных.
Другим примером моделирования является задача о рюкзаке, где дан набор товаров, и мы должны выбрать такие товары, чтобы их стоимость была максимальной, при условии ограничения максимального веса выбранных товаров. Моделирование включает в себя дискретную математическую структуру множества. Представлением набора является приоритетная очередь АТД с методами insert и deleteMin. Обычно многие АТД (список, стек, очередь, карта, словарь, приоритетная очередь и т. д.) доступны в языковой библиотеке.
Структуры данных и алгоритмы архитектуры процессора (набора инструкций)
Микропроцессор реализует схему для выполнения определенных операций со значениями, хранящимися в его регистрах и блоках памяти на материнской плате (ОЗУ). Схема интерпретирует значение, хранящееся в регистре, как структуру данных типа целое число, вещественное число, символ/строка, логическое значение или указатель. Также имеется схема для выполнения операций создания, выбора, обновления и удаления этих структур данных. Интерпретация типа и выполняемая операция закодированы в «коде операции», который действует как оператор. Операнды — это структуры данных, предоставляемые коду операции различными схемами адресации, одной из которых является указатель. Машинная инструкция объединяет код операции и его операнды. Спецификация кодов операций, схем адресации, структур данных и т. д. называется архитектурой набора инструкций (ISA). Язык программирования предоставляет типы данных базовой ISA как примитивные типы данных.
Язык программирования также предоставляет средства структурирования данных для агрегирования полей примитивных данных и формирования составных типов данных. Этими средствами структурирования данных являются такие вещи, как структура, класс, массив, файл и т. д.
Набор инструкций также предоставляет конструкции управления потоком, такие как LOOP, JMP, CALL и т. д. Язык программирования предоставляет их как конструкции управления потоком, такие как for, while, if и т. д., а также как вызов и возврат функции.
Структуры данных и алгоритмы абстрактных типов данных
Поля данных и методы АТД реализуются с использованием средств структурирования данных и конструкций потока управления, предоставляемых языком программирования. Для Graph ADT мы можем выбрать структуру данных двумерного массива или структуру данных списка смежности (отображение/ассоциативное хранилище). Список смежности представляет собой композицию массива, где каждый элемент представляет собой связанный список. Это также может быть отображение vertex_id в АТД вершины, при этом АТД вершины имеет карту соседей, отображающую имя соседней вершины на вес ребра. Таким образом, у нас могут быть вложенные АТД, которые в конечном итоге реализуются с использованием таких структур данных, как массивы, связанные списки, деревья, хеш-таблицы и т. д.
Многие АТД и их реализации предоставляются языковой библиотекой. Для непредоставленных АТД нам необходимо объявить и реализовать их. Как только мы реализуем АТД, алгоритм может использовать АТД и решить проблему. Для задачи светофора мы выбрали графовую (дискретную математическую) модель, представленную в виде графового АТД и реализованную с использованием структуры данных списка смежности. Мы выбрали граф, потому что хотели решить задачу с помощью алгоритма Graph Coloring.
С точки зрения проблемы мы можем рассматривать АТД графа как структуру данных, а раскраску графа как алгоритм. На один уровень глубже в ADT мы можем рассматривать список смежности как структуру данных и get_neighbors как алгоритм. На еще одном (вложенном) уровне мы можем рассматривать хеш-таблицу как структуру данных (реализующую список смежности) и ее методы вставки, удаления и членства. Еще один уровень глубже, мы можем взглянуть на структуру данных указателя [eax] и алгоритм MOV.
Дизайн алгоритма
Любая композиция конструкций потока управления является алгоритмом. Реализация метода get_neighbors Vertex ADT представляет собой алгоритм, как и метод раскраски графа. Но есть различие. Алгоритмы методов АТД служат для реализации потребностей структуры и навигации по АТД, в то время как алгоритм раскраски графа работает с представлением (интерфейс графа) дискретной математической модели (граф модель) для решения проблемы.
Все стандартные алгоритмы имеют некоторые базовые принципы разработки алгоритмов (жадные алгоритмы, динамическое программирование и т. д.). Таких принципов сравнительно немного. Знание этих принципов проектирования помогает нам понять стандартные алгоритмы, а также повышает нашу способность разрабатывать собственные алгоритмы.
Раскраска графа — жадный подход
Код можно найти на github.
В следующем коде вы можете увидеть схему жадного алгоритма Select — Feasible — Union.
График проблемы светофора (рис. 1.2) раскрашен в 4 цвета. Когда вы запускаете GreedyGraphColoringTest, вывод выглядит следующим образом:
For Color.turquoise AB AC AD BA DC ED For Color.indigo BC BD EA For Color.magenta DA DB For Color.cyan EB EC
использованная литература
Структуры данных и алгоритмы — Ахо, Хопкрофт, Ульман
Первоначально опубликовано на https://jeetendradhall.github.io.
