Главная Пишите

Алгоритмы и структуры данных

Алгоритм, алгорифм (от algorithmi, algorismus, первоначально — латинская транслитерация имени математика аль-Хорезми) - способ (программа) решения вычислительных и других задач, точно предписывающий, какие процедуры необходимо выполнить и в какой последовательности, чтобы получить результат, однозначно [не обязательно] определяемый исходными данными. Алгоритм — одно из основных понятий математики и кибернетики. В вычислительной технике для описания алгоритма используются языки программирования.

Разделы страницы:

• Алгоритмы - общая информация
• Информационные технологии и алгоритмы в науке
• Алгоритмическое обеспечение (библиотеки)
• Полезные алгоритмы для АРМов
• Структуры данных
• Литература по алгоритмам

Информацию о численных методах и математическом моделировании смотрите на странице по дискретной математике.

Алгоритмы - общая информация

Обзоры по истории алгоритмических методов

Отец алгебры и алгоритмических методов Аль-Хорезми (~786-850 г., Багдад) был не только математиком, но и автором значительной работы в области географии, где он дал определение широты и долготы 2402 населенных пунктов мира в качестве основы карты мира [! кто измерил и предоставил ?]. Аль-Хорезми написал также ряд других менее известных работ по таким темам, как астролябия, летоисчисление, солнечные часы. Наряду с этими произведениями им была составлена политическая история, в которой были представлены гороскопы известных деятелей.

• Алгоритм на Кругосвете.
• Аль-Хорезми - основатель Алгебры.

Теория алгоритмов

Список основных разделов теории алгоритмов (взято из Википедии):

• Анализ алгоритмов (Analysis of algorithms)
• Аппроксимирующая схема реального времени (Polynomial time approximation scheme)
• Виртуальные вычисления и алгоритмы (Online computations and algorithms)
• Время выполнения (Running time)
• Гипервычисления (Hypercomputation)
• Лучшие и худшие случаи (Best and worst cases)
• O-нотация (Big O notation)
• Размер задачи (Problem size)
• Реализация (Implementation)
• Супертьюринговые вычисления (Super-Turing computation)
• Теория вычислимости (Computability theory)
• Теория вычислительной сложности (Computational complexity theory)
• Численный анализ (Numerical analysis)
• Embarrassingly parallel problem
• Эвристика (Heuristic)
• Алгоритм Лас Вегаса (Las Vegas algorithm)
• Алгоритм Монте-Карло (Monte Carlo algorithm)
• Алгоритм муравейника (Ant colony algorithm)
• Алгоритм обхода графа (Graph exploration algorithm)
• Алгоритм поиска (Search algorithm)
• Алгоритм поиска по дереву (Tree search algorithm)
• Алгоритм сортировки (Sort algorithm)
• Алгоритмы свободные от зависаний и простоев (Lock-free and wait-free algorithms)
• Аппроксимационный алгоритм (Approximation algorithm)
• Быстрое преобразование Фурье [Fast Fourier transform (FFT)]
• Всплывающий алгоритм (Emergent algorithm)
• Генератор псевдослучайных чисел (Pseudorandom number generator)
• Генетический алгоритм (Genetic algorithm)
• Квантовый алгоритм (Quantum algorithm)
• Комбинаторный поиск (Combinatorial search)
• Конкурентный анализ (Competitive analysis)
• Пуленепробиваемый алгоритм (Bulletproof algorithm)
• Скалолазание (Hill climbing)
• Скалолазание со случайным перезапуском (Random-restart hill climbing)
• Смешанный алгоритм (Randomized algorithm)
• Устойчивый алгоритм (Stable algorithm)
• Эволюционный алгоритм (Evolutionary algorithm)

Информационные технологии и алгоритмы в науке

• Применение алгоритмов в лингвистике.

Алгоритмическое обеспечение (библиотеки)

Общие библиотеки алгоритмов

• Алгоритмы на форуме ProgZ.ru.

Библиотеки математических алгоритмов

• Алгоритмы на форуме ProgZ.ru.
• Библиотека алгоритмов ALGLIB.RU Решение обыкновенных дифференциальных уравнений. Решение интегральных уравнений. Решение полиномиальных уравнений и уравнений общего вида. Решение систем линейных уравнений. Операции с матрицами и векторами. Нахождение собственных значений и векторов. Численное интегрирование. Интерполяция, аппроксимация и численное дифференцирование. Поиск экстремумов функций. Быстрое преобразование Фурье и его приложения. Комбинаторные задачи и величины. Операции с графами. Специальные функции. Операции с комплексными числами. Операции с полиномами. Операции с рядами. Суммирование рядов. Геометрические алгоритмы. Операции с выпуклыми множествами точек. Теория чисел. Решение Диофантовых уравнений. Сортировка. Поиск. Работа с датами. Алгоритмы графики. Генерация псевдослучайных чисел. Криптография. Работа с формулами. Разреженные матрицы.
• Алгоритмы - Библиотека алгоритмов. Пока математическиx.
• Алгоритмы элементарных математических функций.

