Босс В. — Лекции по математике. Том 10 :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Красота

Босс В. — Лекции по математике. Том 10

Босс В. — Лекции по математике. Том 10

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Лекции по математике. Том 10

Автор: Босс В.

Аннотация:

Книга посвящена теории сложности алгоритмов в той ее части, где речь идет о противостоянии Р- и NP-задач. В резонанс с проблемой «Р против NP» входит обширная тематика: комбинаторные задачи на графах, неразрешимые проблемы теории алгоритмов, криптография, целочисленное программирование, вероятностные методы, квантовые вычисления, алгоритмы Хачияна и Кармаркара для линейного программирования, а также полиномиальный алгоритм AKS для выяснения простоты числа. Особое внимание уделяется геометрическому взгляду на проблему, который в привычном уже пейзаже обнаруживает свежие ракурсы.
Изложение отличается краткостью и прозрачностью.
Для студентов, преподавателей, инженеров и научных работников.

Язык:

Рубрика: Математика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 2008

Количество страниц: 216

Добавлена в каталог: 18.06.2009

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

3-ВЫП      29
Max-ВЫП      190
O-большое      45
P-задача      52
PCP-теорема      154
q-бит      170
Аддитивная группа вычетов      124
Алгоритм внутренней точки      103
Алгоритм Дейкстры      74
Алгоритм Диффи — Хелмана      118
Алгоритм Евклида      121
Алгоритм Кармаркара      103
Алгоритм нормальный Маркова      51
Алгоритм полиномиальный      13
Алгоритм прямого типа      139
Алгоритм псевдополиномиальный      71
Алгоритм типа Лас-Вегас      155
Алгоритм типа Монте-Карло      155
Алгоритм Флойда — Уоршелла      74
Алгоритм Шора      179
Аффинная сводимость      144
Аффинное отображение      145
База матроида      77
Базис квантовый      169
Бит      46
Вершинное покрытие      23 188
ВМТ      56 150
Входное слово      36
Выпуклая комбинация      131
Выпуклая оболочка      131
Гейт      175
Гиперплоскость      131
Глубина дерева      137
Грань многогранника      132
Граф      19
Граф двудольный      23
Граф многогранника      132
Граф ориентированный      20
Граф планарный      23
Граф полный      22 188
Граф связный      19
Графа вершина      19
Графа ребро      19
Дерево      19
Дизъюнктивная нормальная форма      28
Дизъюнкция      27
Длина входа      13 46
Длина описания задачи      13 46
ДНФ      28
Дополнение задачи      69
Допустимый многогранник      93
Дорожка невырожденности      31
ДПФ      177
Жадный алгоритм      12 78
Задача (0, 1)-РЮКЗАК      26 189
Задача (0, 1)-ЦЛП      26
Задача 2-ВЫП      52
Задача 3-С      24
Задача max-ВЫП      28
Задача NP-полная      58
Задача SAT      28
Задача SPACE-полная      82
Задача АЛГОРИТМ МАРКОВА      50
Задача АНТИКЛИКА      23 189
Задача БУЛЕВА ФОРМУЛА С КВАНТОРАМИ      82
Задача БФК      82
Задача ВЕРШИННОЕ ПОКРЫТИЕ      23 188
Задача ВЫП      28 190
Задача ВЫПОЛНИМОСТЬ      28 190
Задача ГАМИЛЬТОНОВ ЦИКЛ      21 188
Задача двойственная      94
Задача ИВК      30 190
Задача ИЗОМОРФИЗМ ГРАФОВ      22 188
Задача ИЗОМОРФИЗМ ПОДГРАФУ      22 188
Задача индивидуальная      18
Задача ИСЧЕРПАНИЕ ВЕРШИН КУБА      30 190
Задача КЛИКА      22 188
Задача коммивояжер      21 188
Задача КРАТЧАЙШИЙ ПУТЬ      72
Задача ЛИНЕЙНОЕ НЕРАВЕНСТВО      92
Задача ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ      26
Задача ЛН      92 97
Задача массовая      18
Задача МАШИНА ТЬЮРИНГА      49 59 190
Задача МИНИМАЛЬНОЕ ОСТОВНОЕ ДЕРЕВО      12
Задача МОД      12
Задача МТ      49
Задача о максимальном потоке      75
Задача о минимальном разрезе      75
Задача о назначениях      24
Задача ПАРОСОЧЕТАНИЕ      23
Задача ПОКРЫТИЕ      161
Задача ПРОСТОЕ ЧИСЛО      32
Задача ПЧ      32
Задача РАЗБИЕНИЕ      26 189
Задача РАСКРАСКА ГРАФА В 3 ЦВЕТА      23 191
Задача распознавания      14
Задача РЮКЗАК      25 189
Задача СОСТАВНОЕ ЧИСЛО      32
Задача СЧ      32
Задача ТЕОРЕМА      82
Задача транспортная      27 190
Задача ТРЕХМЕРНОЕ СОЧЕТАНИЕ      24
Задача труднорешаемая      54
Задача универсальная переборная      58 59 66
Задача ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ      26 189
Задача ЦЕЛОЧИСЛЕННЫЙ РЮКЗАК      26 189
Задача ЦЛП      26 189
Задача ШИФР      116
Запутанные состояния      170
ЗК      21 188
Интерактивная система      84
Интерактивное доказательство      85
Инцидентность      19
Квантовый бит      170
Класс Co-NP      16 69
Класс IP      85
Класс NP      16 54
Класс NPC      58
Класс P      15 52

