1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 110
Текст из файла (страница 110)
НОЙ целых чисел 345 8.11. Еще раз о применении китайской георемы об остатках 347 8.!2. Разреженные полиномы 348 Упражнения 350 Замечания по литературе 353 354 10. НР.ПОЛНЫЕ 3~ДАЧИ 404 7а БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ЕГО ПРИЛОЖЕНИЕ 7.1.
Дискретное преобразование Фурье и обратное к нему 7.2. Алгоритм быстрого преобразования Фурье 7.3. ЕПФ при использовании битовых операций 7.4. Произведение полиномов 7.5. Алгоритм Шенхаге — Штрассена для умножения целых чисел Упражнения Замечания по литературе АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ НАД ЦЕЛЫМИ ЧИСЛАМИ И 8 ° ПОЛИНОМАМИ 8.1. Аналогии между целыми числами н полиномами 8.2. Умножение и деление целых чисел 8.3. Умножение и деление полиномов 9. АЛГОРИТМЫ ИДЕНТИФИКАЦИИ 9.1.
Конечные автоматы н регулярные выражения 9.2. Распознавание образов, задаваемых регулярными выражениями 9.3. Распознавание подцепочек 9.4. Двусторонний детерминированный магазинный автомат 9.5. Позиционные деревья и идентификаторы позиций Упражнения Замечания по литературе 10.1. Недетерминнрованные машины Тьюринга 10.2. Классы Л и Д'Я' 10.3. Языки и задачи 10Л. ХР-полнота залечи выполнимости 10.5.
Еще несколько ХР-полных задач Ю.б. Задачи с полиномиально ограниченной памятью Упражнения Замечания по литературе Е 1 е НЕКОТОРЫЕ ДОКАЗУЕМО ТРУДНО РАЗРЕШИМЫЕ ЗАДАЧИ 11.!. Иерархии по сложности 1!.2. Иерархия по емкостной сложности дая детерминированных машин Тьюринга 11.3. Задача, требующая зкспоненциальных времени и памяти хнО 298 303 304 308 310 354 363 367 373 385 398 403 405 4!4 417 420 428 440 446 450 45! 45! 452 456 1!.4.
Незлеиентарная задача Упражнения Замечания по литературе 455 471 474 1 2, НИЖНИЕ ОЦЕНКИ ЧИСЛА АРИФМЕТИЧЕСКИХ ОПЕРАЦ14Я 475 12.1. Поля 475 12.2. Еще раз о неветвящихся программах 477 !2.3. Матричная формулировка задач 4?9 12.4. Нижняя граница аля висла умножений, связанная с рангом по строкам 480 12.5. Нижняя граница для числа умножений, связанная с рангом по столбцам 483 12.5.
Граница для числа умножений, свизанная с рассмотрением строк и столбцов 488 12.7. Предварительная обработка 490 Упражнения 493 Замечания по литературе 501 СПИСОК ЛИТЕРАТУРЫ ГЛОССАРИЯ ИМЕННОЯ УКАЗАТЕЛЬ ПРЕДМЕТНЫЯ УКАЗАТЕЛЬ 502 514 5Г5 519 А. Ако, Дж, Хопкрофт, Дж. Упьмаи ПОСТРОЕНИЕ И АНАЛИЗ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ Научный редактор Л. Штейвпресо Младюнй редактор И. Полякова Художник С. Бычков Художествеавмй редаатор Б. Шаповалов Техвическяй редактор Л. Бнрюкова Корректор И.
Гяря ИБ № !079 Схаво в ЯзбоР 6.06.78 ПоДпнсаво к печати 23,11.76 ФоРмат 60Х90Ч,з БУмага типографская № 2 Гарнетура литератур. Печать высокая. Объем 16,76 бум. л. Уел. печ. л. 33,80 Уч..нзд. л. 33,92 Тнрвж 26000 зкз. Изд. № 1/9799 Заказ № 2763. це хр. аа . Издательство «Мнр» Москва, 1-0 Ряжский пер., 2 Ордеяа Октябрьской Революция я ордена Трудового Крзсяого Знамени первая Образповаз тнпографяя ямеп» А. х. и!данова союзполиграфпрома прн Государственном комитете СССР по делам яздзтельств, полнграфни и кнвжиой торговли.
Москва, М-ае, Баловав. 26 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
