Связанные понятия
Гептамино — семиклеточное полимино, то есть плоская фигура, состоящая из семи равных квадратов, соединённых сторонами. С фигурами гептамино, как со всеми полимино, связано много задач занимательной математики.
Октамино — восьмиклеточные полимино, то есть плоские фигуры, состоящие из восьми равных квадратов, соединённых сторонами. С фигурами октамино, как со всеми полимино, связано много задач занимательной математики.
Диаграмма Насси — Шнейдермана (англ. Nassi — Shneiderman diagram) — это графический способ представления структурированных алгоритмов и программ, разработанный в 1972 году американскими аспирантами Беном Шнейдерманом и Айзеком Насси.
Исчезновение клетки (появление клетки) — известный класс задач (оптических иллюзий) на перестановку фигур, обладающих признаками софизмов: изначально в их условие введена замаскированная ошибка. Некоторые из этих задач тесно связаны со свойствами последовательности чисел Фибоначчи.
Алгоритм Грэхема — алгоритм построения выпуклой оболочки в двумерном пространстве.
«Перебрось мостик », бридж-ит, «трубопровод», «птичья клетка», переключательная игра Шеннона или игра Гейла — абстрактная игра типа гекса для двух игроков. Игра придумана в середине XX века независимо Дэвидом Гейлом и Клодом Шенноном. В 1958 году Мартин Гарднер показал игру широкой публике в своей колонке в Scientific American. Хотя в бридж-ит можно играть и на бумаге, американские производители игрушек делали игральные комплекты.
Куб принца Руперта (англ. Prince Rupert’s cube) — самый большой куб, который может пройти через отверстие, вырезанное в единичном кубе (то есть через куб, рёбра которого имеют размер 1). Ребро куба Руперта приблизительно на 6 % длиннее, чем ребро куба, через который он проходит. Задача поиска такого куба тесно связана с задачей поиска самого большего квадрата, который полностью расположен в пределах единичного куба, и имеет аналогичное решение.
Итеративное сжатие — это алгоритмическая техника разработки фиксированно-параметрически разрешимых алгоритмов, в которой один элемент (такой как вершина графа) добавляется в задачу на каждом шаге и используется небольшое решение задачи перед добавлением элемента, чтобы найти небольшое решение задачи после добавления.
В математике деление на два, деление пополам — это математическая операция, частный случай деления. Древние египтяне отличали деление на два от деления на другие числа, поскольку их алгоритм умножения использовал деление на два как один из промежуточных этапов. В XVI веке некоторые математики предложили рассматривать деление на два как операцию, отличающуюся от деления на другие числа. В современном программировании также иногда выделяют деление именно на два.
Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем...
Матрица жёсткости (матрица Дирихле) — матрица особого вида, использующаяся в методе конечных элементов для решения дифференциальных уравнений в частных производных. Она применяется при решениях задач электродинамики и механики.
Набор плиток с самозамощением (англ. setiset) порядка n — это набор из n фигур, обычно плоских, каждая из которых допускает замощение меньшими копиями тех же n фигур. Более точно, n фигур могут быть собраны n различными способами, дающими большие копии фигур из того же набора, и коэффициент увеличения один и тот же. Рисунок 1 показывает пример для n = 4 с использованием декамино различной формы. Концепцию можно обобщить и использовать фигуры большей размерности. Название setisets дал Ли Сэллоус (англ...
Многоугольник видимости или область видимости для точки p на плоскости среди препятствий — это (возможно неограниченная) многоугольная область всех точек плоскости, видимых из точки p. Многоугольник видимости можно определить для видимости из отрезка или многоугольника. Многоугольники видимости полезны в робототехнике, компьютерных играх и для определения позиций объектов, например, для определеиня наилучшего расположения охраны в картинных галереях.
Два-граф ы не являются графами, и их не следует путать с другими объектами, которые называются 2-графами в теории графов, в частности, с 2-регулярными графами. Для их различения используется слово «два», а не цифра «2».
Геометрическая криптография — теоретические криптографические методы, в которых сообщения и шифротексты представлены в виде геометрических величин: углов, отрезков, а вычисления проводятся с помощью циркуля и линейки. Основана на сложности решения определенного класса геометрических задач, например, трисекции угла.
Метод шаров и перегородок (англ. stars and bars — букв. «звёздочки и чёрточки») — это графический метод для вывода некоторых комбинаторных теорем. Метод популяризировал Уильям Феллер в его классической книге по теории вероятностей. Метод может быть использован для решения многих простых задач подсчёта, таких как «сколькими способами можно разложить n неразличимых шаров по k различимым ящикам».
Свёртка последовательностей — это результат перемножения элементов двух заданных числовых последовательностей таким образом, что члены одной последовательности берутся с возрастанием индексов, а члены другой — с убыванием (что и служит основанием для принятого названия данной операции).
В математике конечное правило подразделения — это рекурсивный способ деления многоугольника и других двумерных фигур на всё меньшие и меньшие части. Правила подразделения в этом смысле является обобщением фракталов. Вместо повторения одного и того же узора снова и снова здесь имеются небольшие изменения на каждом шаге, что позволяет получить более богатые структуры, сохраняя при этом поддержку элегантного стиля фракталов . Правила подразделения используются в архитектуре, биологии и информатике...
Гомеоско́п (от др.-греч. ὅμοιος «подобный» + σκοπέω «смотреть») — это одна из пяти так называемых «интеллектуальных машин» С. Н. Корсакова — классифицирующее логическое устройство, которое было предложено в 1832 году для автоматизации сравнения идей (понятий).
Двоичный алгоритм поиска подстроки (также bitap algorithm, shift-or algorithm) — алгоритм поиска подстроки, использующий тот факт, что в современных компьютерах битовый сдвиг и побитовое ИЛИ являются атомарными операциями. По сути, это примитивный алгоритм поиска с небольшой оптимизацией, благодаря которой за одну операцию производится до 32 сравнений одновременно (или до 64, в зависимости от разрядности машины). Легко переделывается на приблизительный поиск.
В вычислительной геометрии известна задача об определении принадлежности точки многоугольнику. На плоскости даны многоугольник и точка. Требуется решить вопрос о принадлежности точки многоугольнику.
Подробнее: Задача о принадлежности точки многоугольнику
Задачи упаковки — это класс задач оптимизации в математике, в которых пытаются упаковать объекты в контейнеры. Цель упаковки — либо упаковать отдельный контейнер как можно плотнее, либо упаковать все объекты, использовав как можно меньше контейнеров. Многие из таких задач могут относиться к упаковке предметов в реальной жизни, вопросам складирования и транспортировки. Каждая задача упаковки имеет двойственную задачу о покрытии, в которой спрашивается, как много требуется некоторых предметов, чтобы...
«Абалон » (фр. Abalone) — настольная абстрактная стратегическая игра для двух игроков, придуманная французскими дизайнерами игр Мишелем Лале (Michel Lalet) и Лораном Леви (Laurent Lévi) в 1987 году под названием «Сумито». В игре используются шарики разных цветов (по 14 шаров каждого цвета) и шестиугольное игровое поле, содержащее 61 пункт. Целью игры является выталкивание шести шаров соперника за пределы поля. Существуют варианты правил для трёх-шести игроков.
Алгоритм Брезенхе́ма (англ. Bresenham's line algorithm) — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Элтоном Брезенхэмом (англ. Jack Elton Bresenham) в компании IBM в 1962 году. Алгоритм широко используется, в частности, для рисования линий на экране компьютера. Существует обобщение алгоритма Брезенхэма для построения...
Ошибка на единицу или ошибка неучтённой единицы (англ. off-by-one error) — логическая ошибка в алгоритме, включающая в частности дискретный вариант нарушения граничных условий.
Задача о змее в коробке в теории графов и информатике имеет дело с поиском определённого вида пути вдоль рёбер гиперкуба. Этот путь начинается с одного угла и проходит вдоль рёбер столько углов, сколько он может достичь. После того как достигается новый угол, предыдущий угол и все его соседи делаются недопустимыми для использования. Путь никогда не должен проходить через угол после того, как он помечен как недопустимый.
Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём...
Рациональное решето — это алгоритм общего вида для разложения целых чисел на простые множители. Алгоритм является частным случаем общего метода решета числового поля. Хотя он менее эффективен, чем общий алгоритм, концептуально он проще. Алгоритм может помочь понять, как работает общий метод решета числового поля.
Далдос (дат. daldøs) — старинная настольная игра из Дании. В Норвегии эта игра с небольшими отличиями известна под названием daldøsa.
Заполняющие пространство деревья — это геометрические построения, аналогичные кривым Пеано, но имеет ветвящуюся подобно дереву структуру и корень. Заполняющее пространство дерево определяется пошаговым процессом, который даёт дерево, в котором любая точка пространства имеет конечной длины путь, который сходится к данной точке. В отличие от заполняющих пространство кривых, каждый путь в дереве короток, что позволяет любую часть пространства достичь из корня...
Задача о наименьшей окружности или задача о минимальном покрывающем круге — задача о вычислении наименьшей окружности, содержащей все заданные точки из множества на евклидовой плоскости.
Гамма-алгоритм — это алгоритм плоской укладки графа и попутной проверки его на планарность.
Статья описывает упаковку
кругов на поверхностях. Для связанной статьи об упаковке кругов с заданным графом пересечений, см. статью «Теорема об упаковке кругов».
Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была введена и доказана.
Инверсия кривой — результат применения операции инверсии к заданной кривой C. По отношению к фиксированной окружности с центром O и радиусом k инверсия точки Q — это точка P, лежащая на луче OQ, и OP•OQ = k2. Инверсия кривой C — это множество всех точек P, являющихся инверсиями точек Q, принадлежащих кривой C. Точка O в этом построении называется центром инверсии, окружность называется окружностью инверсии, а k — радиусом инверсии.
Разбиение многоугольника — это множество примитивных элементов (например, квадратов), которые не накладываются и объединение которых равно многоугольнику. Задача о разбиении многоугольника — это задача поиска разбиения, которое в некотором смысле минимально, например, разбиение с наименьшим числом элементов или разбиение с наименьшей суммой длин сторон.
Флексагон ы (от англ. to flex, лат. flectere — складываться, сгибаться, гнуться и греч. ωνος — угольник) — плоские модели из полосок бумаги, способные складываться и сгибаться определённым образом. При складывании флексагона становятся видны поверхности, которые ранее были скрыты в конструкции флексагона, а прежде видимые поверхности уходят внутрь.
Пентамино ́ (от др.-греч. πέντα пять, и домино) — пятиклеточные полимино, то есть плоские фигуры, каждая из которых состоит из пяти одинаковых квадратов, соединённых между собой сторонами («ходом ладьи»). Этим же словом иногда называют головоломку, в которой такие фигуры требуется укладывать в прямоугольник или другие формы.
Куб Фибоначчи можно определить в терминах кодов Фибоначчи и расстояния Хэмминга, независимых множеств вершин в путях, или через дистрибутивные решётки.
Ханойская башня является одной из популярных головоломок XIX века. Даны три стержня, на один из которых нанизаны восемь колец, причём кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.
Компьютер для операций с математическими функциями (в отличие от обычного компьютера) оперирует с функциями на аппаратном уровне (то есть без программирования этих операций).
Окружности Мальфатти — три окружности внутри заданного треугольника, такие, что каждая окружность касается двух других и двух сторон треугольника. Окружности названы именем Джанфранческо Мальфатти, который начал исследовать задачу построения этих окружностей с ошибочным убеждением, что они в сумме дают максимальную возможную площадь трёх непересекающихся окружностей внутри треугольника. Задача Мальфатти относится к обеим задачам — как к построению окружностей Мальфатти, так и к задаче нахождения...
Скьюб (англ. Skewb) — механическая головоломка в стиле кубика Рубика, состоящая из частей, которые вращаются и меняют своё положение. Название происходит от английских слов skew (искривлен) и cube (куб). Скьюб был изобретен английским журналистом Тони Дарема, и первоначально имел название «Кубик-пирамидка» (англ. Cube Pyraminx). Дуглас Хофстадтер придумал слово «Skewb», которое было употреблено впервые в статье журнала Scientific American в июле 1982 года.
Алгоритм Гельфонда — Шенкса (англ. Baby-step giant-step; также называемый алгоритмом больших и малых шагов) — в теории групп детерминированный алгоритм дискретного логарифмирования в мульпликативной группе кольца вычетов по модулю простого числа. Был предложен советским математиком Александром Гельфондом в 1962 году и Дэниэлем Шенксом в 1972 году.