Класс P/poly      83
Класс PCP      86 153
Класс PSPACE      81
КНФ      28
Код единичный      43
Комплексная амплитуда      169
Контур      19
Конус      132
Конусная интерпретация      128
Конъюнктивная нормальная форма      28
Конъюнкция      27
Крайнее множество      133
Крайняя точка      133
Кубит      170
Латентное состояние      169
Лес      19
Линейное разделяющее дерево      137
Литерал      28
Логическая функция      27
Логические связки      27
ЛРД      137
Максимальное паросочетание      24
Малая теорема Ферма      108
Матрица неразложимая      31
Матрица перестановки      31
Матрица смежности      19
Матрица унитарная      172
Матроид      77
Матроид коциклический      79
Матроид разрезов      79
Матроид трансверсалей      79
Матроид циклический      79
Машина с полиномиальным будильником      82
Машина с полиномиальным сторожем      82
Машина Тьюринга      41
Машина Тьюринга вероятностная      56 150
Машина Тьюринга недетерминированная      55
Машина универсальная      42
Метод ветвей и границ      163
Метод резолюций      52
Метод Хачияна      100
Метода эллипсоидов      100
Многогранник      132
Многогранник Бондаренко — Падберга      143
Многогранник релаксационный      142
Многогранник циклический      134
Множество аффинное      131
Множество выпуклое      131
Множество независимое      77
Мультипликативная группа вычетов      124
Описание вершинное      127
Описание фасетное      127
Опорная гиперплоскость      132
Оракул      86
Орграф      20
Остов графа      12
Отделимость      132
Открытый ключ      113
Отображение аффинное      131
Отсекающая плоскость Гомори      165
Перечислимое множество      37
Плотность графа      22 188
Подграф      22 188
Подсказка      54
Полиномиальная проверяемость      16
Полиэдр      133
Преобразование Уолша — Адамара      172
Путь      19
Разделяющая гиперплоскость      132
Размер входа      13
Размер описания      97
Разрешимое множество      37
Релятивизация      87
Сводимость по Карпу      57
Сводимость полиномиальная      57
Сильная NР-полнота      71
Симплекс-метод      96
Система различных представителей      79
Система с нулевым разглашением      85 119
Смежные вершины      19
Совершенное паросочетание      23
Спутанные состояния      170
Сравнимые функции      64 65
Схемная сложность      83
Сцепленные состояния      170
Тезис Тьюринга      42
Теорема китайская об остатках      124
Теорема Кука      59
Теорема Миллера      110
Теорема Мошкова      138
Теорема отделимости      132
Теорема Холла      24
Теорема Эдмондса — Фалкерсона      79
Теорема Эйлера      114
Теоремы Гёделя      39
Теория Рамсея      89
Тест Ферма      108
Трансверсаль      79
Трансверсаль частичная      79
Удостоверение      54
Универсальная машина      42
Унитарная матрица      172
Усиление вероятности      155
Факторизация      32
Фасета      132
Формула Стирлинга      11
Функция k-местная      35
Функция вычислимая      35
Цепь      19
Цикл      19
Цикл гамильтонов      19
Цикл матроида      77
Цикл простой      19
Цикл элементарный      19
Число Кармайкла      109
Число Рамсея      89
Эквивалентность полиномиальная      57
ЭПР-парадокс      183
Язык      15
Языка распознавание      15

Реклама

© Электронная библиотека попечительского совета мехмата МГУ, 2004-2024

Электронная библиотека мехмата МГУ

Valid HTML 4.01!

|

Valid CSS!

О проекте