Авторизация
Поиск по указателям
Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений
Обсудите книгу на научном форуме Нашли опечатку?
Название: Введение в теорию автоматов, языков и вычисленийАвторы: Хопкрофт Д., Мотвани Р., Ульман Д.Аннотация: Книга известных американских ученых посвящена теории автоматов и соответствующих формальных языков и грамматик — как регулярных, так и контекстно-свободных. Во второй части рассматриваются различные машины Тьюринга, при помощи которых формализуются понятия разрешимых и неразрешимых проблем, а также определяются функции временной и емкостной оценки сложности алгоритмов. Изложение ведется строго, но доступно, и сопровождается многочисленными примерами, а также задачами для самостоятельного решения. Книга будет полезна читателям различных категорий — студентам, аспирантам, научным сотрудникам, преподавателям высших учебных заведений, а также всем, кто интересуется математическими основами современной вычислительной техники.
Язык: Рубрика: Computer science /Статус предметного указателя: Готов указатель с номерами страниц ed2k: ed2k stats Издание: 2-е изданиеГод издания: 2002Количество страниц: 527Добавлена в каталог: 08.11.2009Операции: Положить на полку |
Скопировать ссылку для форума | Скопировать ID
Предметный указатель
Обращение цепочки 154 Обращение языка 154 Объединение языков 102 149 Огден У. 294 Оператор + 127 Оператор ? 127 Оператор {n} 128 Оператор | 127 Операция диагонализации 381 Операция замыкания 215 Определение типа документа 207 214 Оракул 434 Останов машины Тьюринга 338 Остаток 251 Палиндром 185 234 Пара цепная 277 Переключательная игра Шеннона 499 Переменная 273 Переменная булева 436 Переменная грамматики 187 Перемешивание цепочек 305 Перемешивание языков 305 Пересечение с регулярным языком 299 Пересечение языков 149 Перестановка цепочки 305 Переход машины Тьюринга 330 Питтс Э. 98 Подстановка 295 Подстановка значений переменных 437 Подстановка, удовлетворяющая формуле 437 Поиск цепочек в тексте 85 Покрытие графа, реберное 462 Покрытие графа, реберное, минимальное 462 Покрытие графа, узельное 463 Покрытие графа, узельное, минимальное 463 Полнота по Карпу 434 Полнота по Куку 434 Порождение 189 Порождение левое 191 Порождение правое 191 Порядок числа 514 Пост Э. 402 Посылка 22 Правило modus ponens 24 Правило вывода 187 Правило логическое 24 Префиксное свойство 262 Принцип голубятни 82 Принцип индукции 37 Приоритет регулярного оператора 106 Пробел 331 Проблема 48 Проблема, "calls-foo" 326 Проблема, "hello, world" 321 Проблема, 2ВЫП 457 Проблема, 3-выполнимости 455 Проблема, 3ВЫП 447 455 Проблема, k-ВЫП 446 Проблема, NP-полная 432 Проблема, NP-трудная 17 433 Проблема, PS-полная 490 Проблема, ВКНФ 446 450 Проблема, выполнимости 437 Проблема, гамильтонова пути 476 Проблема, гамильтонова цикла 464 Проблема, доминирующего множества 475 Проблема, изоморфизма подграфа 475 Проблема, КБФ 494 Проблема, клики 473 Проблема, коммивояжера 429 471 Проблема, невыполнимости 482 Проблема, независимого множества 459 Проблема, неориентированного гамильтонова цикла 470 Проблема, неразрешимая 323 325 383 Проблема, ориентированного гамильтонова цикла 464 Проблема, останова 389 Проблема, пожарных депо 475 Проблема, половинной клики 475 Проблема, принадлежности цепочки языку 166 Проблема, пустоты языка 166 Проблема, разбиения 476 Проблема, разрешимая 323 338 383 Проблема, раскраски графа 473 Проблема, расписания 475 Проблема, реберного покрытия обратных связей 475 Проблема, соответствий Поста 402 Проблема, соответствий Поста, модифицированная 404 Проблема, ТАВТ 483 Проблема, точного покрытия 476 Проблема, труднорешаемая 17 Проблема, узельного покрытия 463 Проблема, формулы с кванторами 494 Проблема, эквивалентности 166 Программа приветствия мира 320 Программное обеспечение 18 Продукция 187 Продукция цепная 269 276 Пространство полиномиальное 485 Пространство полиномиальное, недетерминированное 485 Протокол 55 Путь гамильтонов 476 Путь гамильтонов ориентированный 476 Рабин М. 99 Равносильность 28 Разбиение множества состояний 178 Различимость состояний 172 177 Разложение на простые сомножители 510 Разность усеченная 335 Разность языков 153 Райс Х. 398 Регистр 368 Регулярный оператор 102 Решение проблемы соответствий Поста 402 Ритчи Д. 320 Сведение полиномиальное 424 Сведение проблем полиномиальное 432 Сведение проблемы 325 Сводимость проблем 392 Свойства замкнутости КС-языков 295 Свойства замкнутости регулярных языков 148 Свойство префиксности 262 Свойство РП-языков 397 Сети Р. 142 Символ бесполезный 269 Символ входной 19 62 Символ достижимый 270 Символ ленточный 330 Символ полезный 269 Символ порождающий 270 Символ пустой 330 Символ стартовый 187 Символ терминальный 187 Синтаксическая категория 187 Скотт Д. 99 Слагаемое 224 Следствие логическое 23 Слово 46 Слово зарезервированное 130 Слово ключевое 86 130 Слово памяти 367 Сложность временная 424 Сомножитель 223 Состояние 62 Состояние допускающее 19 62 331 Состояние достижимое 61 Состояние дьявольское 84 Состояние заключительное 62 331 Состояние начальное 19 62 331 Степень узла 477 Стокмейер Л. 521 Сэвич У. 489 Таблица переходов 65 Тавтология 483 ТАГ-система Поста 412 Тезис Черча — Тьюринга 330 Тело продукции 187 Теорема 34 Теорема Кука 439 Теорема Райса 398 Теорема Сэвича 489 Теорема Ферма великая 321 Теорема Ферма малая 514 Терм 224 Терминал 187 Томпсон К. 142 Тьюринг А. 329 Узел внутренний 198 Узел дерева 40 Ульман Дж. 14 52 142 Утверждение 22 Утверждение обратное 33 Утверждение обратное противоположному 32 Фактор 223 Ферма П. 321 Формула булева 436 Формула булева выполнимая 437 Формула булева с кванторами 491 Функция Аккермана 390 Функция переходов 62 Функция переходов, ДКА расширенная 66 Функция переходов, машины Тьюринга 331 Функция переходов, НКА 74 Функция переходов, НКА расширенная 74 Функция рекурсивная 390 Функция частичная 340 Характеристический вектор языка 381 Хаффмен Д. 98 Хомский Н. 280 Хопкрофт Дж. 14 Цепочка 46 Цепочка выводимая 194 Цепочка левовыводимая 194 Цепочка обратная 154 Цепочка правовыводимая 194 Цепочка пустая 46 Цикл гамильтонов 430 Цикл инструкции компьютера 369 Черч А. 330 Число Кармайкла 516 Число простое 510 Число псевдослучайное 499 Число составное 510 Шеннон К. 99 499 Шифрование 511 Шифрование с открытыми ключами 511 Эквивалентность 28 Эквивалентность булевых формул 447 Эквивалентность ДКА и НКА 77 Эквивалентность МП-автоматов 242 Эквивалентность МП-автоматов и КС-грамматик 251 Эквивалентность порождения и деревьев разбора 200 Эквивалентность регулярных выражений 132 Эквивалентность регулярных выражений и конечных автоматов 109 Эквивалентность состояний 172 177 Элемент ведущий 500 Элемент единичный 134 Элемент нейтральный, относительно конкатенации 47 Элемент нулевой 134 Язык 47 Язык NP-полный 432 Язык грамматики 189 193 Язык диагонализации 380 Язык ДКА 68 Язык допускаемый по заключительному состоянию 242 Язык допускаемый по пустому магазину 244 Язык контекстно-свободный 193 Язык машины Тьюринга 337 Язык неперечислимый 383 Язык нерегулярный 145 Язык НКА 75 Язык однозначный 226 Язык описания документов 211 Язык палиндромов 186 Язык пустой 48 Язык регулярного выражения 104 Язык регулярный 69 Язык рекурсивно перечислимый 337 378 Язык рекурсивный 338 383 Язык универсальный 387 Ямала Х. 142
Реклама
-порождающая 
|
|
О проекте