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

Алгоритмы, структуры данных и вычислительные методы

Алгоритм, алгорифм (от 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)

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

• Алгоритмы - Библиотека алгоритмов. Пока математическиx.
• Алгоритмы на форуме ProgZ.ru.
• Алгоритмы элементарных математических функций.

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

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

• Линейные структуры данных (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)

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

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

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

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

• .

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

• .

Литература по алгоритмам и численным методам

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

"Если вы считаете себя действительно хорошим программистом, прочтите книгу "Искусство программирования" Д.Кнут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.

Литература по вычислительным методам

• Л. И. Турчак. Основы численных методов. - М.: Yferf? 1987.
• Д. Мак Крокен, Ч. Дорн. Численные методы и программирование на ФОРТРАНЕ. - М.: Мир, 1977.
• Численные методы. Учебник для техникумов. М., "Высшая школа", 1976.
• А. С. Шалыгин, Ю. И. Палагин. Прикладные методы статистического моделирования. - Л.: Машиностроение, 1986.
• С. Т. Хвощ, Н. Н. Варлинский, Е. А. Попов. Микропроцессоры и микроЭВМ в системах автоматического управления. Справочник. - Л.: Машиностроение, 1987.

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

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

Введите условия поиска Отправить форму поиска   Web Википедия Garshin.ru

Ключевые слова для поиска сведений по алгоритмам: На русском языке: алгоритм, структуры данных, алгоритмическое обеспечение человеческой деятельности, алгоритмизация исследований, статистические расчёты и подсчеты, вычислительные методы и функции, алгоритмы элементарных математических функций, коды, пользовательские функции, элементарные процедуры, перевод числа в пропись, копилка полезных строковых функций, описание алгоритмов с помощью языков программирования Visual Basic, VC++, MS VBA; На английском языке: algorythms.

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