Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
В алгоритмической теории информации колмогоровская сложность объекта есть мера вычислительных ресурсов, необходимых для точного определения этого объекта.
Ко́мпле́ксный ана́лиз, тео́рия фу́нкций ко́мпле́ксного переме́нного — раздел математического анализа, в котором рассматриваются и изучаются функции комплексного аргумента.
Алгори́тм Де́йкстры — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации OSPF и IS-IS.
Суффиксное дерево — бор, содержащий все суффиксы некоторой строки. Позволяет выяснять, входит ли строка w в исходную строку t, за время O(|w|), где |w| — длина строки w.
Контекстно-свободная грамматика — частный случай формальной грамматики, у которой левые части всех продукций являются одиночными нетерминалами. Смысл термина «контекстно-свободная» заключается в том, что есть возможность применить продукцию к нетерминалу, причём независимо от контекста этого нетерминала.
Лемма о накачке — важное утверждение теории автоматов, позволяющее во многих случаях проверить, является ли данный язык автоматным. Поскольку все конечные языки являются автоматными, эту проверку имеет смысл делать только для бесконечных языков. Термин «накачка» в названии леммы отражает возможность многократного повторения некоторой подстроки в любой строке подходящей длины любого бесконечного автоматного языка.
В вычислительной технике diff — утилита сравнения файлов, выводящая разницу между двумя файлами. Эта программа выводит построчно изменения, сделанные в файле. Современные реализации поддерживают также двоичные файлы. Вывод утилиты называется «diff», или, что более распространено, патч, так как он может быть применён с программой patch. Вывод других утилит сравнения файлов также часто называется «diff».
Алгоритм поиска строки Бойера — Мура считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером и Джеем Муром в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.
Альтернати́ва Фредго́льма — совокупность теорем Фредгольма о разрешимости интегрального уравнения Фредгольма второго рода.
Лемма о разрастании для контекстно-свободных языков — лемма, по аналогии с одноименной леммой для регулярных языков позволяющая относительно несложно доказывать, что данный язык не является контекстно-свободным.
В информатике неоднозначной грамматикой называется формальная грамматика, которая может породить некоторую строку более чем одним способом. Язык называется существенно неоднозначным, если он может быть порождён только неоднозначными грамматиками.
Спектральная теорема — класс теорем о матрицах линейных операторов, дающих условия, при которых такие матрицы могут быть диагонализированы, то есть представлены в виде диагональной матрицы в некотором базисе. Эти теоремы позволяют свести вычисления, включающие диагонализируемые матрицы к гораздо более простым вычислениям, использующим соответствующие диагональные матрицы.
Факторизация с помощью эллиптических кривых — алгоритм факторизации натурального числа с использованием эллиптических кривых. Данный алгоритм имеет субэкспоненциальное время выполнения. Является третьим по скорости работы после общего метода решета числового поля и метода квадратичного решета.
В теории формальных языков теорема Майхилла — Нероуда определяет необходимое и достаточное условия регулярности языка.
«Трактат о шифрах» — одна из первых в Европе книг, посвящённая криптоанализу, написана Леоном Баттиста Альберти — итальянским учёным, гуманистом, писателем, одним из зачинателей новой европейской архитектуры и ведущим теоретиком искусства эпохи Возрождения. Своей работой он внёс существенный вклад в развитие криптографии, предложив идею многоалфавитного шифра, и изобрёл устройство, реализующее шифр многоалфавитной замены, получившее название «диск Альберти».
Лемма Шепли — Фолкмана связывает две операции выпуклой геометрии — сложение по Минковскому и выпуклую оболочку. Лемма имеет приложения в ряде дисциплин, в том числе в математической экономике, оптимизации и теории вероятностей. Лемма и связанные с ней результаты позволяют дать утвердительный ответ на вопрос «Близка ли к состоянию выпуклости сумма нескольких множеств?».
L-система или система Линденмайера — это параллельная система переписывания и вид формальной грамматики. L-система состоит из алфавита символов, которые могут быть использованы для создания строк, набора порождающих правил, которые задают правила подстановки вместо каждого символа, начальной строки («аксиомы»), с которой начинается построение, и механизма перевода образованной строки в геометрические структуры.