Полезные алгоритмы для АРМов

Программы преобразования текста

• Алгоритм "Сумма прописью" (Clipper, Pascal, Basic): RTF | Zip.

Алгоритмы обработки строк

• .

Вычисление других функций

• .

Структуры данных

Список структур данных (взято из Википедии):

• Линейные структуры данных (Linear data structures):
  • Список (List):
    • Массив (Array):
      • Битовые поля (Bitmaps):
        • Изображения (Images)
        • Поля высот (Heightfields)
      • Параллельный массив (Parallel array)
      • Дерево отрезков
      • Дерево Фенвика
    • Связанный список (Linked list):
      • Список с пропусками (Skip list)
      • Развёрнутый связанный список (Unrolled linked list)
      • Xor-связанный список (Xor linked list)
    • V-список (VList)
  • Ассоциативный массив (Associative array a.k.a. dictionary or map) — также известен как словарь или карта
  • Хеш-таблица (Hash table)
  • Стек (Stack a.k.a. LIFO Last in, first out) — также известен как ЛИФО
  • Очередь (Queue a.k.a. FIFO First in, first out) — также известен как ФИФО:
    • Приоритетная очередь (Priority queue) — иногда выполняется в виде кучи, см. ниже
  • Дек (Deque) — двусвязная очередь
  • Буферное окно (Buffer gap)
• Граф (Graph):
  • Список рёбер (Adjacency list)
  • Представление графа в разорванном виде (Disjoint-set data structure)
  • Представление графа в виде стеков (Graph-structured stack)
  • Сценограф (Scene graph)
  • Деревья:
    • M-Way Tree
      • B-дерево
    • Двоичное дерево поиска (Binary search tree):
      • Самобалансирующееся дерево поиска (Self-balancing binary search tree):
        • АВЛ-дерево (AVL tree)
        • Красно-чёрное дерево (Red-black tree)
        • Дерево со штрафами (Scapegoat tree)
        • Косое дерево (Splay tree)
        • Дерево ван Емде Боаса (van Emde Boas tree)
      • Дерево остатков (Radix tree)
      • Интервальное дерево (Interval tree)
    • Куча (Heap):
      • Двоичная куча (Binary heap)
      • Биномиальная куча (Binomial heap)
      • Фибоначчиевская куча (Fibonacci heap)
      • 2-3-куча (2-3 heap)
      • Мягкая куча (Soft heap)
    • Дерево разбора (Parse tree)
    • Квад-дерево (Quadtree) и Окт-дерево (Octree)
    • Дерево суффиксов (Suffix tree)
    • Бор Префиксное дерево (Trie):
      • Бор (Patricia trie)
• Другие структуры данных:
  • Помеченное объединение (Tagged union)
  • Объединение (Union)
  • Таблица (Table)

Литература по алгоритмам

"Если вы считаете себя действительно хорошим программистом, прочтите книгу "Искусство программирования" Д.Кнутa... Вам определенно следует прислать мне резюме, если Вы прочли эту книгу до конца" (Билл Гейтс)

Дональд Е. Кнут - автор всемирно известной серии книг, посвященной основным алгоритмам и методам вычислительной математики, создатель настольных издательских систем TEX и METAFONT, предназначенных для верстки физико-математических книг. Его перу принадлежит 19 книг и более 160 статей. Дональд Кнут является почетным профессором Стэндфордского университета в области программирования и вычислительной математики. В настоящее время он полностью занят написанием новых книг серии "Искусство программирования". Работу над первым томом он начал еще в 1962 году, сразу после окончания Калифорнийского технологического института (California Institute of Technology). Профессор Кнут удостоен многочисленных премий и наград, среди которых можно отметить ACM Turing Award, Medal of Science президента Картера, AMS Steele Prize за серию научно-популярных статей. В ноябре 1996 года Дональд Кнут был удостоен престижной награды Kyoto Prize в области передовых технологий.

• "Кнут Дональд Э. - Искусство программирования. Том 1. Основные алгоритмы. Том 2. Получисленные алгоритмы. Том 3. Сортировка и поиск. [На Необуке]
• Искусство программирования - 3 изд.. Том 1. Основные алгоритмы. Кнут Д.. Изд-во Вильямс, 2007. 720 с.
  Первый том серии книг "Искусство программирования" начинается с описания основных понятий и методов программирования. Затем автор сосредоточивается на рассмотрении информационных структур — представлении информации внутри компьютера, структурных связях между элементами данных и способах эффективной работы с ними. Для методов имитации, символьных вычислений, числовых методов и методов разработки программного обеспечения даны примеры элементарных приложений. По сравнению с предыдущим изданием добавлены десятки простых, но в то же время очень важных алгоритмов. В соответствии с современными направлениями исследований был существенно переработан также раздел математического введения.
  Заказать на Библионе,
• Э. Йодан. Структурное проектирование и конструирование программ. - М.: Мир, 1977.

© «Сайт Игоря Гаршина», 2002. Пишите письма ().