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

Трансильванский университет Sapientia представил свой новый обучающий курс по алгоритмам сортировки. Стоит отметить талант создателей и высокую наглядность пособия.

1. Сортировка пузырьком как венгерский народный танец

Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: $O(n^2)$ .

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

Исполняется танец народа Чангоши (венг. csángók, также чанго от венг. Csángó)

2. Сортировка слиянием как немецкий народный танец

Сортировка слиянием (англ. merge sort) — алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например — потоки) в определённом порядке. Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Время работы алгоритма порядка $O(n\log n)$ при отсутствии деградации на неудачных случаях, которая является больным местом быстрой сортировки (тоже алгоритм порядка $O(n\log n)$ , но только для среднего случая).

Исполняется трансильвано-саксонский (немецкий) народный танец.

3. Сортировка выбором как цыганский народный танец

Сортировка выбором (Selection sort) — алгоритм сортировки. Может быть как устойчивый, так и неустойчивый. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае $O(n^2)$ , предполагая что сравнения делаются за постоянное время.

4. Быстрая сортировка как венгерский народный танец

Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году. Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем $O(n\log n)$ обменов при упорядочении $n$ элементов.

Исполняется танец legényes (в Венгрии) или feciorească (в Румынии)

5. Сортировка Шелла как венгерский народный танец

Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Дональда Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга; иными словами — это сортировка вставками, но с предварительными «грубыми» проходами. Аналогичный метод усовершенствования «пузырьковой» сортировки называется «сортировка расчёской».

Исполняется танец венгерской народности Székelys.

6. Сортировка вставками как румынский народный танец

Сортировка вставками (англ. Insertion sort) — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов. Вычислительная сложность $O(n^2)$ .

7. Сортировка кучей как венгерский народный танец

Сортировка кучей (англ. Heapsort) — алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за $O(n \log n)$ операций при сортировке $n$ элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, $O(1)$ ). Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям. Пирамидальная сортировка была предложена Дж. Уильямсом в 1964 году.

Исполняется венгерский народный танец Mezőségi.

Создано в Sapientia University, Tirgu Mures (Marosvásárhely), Romania.
Режиссеры: Kátai Zoltán and Tóth László.
Хореограф: Füzesi Albert.

Комментарии: 0

Похожее

Развитие искусственного интеллекта в шахматных программах

История развития автоматики и вычислительной техники странным образом связана с шахматами. В XVIII в. "думающие" шахматные автоматы служили для фокусов и мистификаций. Первый аппарат с настоящим искусственным интеллектом, созданный в Испании в начале ХХ в., был способен поставить мат королем и ладьей шахматисту, играющему королем. Видимо, не случайно и то, что одной из первых действительно интеллектуальных задач, поставленных перед программистами еще на заре вычислительной техники, была игра в шахматы. О шахматных программах и связи этой древней игры с развитием технологий искусственного интеллекта мы попросили рассказать одного из тех, кто создавал первые шахматные программы, доктора технических наук, профессора Владимира Львовича Арлазарова.
Алгоритмы шахматных программ

Владимир Арлазаров

Минимакс, Альфа-бета, Применение теории к практике, Улучшения, Современные шахматные программы, История Deep Blue, Как устроена Deep Blue.
Эволюционные алгоритмы

Джозеф Браун

На чем основаны генетические алгоритмы? Как происходит создание различных уровней в компьютерной игре? Каковы перспективы применения эволюционных алгоритмов? На эти и другие вопросы отвечает доцент Университета Иннополис Джозеф Браун. Процедурная генерация контента в играх — это процесс автоматического создания различных ресурсов. Таким образом можно создавать повествование или сюжет игры или более простые объекты, такие как деревья. Или какие-нибудь элементы игрового процесса. Например, какие будут уровни. Этим я в основном и занимаюсь: как создать уровень, который отвечает некоторым ожиданиям игрока и некоторым ожиданиям в контексте повествования. Я использую много приемов из области, которая называется вычислительный интеллект. А вычислительный интеллект применяет биоинспирированные методы для решения сложных задач оптимизации.
Эволюционные алгоритмы

Мультфильм рассказывает об использовании идеи биологической эволюции в задачах искусственного интеллекта, истории эволюционных алгоритмов и принципах их работы. Все это подробно изучается на магистерской программе Университета Иннополис «Робототехника». Историю об эволюционных алгоритмах нам помог рассказать доцент, руководитель Лаборатории искусственного интеллекта в разработке игр Университета Иннополис Джозеф Браун.
Ученые просчитали оптимальную стратегию игры в покер

Объявлено об успешном завершении работы компьютерной программы, просчитывавшей одну из версий покера — хедз-ап в лимитном техасском холдеме. Программа научилась принимать правильное решение в каждом из примерно 3,19×10^14 возможных состояний игры. Найденная таким образом стратегия на длинной дистанции должна обыгрывать остальные стратегии.
Насколько программисту нужно знание математики?

«Типичный программист» в рубрике «Вопросы к экспертам» затронул извечный вопрос про программирование и математику. Итак, действительно ли программисту нужно знание математики для успешной работы и если нужно, то насколько?
История развития компьютерных шахмат

Математики оценивают количество различных шахматных партий величиной 10 в 120 степени – так называемое Число Шеннона (для сравнения – число атомов в изученной части вселенной — 10^80). Число различных позиций, возникающих на шахматной доске во время игры, несомненно, меньше, ведь в разных партиях могут возникать одинаковые позиции. Рассчитанное число позиций в шахматах около 10^43, включая некоторые невозможные позиции. Условно, с учетом легальности позиций, можно считать их количество приблизительно равным 10^40.
Как компьютер научили играть в го

Антон Трушечкин

Март 2016 года ознаменовался сенсацией в области информатики и искусственного разума: программа AlphaGo, разработанная компанией Google DeepMind, выиграла со счётом 4:1 матч в го у одного из сильнейших гоистов мира Ли Седоля. До этого игра го считалась недоступной для компьютера, ввиду того что большую роль в ней играют не только расчёт, но и такие сложно формализуемые понятия, как интуиция, чувство гармонии и т.п. Как же удалось научить машину «чувствовать гармонию», преодолеть ограничения классических методов машинного анализа игр? В докладе будут рассмотрены как классические методы (минимакс, альфа-бета-отсечение), которые показали свою эффективность в шахматах и шашках, так и методы, воплощённые в программе AlphaGo: поиск на дереве методом Монте-Карло, свёрточные нейронные сети для распознавания изображений, обучение с подкреплением.
Об истории криптографии и надежности ваших паролей

Со времен возникновения письменности и до середины XX века криптография была искусством. Сейчас это не только проработанная область науки на стыке математики и информатики, но и то, чем мы пользуемся ежедневно. К чему может привести незнание криптографии и любовь к халяве, как прочитать вашу переписку, почему шифрование на открытых ключах безопаснее и что значит cLhmGccA4aSaRslIsnA, рассказывает кандидат физико-математических наук, лектор по защите информации в МФТИ Сергей Владимиров.
Деньги, карты и защита информации

Елена Белоусова

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

Далее >>>

∀ x, y, z

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

Теги

Похожее