1. Теория графов. Термины и определения в картинках
В этой статье мы познакомимся с основными терминами и определениями Теории графов. Каждый термин схематично показан на картинках. Читать
2. Способы хранения графа в памяти компьютера
В продолжение предыдыдущей статьи обсудим различные способы представления графа в памяти компьютера для его обработки. Покажем, какие структуры данных можно использовать, а также проговорим преимущества и недостатки каждого способа. Читать
3. Разделяй и Властвуй. Разбор задач
В этой статье мы рассмотрим два примера задач с пояснениями и кодом, в которых будет использоваться этот подход. Для начала сформулируем, разделение и властвование. Решение задачи с помощью данного подхода обладает следующими тремя свойствами:
- Разделить входные данные на меньшие подмножества.
- Решить подзадачи рекурсивно.
- Объединить решения подзадач в решение исходной задачи.
Попробуем узнать эти свойства на практике и попытаемся решить две задачи. Читать
4. Алгоритм Дейкстры. Разбор Задач
«Поиск оптимального пути в графе» — такая задача встречается довольно часто и в повседневной жизни, и в мире технологий. Справиться с такими вызовами помогает подход, который должен быть в арсенале каждого программиста — алгоритм Дейкстры.
Если вы хотите найти ответить на вопросы, чем этот алгоритм лучше BFS (поиска в ширину), при каких условиях алгоритм применим, и какие теоретические и практические задачи можно с его помощью решать, читайте далее.
5. Байесовская Сеть Доверия: Практика
В этой статье мы сначала вкратце вспомним теорию. Дальше будет, что называется, только хардкор: на примере данных «Титаника» мы будем строить БСД. Читать
6. Префиксное дерево (trie)
В этой статье обсудим такую структуру данных, как «префиксное дерево» (оно же нагруженное дерево, бор, trie, prefix tree). Кратко рассмотрим основы и реализуем наиболее важные операции: вставку, поиск по ключу и префиксный поиск. Читать
7. Префиксное дерево (trie) — вставка и поиск
Префиксное дерево (нагруженное дерево, trie) — структура данных для эффективного поиска. С его помощью сложность поиска можно довести до оптимального уровня — длины ключа. Вспомним, что в хорошо сбалансированном бинарном дереве поиска данные можно найти за время, пропорциональное M * log N, где M — максимальная длина строки, а N — количество ключей в дереве. В префиксном дереве — O(M), но увеличиваются требования к памяти. Читать далее
