Теория чисел или высшая арифметика — раздел математики, первоначально изучавший свойства целых чисел. В современной теории чисел рассматриваются и другие типы чисел — например, алгебраические и трансцендентные, а также функции различного происхождения, которые связаны с арифметикой целых чисел и их обобщений.
Квадрату́ра кру́га — задача, заключающаяся в нахождении способа построения с помощью циркуля и линейки квадрата, равновеликого по площади данному кругу. Наряду с трисекцией угла и удвоением куба, является одной из самых известных неразрешимых задач на построение с помощью циркуля и линейки.
Тео́рия ха́оса — математический аппарат, описывающий поведение некоторых нелинейных динамических систем, подверженных, при определённых условиях, явлению, известному как хаос. Поведение такой системы кажется случайным, даже если модель, описывающая систему, является детерминированной. Для акцентирования особого характера изучаемого в рамках этой теории явления обычно принято использовать название теория динамического хаоса.
Проблема остановки — одна из проблем в теории алгоритмов, которая может неформально быть поставлена в виде:
- Даны описание процедуры и её начальные входные данные. Требуется определить: завершится ли когда-либо выполнение процедуры с этими данными; либо, что процедура всё время будет работать без остановки.
Алонзо Чёрч — американский математик и логик, внесший значительный вклад в основы информатики.
Кле́точный автома́т — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Основой является пространство из прилегающих друг к другу клеток (ячеек), образующих решётку. Каждая клетка может находиться в одном из конечного множества состояний. Решётка может быть любой размерности, бесконечной или конечной, для решётки с конечными размерами часто предусматривается закольцованность при достижении предела (границы). Для каждой клетки определено множество клеток, называемых окрестностью. Например, окрестность фон Неймана ранга 2 включает все клетки на расстоянии не более 2 от текущей. Устанавливаются правила перехода клеток из одного состояния в другое. Обычно правила перехода одинаковы для всех клеток. Один шаг автомата подразумевает обход всех клеток и на основе данных о текущем состоянии клетки и её окрестности определение нового состояния клетки, которое будет у неё при следующем шаге. Перед стартом автомата оговаривается начальное состояние клеток, которое может устанавливаться целенаправленно или случайным образом.
Вопрос о равенстве классов сложности P и NP — это одна из центральных открытых проблем теории алгоритмов, сформулированная в начале 1970-х годов и до сих пор не имеющая доказательного ответа. Если будет дан утвердительный ответ, это будет означать, что существует теоретическая возможность решать многие сложные задачи существенно быстрее, чем сейчас.
Откры́тые (нерешённые) математи́ческие пробле́мы — задачи, которые рассматривались математиками, но до сих пор не решены. Часто имеют форму гипотез, которые предположительно верны, но нуждаются в доказательстве.
Борис Авраамович Трахтенброт — советский и израильский математик в области математической логики, теории алгоритмов и кибернетики. Доктор физико-математических наук (1962), профессор (1963).
Джон Ге́нри Ко́нстантайн Уа́йтхед — английский математик, один из основных разработчиков теории гомотопий.
Тео́рия алгори́тмов — раздел математики, изучающий общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач, асимптотический анализ сложности алгоритмов, классификация алгоритмов в соответствии с классами сложности, разработка критериев сравнительной оценки качества алгоритмов и т. п. Вместе с математической логикой теория алгоритмов образует теоретическую основу вычислительных наук, теории передачи информации, информатики, телекоммуникационных систем и других областей науки и техники.
Пётр Серге́евич Но́виков (1901—1975) — советский математик, специалист по теории множеств, математической логике, теории алгоритмов и теории групп. Академик АН СССР (1960 год). Лауреат Ленинской премии (1957) и Государственной премии РФ.
Мозаика Пенроуза — общее название трёх особых типов непериодического разбиения плоскости; названы по имени английского математика Роджера Пенроуза, исследовавшего их в 1970-е годы.
Зада́ча синхрониза́ции стрелко́в — задача из области информатики и теории клеточных автоматов.
Парке́т или замощение — разбиение плоскости на многоугольники или пространства на многогранники без пробелов и наслоений.
Рафаэль Митчел Робинсон — американский математик, внёсший большой вклад в развитие математической логики.
Задача одной плитки — решённая геометрическая проблема поиска одной протоплитки, которая образует непериодическое множество плиток, то есть фигуры, копиями которой можно замостить плоскость, но только непериодичным способом.
Плитки Вана, впервые предложенные математиком, логиком и философом Хао Ваном в 1961, — это класс формальных систем. Они моделируются визуально с помощью квадратных плиток с раскрашиванием каждой стороны. Определяется набор таких плиток, затем копии этих плиток прикладываются друг к другу с условием согласования цветов сторон, но без вращения или симметрического отражения плиток.
Мартин Дэвид Дэвис — американский математик, известный своей работой, которая посвящена десятой проблеме Гильберта.
Апериодичная мозаика — это непериодичное замощение с дополнительным свойством, что замощение не содержит бесконечно больших периодических кусков. Множество типов плиток является набором непериодичных протоплиток, если копии этих плиток могут образовать только апериодичные мозаики. Мозаики Пенроуза являются наиболее известными примерами апериодичных мозаик.
Медиафайлы на Викискладе
