Связанные понятия
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причём кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
Тетрамино ́ — геометрические фигуры, состоящие из четырёх квадратов, соединённых сторонами (от греч. τετρα- — четыре), то есть так, что квадраты можно обойти за конечное число ходов шахматной ладьи. Тетрамино являются подмножеством полимино.
Пентамино ́ (от др.-греч. πέντα пять, и домино) — пятиклеточные полимино, то есть плоские фигуры, каждая из которых состоит из пяти одинаковых квадратов, соединённых между собой сторонами («ходом ладьи»). Этим же словом иногда называют головоломку, в которой такие фигуры требуется укладывать в прямоугольник или другие формы.
Математическая головоломка — задача занимательной математики с игровыми элементами (правилами возможных действий, иногда — сюжетом), требующая в большей степени сообразительности, нежели математической подготовки или специальных знаний.
В геометрии
домино замощение области в евклидовой плоскости — это мозаика области плитками домино, образованными объединением двух единичных квадратов, соединённых по ребру. Эквивалентно это паросочетание в графе решётки, образованное помещением вершины в центр каждого квадрата области и соединением двух вершин, если два соответствующих квадрата смежны.
Конструктивная блочная геометрия, КБГ (англ. Constructive Solid Geometry, CSG) — технология, используемая в моделировании твёрдых тел. Конструктивная блочная геометрия зачастую, но не всегда, является способом моделирования в трёхмерной графике и САПР. Она позволяет создать сложную сцену или объект с помощью битовых операций для комбинирования нескольких иных объектов. Это позволяет более просто математически описать сложные объекты, хотя не всегда операции проходят с использованием только простых...
Двоичное разбиение пространства (англ. binary space partitioning) — метод рекурсивного разбиения евклидова пространства в выпуклые множества и гиперплоскости. В результате объекты получают представление в виде структуры данных, называемой BSP-деревом.
Метод тонирования Гуро ́ — метод закрашивания в трёхмерной компьютерной графике (затенения), предназначенный для создания иллюзии гладкой криволинейной поверхности, описанной в виде полигональной сетки с плоскими гранями, путём интерполяции цветов примыкающих граней. Метод впервые предложен Анри Гуро в 1971 году.
В геометрии подстановки плиток — это метод построения мозаик. Наиболее важно, что некоторые подстановки плиток образуют апериодические мозаики, то есть замощения, протоплитки которых не образуют какую-либо мозаику с параллельным переносом. Наиболее известные из них — мозаики Пенроуза. Подстановочные мозаики являются специальными случаями правил конечного подразделения, когда не требуется геометрическое равенство плиток.
Обнаружение столкновений (англ. Collision detection) — вычислительная проблема обнаружения пересечений между собой двух или больше объектов. Тема чаще всего связана с её использованием в физических движках, компьютерной анимации и робототехнике. В дополнение к определению, столкнулись ли два объекта, системы обнаружения столкновений могут вычислить время воздействия и сообщить о коллекторе контакта (набор пересечения точек). Ответ на столкновение (что происходит, когда столкновение обнаружено) зависит...
Октамино — восьмиклеточные полимино, то есть плоские фигуры, состоящие из восьми равных квадратов, соединённых сторонами. С фигурами октамино, как со всеми полимино, связано много задач занимательной математики.
Судо́ку (яп. 数独 су:доку, произношение ) — головоломка с числами. Иногда судоку называют магическим квадратом, что в общем-то неверно, так как судоку является латинским квадратом 9-го порядка. Судоку активно публикуют газеты и журналы разных стран мира, сборники судоку издаются большими тиражами. Решение судоку — популярный вид досуга.
Скьюб (англ. Skewb) — механическая головоломка в стиле кубика Рубика, состоящая из частей, которые вращаются и меняют своё положение. Название происходит от английских слов skew (искривлен) и cube (куб). Скьюб был изобретен английским журналистом Тони Дарема, и первоначально имел название «Кубик-пирамидка» (англ. Cube Pyraminx). Дуглас Хофстадтер придумал слово «Skewb», которое было употреблено впервые в статье журнала Scientific American в июле 1982 года.
Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором каждая область этого разбиения образует множество точек, более близких к одному из элементов множества S, чем к любому другому элементу множества.
Полимино , или полиомино (англ. polyomino) — плоские геометрические фигуры, образованные путём соединения нескольких одноклеточных квадратов по их сторонам. Это полиформы, сегменты которых являются квадратами.
В математике конечное правило подразделения — это рекурсивный способ деления многоугольника и других двумерных фигур на всё меньшие и меньшие части. Правила подразделения в этом смысле является обобщением фракталов. Вместо повторения одного и того же узора снова и снова здесь имеются небольшие изменения на каждом шаге, что позволяет получить более богатые структуры, сохраняя при этом поддержку элегантного стиля фракталов . Правила подразделения используются в архитектуре, биологии и информатике...
Черепа́шья гра́фика — принцип организации библиотеки графического вывода, построенный на метафоре Черепахи, воображаемого (а в некоторых экспериментах и реального) роботоподобного устройства, которое перемещается по экрану или бумаге и поворачивается в заданных направлениях, при этом оставляя (или, по выбору, не оставляя) за собой нарисованный след заданного цвета и ширины.
Солитер — это настольная игра для одного игрока, в которой переставляются колышки на доске с отверстиями. Некоторые комплекты используют шарики и доски с выемками. В США игра имеет название Peg Solitaire (колышковый солитер), а название Солитер относится к пасьянсу. В Великобритании игра известна под именем Solitaire (солитер), а карточная игра называется Patience (пасьянс). В некоторых местах, в частности, в Индии, игра носит название Brainvita.
Гексамино — шестиклеточное полимино, то есть плоская фигура, состоящая из шести равных квадратов, соединённых сторонами. С фигурами гексамино, как со всеми полимино, связано много задач занимательной математики.
Плитки Вана (или домино Вана), впервые предложенные математиком, логиком и философом Хао Ваном в 1961, — это класс формальных систем. Они моделируются визуально с помощью квадратных плиток с раскрашиванием каждой стороны. Определяется набор таких плиток (например, как на иллюстрации), затем копии этих плиток прикладываются друг к другу с условием согласования цветов сторон, но без вращения или симметрического отражения плиток.
Трёхме́рное простра́нство — геометрическая модель материального мира, в котором мы находимся. Это пространство называется трёхмерным, так как оно имеет три однородных измерения — длину, ширину и высоту, то есть трёхмерное пространство описывается тремя единичными ортогональными векторами.
Полиамонд (англ. polyiamond) или треуго́льный мо́нстр (англ. triangular animal) — геометрическая фигура в виде многоугольника, составленного из нескольких одинаковых равносторонних треугольников, примыкающих друг к другу по рёбрам. Полиамонды можно рассматривать как конечные подмножества треугольного паркета со связной внутренностью.
Многоугольник видимости или область видимости для точки p на плоскости среди препятствий — это (возможно неограниченная) многоугольная область всех точек плоскости, видимых из точки p. Многоугольник видимости можно определить для видимости из отрезка или многоугольника. Многоугольники видимости полезны в робототехнике, компьютерных играх и для определения позиций объектов, например, для определеиня наилучшего расположения охраны в картинных галереях.
Алгоритм Грэхема — алгоритм построения выпуклой оболочки в двумерном пространстве.
Полигональная сетка (жарг. меш от англ. polygon mesh) — это совокупность вершин, рёбер и граней, которые определяют форму многогранного объекта в трёхмерной компьютерной графике и объёмном моделировании. Гранями обычно являются треугольники, четырёхугольники или другие простые выпуклые многоугольники (полигоны), так как это упрощает рендеринг, но сетки могут также состоять и из наиболее общих вогнутых многоугольников, или многоугольников с отверстиями.
Набор плиток с самозамощением (англ. setiset) порядка n — это набор из n фигур, обычно плоских, каждая из которых допускает замощение меньшими копиями тех же n фигур. Более точно, n фигур могут быть собраны n различными способами, дающими большие копии фигур из того же набора, и коэффициент увеличения один и тот же. Рисунок 1 показывает пример для n = 4 с использованием декамино различной формы. Концепцию можно обобщить и использовать фигуры большей размерности. Название setisets дал Ли Сэллоус (англ...
В геометрии 4-мерный многогранник — это многогранник в четырёхмерном пространстве. Многогранник является связанной замкнутой фигурой, состоящей из многогранных элементов меньшей размерности — вершин, рёбер, граней (многоугольников) и ячеек (3-мерных многогранников). Каждая грань принадлежит ровно двум ячейкам.
Пла́нер , или гла́йдер (англ. glider) — пятиклеточная конфигурация «Жизни», способная перемещаться в двумерной вселенной с квадратными ячейками.
Блочный клеточный автомат — класс клеточных автоматов, в которых решётка разбита на блоки, а функция перехода применяется к каждому блоку по отдельности. Блочные клеточные автоматы полезны для моделирования физических явлений, поскольку часто несложно выбрать функции перехода так, чтобы получившийся клеточный автомат был обратим и подчинялся выбранным законам сохранения.
Пра́вильный двадцатичетырёхъяче́йник, или просто двадцатичетырёхъяче́йник, или икоситетрахор (от др.-греч. εἴκοσι — «двадцать», τέτταρες — «четыре» и χώρος — «место, пространство»), — один из правильных многоячейников в четырёхмерном пространстве.
Подробнее: Двадцатичетырёхъячейник
Флексагон ы (от англ. to flex, лат. flectere — складываться, сгибаться, гнуться и греч. ωνος — угольник) — плоские модели из полосок бумаги, способные складываться и сгибаться определённым образом. При складывании флексагона становятся видны поверхности, которые ранее были скрыты в конструкции флексагона, а прежде видимые поверхности уходят внутрь.
Шесть степеней свободы (часто употребляется аббревиатура 6DoF, от англ. Six degrees of freedom) — указывает на возможность геометрической фигуры совершать геометрические движения в (трёхмерном) пространстве, а именно: двигаться вперёд/назад, вверх/вниз, влево/вправо (в декартовой трёхмерной системе координат), включая повороты углов Эйлера вокруг каждой из трёх взаимно перпендикулярных осей (рыскание, тангаж, крен).
Задачи упаковки — это класс задач оптимизации в математике, в которых пытаются упаковать объекты в контейнеры. Цель упаковки — либо упаковать отдельный контейнер как можно плотнее, либо упаковать все объекты, использовав как можно меньше контейнеров. Многие из таких задач могут относиться к упаковке предметов в реальной жизни, вопросам складирования и транспортировки. Каждая задача упаковки имеет двойственную задачу о покрытии, в которой спрашивается, как много требуется некоторых предметов, чтобы...
Плотность упаковки в некотором пространстве — это доля пространства, заполненная упакованными телами (фигурами). В задачах упаковки обычно целью является получение упаковки с максимальной возможной плотностью.
Гептамино — семиклеточное полимино, то есть плоская фигура, состоящая из семи равных квадратов, соединённых сторонами. С фигурами гептамино, как со всеми полимино, связано много задач занимательной математики.
Прямолинейный скелет — это метод представления многоугольника его топологическим скелетом. Прямолинейный скелет подобен в некотором роде срединным осям, но отличается тем, что скелет состоит из отрезков, в то время как срединные оси многоугольника могут включать параболические кривые.
Элементарный клеточный автомат — это клеточный автомат с одномерным массивом ячеек в форме бесконечной в обе стороны ленты, который имеет два возможных состояния ячеек (0 и 1, «мёртвые» и «живые», «пустые» и «заполненные») и правило для определения состояния ячейки на следующем шаге, использующее только состояние ячейки и её двух соседей на текущем шаге. В целом такие автоматы являются одними из наиболее простых возможных клеточных автоматов, однако при некоторых правилах они показывают сложное поведение...
Аксонометри́ческая прое́кция (от др.-греч. ἄξων «ось» + μετρέω «измеряю») — способ изображения геометрических предметов на чертеже при помощи параллельных проекций.
Пифагорова мозаика (замощение двумя квадратами) — замощение евклидовой плоскости квадратами двух различных размеров, в которой каждый квадрат касается четырёх квадратов другого размера своими четырьмя сторонами. Исходя из этой мозаики, можно доказать (наглядно) теорему Пифагора, за что мозаика и получила название пифагоровой. Мозаика часто используется в качестве узора для кафельного пола. В этом контексте мозаика известна также как узор классов.
Итерация в программировании — в широком смысле — организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя (в отличие от рекурсии). В узком смысле — один шаг итерационного, циклического процесса.
Пасьянс маджонг — настольная игра для одного человека, по структуре и игровому процессу похожа на карточный пасьянс, играется с помощью набора фишек азиатской азартной игры маджонг. Следует отличать пасьянс маджонг от азартной игры маджонг, набор фишек которой используется в данной игре — в компьютерных играх чаще всего реализуется именно пасьянс маджонг, а не азартная игра. Более того, некоторые реализации используют изображения случайных предметов вместо костей маджонга, а от собственно маджонга...
В геометрии правильный косой многогранник — это обобщение множества правильных многогранников, которое включает возможность непланарных граней или вершинных фигур. Коксетер рассматривал косые вершинные фигуры, которые создавали новые четырёхмерные правильные многогранники, а много позднее Бранко Грюнбаум рассматривал правильные косые грани.
Конфигурация прямых (или разбиение плоскости прямыми) — это разбиение плоскости, образованное набором прямых.
Бесконечная группа — группа с бесконечным числом элементов, в противоположность конечным группам.
В математике константой
Чигера (также числом Чигера или изопериметрическим числом) графа называется числовая характеристика графа, отражающая, есть ли у графа «узкое место» или нет. Константа Чигера как способ измерения наличия «узкого места» представляет интерес во многих областях, например, для создания сильно связанных компьютерных сетей, для тасования карт и в топологии малых размерностей (в частности, при изучении гиперболических 3-мерных многообразий). Названа в честь математика Джефа Чигера...
Обратимый клеточный автомат — клеточный автомат, в котором каждое состояние имеет единственного предшественника. Таким образом, это регулярная решётка из ячеек, состояние каждой из которых берётся из конечного множества состояний, и правило для одновременного обновления состояний ячеек, исходя из состояний её соседей. Условие обратимости заключается в том, что предыдущее состояние любой ячейки может быть определено, зная обновлённые состояния всех ячеек решётки. После обращения времени получается...
Октодерево (дерево октантов, восьмеричное дерево, англ. octree) — тип древовидной структуры данных, в которой у каждого внутреннего узла ровно восемь «потомков». Восьмеричные деревья чаще всего используются для разделения трёхмерного пространства, рекурсивно разделяя его на восемь ячеек. Октодеревья являются трёхмерными аналогами квадродеревьев. Англоязычное название «octree» сформировано из oct + tree и обычно пишется как «octree», а не «octtree».