Темы

Алгоритмические техники

Algorithmic Techniques · 42 статей

  1. Алгоритм поиска в ширину в графах

    Поиск в ширину (BFS): алгоритм обхода графов и деревьев. Находит узел с заданным свойством, исследуя уровни по очереди. Применяется в ИИ и задачах поиска.

    #22572 · 4 мин чтения

  2. Алгоритм A* для поиска пути и обхода графов

    Алгоритм A* (А звезда): поиск пути и обход графов. Эффективный, оптимальный, но требовательный к памяти. Применение в компьютерных науках с 1968 года.

    #23318 · 4 мин чтения

  3. Полный перебор: метод решения задач в информатике.

    Полный перебор (brute force) в информатике: простой, но ресурсоемкий метод решения задач. Обзор алгоритма, примеры и ограничения по размеру данных.

    #23843 · 7 мин чтения

  4. Алгоритм сопоставления с образцом Rete

    Алгоритм Rete: эффективный поиск соответствий для систем, основанных на правилах. Разработан в 1974 г. Чарльзом Форджи, оптимизация работы с базами знаний.

    #52474 · 21 мин чтения

  5. Автоматическое создание лабиринтов

    Генерация лабиринтов: автоматические алгоритмы создания, включая рекурсивный алгоритм поиска в глубину. Простое создание лабиринтов на компьютере.

    #58382 · 7 мин чтения

  6. Метод Акры-Баззи для анализа рекуррентных соотношений

    Метод Акры-Баззи: анализ асимптотики рекуррентных соотношений в алгоритмах "разделяй и властвуй" с разными размерами подзадач. Обобщение мастер-теоремы.

    #63731 · 2 мин чтения

  7. Дилемма встречи в парке: логический анализ и стратегии

    Логическая дилемма встречи: что выбрать – ждать в парке или искать? Разбор классической задачи о координации и оптимальной стратегии для успешной встречи.

    #64599 · 2 мин чтения

  8. Алгоритм поиска с возвратом (откатом)

    Алгоритм поиска с возвратом: принцип работы, пример (8 ферзей). Эффективен для задач с частичными решениями и быстрой проверкой на валидность.

    #65173 · 4 мин чтения

  9. Итеративное углубление поиска: стратегии и ограничения

    Итеративное углубление поиска (IDDFS): оптимальный алгоритм поиска в графах. Повторяет поиск в глубину с возрастающей глубиной до нахождения цели. Эффективен и улучшает эвристики.

    #97720 · 2 мин чтения

  10. Иерархическая кластерная группировка: методы и анализ

    Иерархическая кластеризация: методы анализа данных для построения иерархии кластеров. Агломеративный и дивизивный подходы, дендрограммы.

    #105045 · 2 мин чтения

  11. Алгоритм Apriori для поиска часто встречающихся наборов элементов и ассоциативных правил

    Алгоритм Apriori для поиска часто встречающихся наборов данных и ассоциативных правил в базах данных. Анализ рыночной корзины, выявление трендов.

    #123276 · 1 мин чтения

  12. Недетерминированные алгоритмы: поведение и применение

    Недетерминированные алгоритмы в программировании: поведение зависит от запуска, случайности или условий гонки. Различия в результатах при одинаковых данных.

    #131648 · 2 мин чтения

  13. Обнаружение циклов в итерированных функциях

    Обнаружение циклов в алгоритмах: поиск повторений в последовательностях итераций функций. Эффективные алгоритмы для выявления циклов и оптимизации памяти.

    #132156 · 4 мин чтения

  14. Пространство и время в алгоритмах: компромиссы и оптимизация.

    Алгоритмическая торговля: компромисс между временем и памятью. Оптимизация алгоритмов – снижение времени выполнения за счет увеличения объема используемой памяти.

    #144246 · 2 мин чтения

  15. Алгоритм Марзулло: Выбор источников точного времени и вычисление пересечений интервалов.

    Алгоритм Марзулло: выбор точных источников времени, используемый в NTP и для оценки пересечения множеств. Эффективен при неточных данных.

    #144537 · 3 мин чтения

  16. Метод амортизированного анализа: учетные методы в алгоритмах и финансовой отчетности

    Метод амортизированного анализа в компьютерных науках: учет операций для оценки сложности алгоритмов. Интуитивный подход к определению стоимости операций.

    #184229 · 1 мин чтения

  17. Алгоритм планирования дискового ввода-вывода "Лифт" (SCAN)

    Алгоритм SCAN (Elevator) для планирования доступа к диску: оптимизация перемещения головок, обслуживание запросов в одном направлении для повышения эффективности.

    #193558 · 1 мин чтения

  18. Алгоритм выбора оптимальных источников для оценки времени

    Алгоритм выбора источников времени: Intersection и Marzullo. Точная оценка времени в NTP, выбор надежных источников, интервалы и центры смещений.

    #200664 · 2 мин чтения

  19. Оптимизация умножения матриц: динамическое программирование и алгоритмы

    Оптимизация умножения матриц: алгоритм нахождения минимальной стоимости вычислений цепи матриц. Динамическое программирование, псевдокод и Python реализация.

    #226786 · 3 мин чтения

  20. Поиск лучшим лучом: Эвристический алгоритм поиска

    Поиск в ширину (beam search): эффективный эвристический алгоритм для исследования графов. Оптимизация памяти по сравнению с best-first search. ИИ, компьютерные науки.

    #241699 · 1 мин чтения

  21. Алгоритмы, нечувствительные к размеру кэша

    Кэш-независимые алгоритмы: эффективная работа с памятью без учёта размера кэша. Оптимизация производительности на разных системах и уровнях кэша.

    #249923 · 2 мин чтения

  22. Псевдо-LRU: Алгоритмы кэширования и их реализация.

    Псевдо-LRU (PLRU): алгоритмы кэширования, улучшающие LRU за счет приближенной оценки возраста данных. Tree PLRU и bit PLRU – в Intel 486 и PowerPC.

    #263585 · 2 мин чтения

  23. Алгоритм минимальных конфликтов для решения задач об ограничениях.

    Алгоритм Min-Conflicts: эффективный метод решения задач с ограничениями в информатике. Подбор значений переменных для минимизации конфликтов и поиска решения.

    #271859 · 3 мин чтения

  24. Массивы Костаса: Геометрическое расположение точек на сетке

    Массивы Костаса: математические структуры для радаров и сонаров. Уникальные наборы точек на сетке, оптимизированные для автокорреляционных функций.

    #277942 · 2 мин чтения

  25. Эвристический алгоритм поиска пути IDA*

    Алгоритм IDA*: поиск кратчайшего пути в графах с использованием эвристики. Экономия памяти по сравнению с A*, но с повторным посещением узлов.

    #295075 · 2 мин чтения

  26. Principal variation search

    #298237 · 3 мин чтения

  27. Переплетение вычислений: техника "ласточкин хвост"

    Переплетение вычислений (dovetailing) в алгоритмах: одновременное выполнение задач для обхода бесконечных путей и эффективного поиска решений.

    #321923 · 2 мин чтения

  28. Диаграммы-бабочки в алгоритмах БПФ

    Быстрые преобразования Фурье (FFT): объяснение "бабочки" – ключевого элемента алгоритма Cooley-Tukey. Структура вычислений, радикс, Viterbi алгоритм.

    #332931 · 1 мин чтения

  29. Танцующие связи: техника для алгоритма точного покрытия

    Танцующие связи (DLX) – техника для эффективной работы с двусвязными списками и алгоритмом поиска точного покрытия. Применяется в задачах, как судоку.

    #334859 · 3 мин чтения

  30. Алгоритмы GSAT и WalkSAT для решения задач выполнимости булевых формул.

    GSAT и WalkSAT: локальные алгоритмы поиска решений для задач выполнимости булевых формул. Работают с КНФ, случайным назначением переменных и перебором.

    #343059 · 2 мин чтения

  31. Частичный порядок редукции в верификации компьютерных систем

    Уменьшение пространства состояний при верификации систем: частичный порядок редукции. Методы снижения сложности model checking, stubborn и ample sets.

    #359477 · 1 мин чтения

  32. Двунаправленный поиск: алгоритмы и применение эвристик.

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

    #365737 · 3 мин чтения

  33. Стражевое значение в программировании

    Сторожевое значение в программировании: особый флаг для завершения алгоритмов и циклов. Альтернатива указанию размера данных, избегающая ошибок.

    #379928 · 2 мин чтения

  34. Алгоритм X для решения задачи об точном покрытии

    Алгоритм X для задачи точного покрытия: рекурсивный поиск решения с использованием техники "танцующих связей" (DLX). Матрица 0 и 1, выбор строк.

    #396677 · 2 мин чтения

  35. Локальная согласованность в задачах поиска решений с ограничениями.

    Локальная согласованность в задачах на ограничения: методы уменьшения пространства поиска (node, arc, path consistency). Распространение ограничений (constraint propagation).

    #414261 · 22 мин чтения

  36. Методы предвидения в алгоритмах возврата: обзор и сравнение.

    Алгоритмы с возвратом: что такое "look ahead"? Выбор переменных и порядка значений для эффективного решения задач с ограничениями. Оптимизация поиска.

    #417211 · 2 мин чтения

  37. Метод отката с перескоком в алгоритмах поиска с возвратом

    Алгоритмы с возвратом: техника backjumping для сокращения пространства поиска и повышения эффективности. Оптимизация поиска решений в задачах с ограничениями.

    #418492 · 9 мин чтения

  38. Обучение ограничениям в алгоритмах поиска с возвратом

    Обучение ограничениям в алгоритмах поиска с возвратом: повышение эффективности за счет запоминания новых ограничений при обнаружении противоречий. Поиск решений.

    #419228 · 4 мин чтения

  39. Нить Ариадны: Метод решения проблем

    Метод "Нить Ариадны": логичный подход к решению сложных задач и головоломок. Систематизация вариантов и отслеживание пройденного пути для достижения цели.

    #423945 · 4 мин чтения

  40. Гибридные алгоритмы решения задач удовлетворения ограничений

    Гибридные алгоритмы ИИ для решения задач с ограничениями: сочетание поиска и логического вывода. Эффективны для широкого спектра задач и проблем.

    #429114 · 1 мин чтения

  41. Stochastic diffusion search

    #468997 · 2 мин чтения

  42. List ranking

    #506507 · 1 мин чтения