1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 109
Текст из файла (страница 109)
Сложность средняя Смежный (ад!асеп() 64 Смешение (б!зр!асешеп1) 164 Содевжимое регистра (1Ье соп1еп(з о! а гейийег) 16 СОРТ (ЗОЯТ) 82 СОРТВЗБАЛТЫВАНИЕМ (В()ВВЬЕЗОЕТ) 123 Сортдеревом (Ьеарзог1) 106, 110 Сортировка (зогВпй) 93 — внешняя (ех1егпа!) 94 — внутренняя (1п1егпа!) 99 — вставками (!пзегВоп) 126 — вычерпыванием (Ьнс1ге() 95 — лексикографическая (!ех)соагарЫс) 96, 98 — слиянием (шегйе) 82 — с помощью сравнений (Ьу сошраг(зопз) 104 — топологическая (1оро!ой!са!) 87 — цифровая (габ!х) 95 пиндмнтныи иклзлтнль ощ!а!) 491 Массив, Очередь, Тавтология (1ап1о!ойу) 446 Теорема о свертке (сопчо!и!!оп Роеогегп) 288 ТЕРМ (ТЕРМ) 380 Терминатор (1егпппа1ог) 379 Тип данных (да(а 1уре) 48 Точка сочленения (аг1!сйаВоп ро!п1) 206 Тройка допустимая (адппззаЫе 1Нр!е) 309 Трудно разрешимый (!п(гас(аЬ!е) 404 УДАЛИТЬ (ОВЕЕТЕ) 128 УЗЕЛ (УЕЯТЕХ) 71 Сортирующее дерево (Ьеар) 106 СОСТОЯНИЕ ($ТАТ()Б) 53 Состояние (з(а(е) 40 — допускающее (ассерВпб) 41, !66, 356, 375 — заключительное (Впа1) 4!.
См. также Состояние допускающ — — 2ДМА (о! а 2ОРОА) 375 — начальное (!пгЕа!) 40 — начальное (з(аг!) 166, 356, 375 — управляющего устройства (о1 а Епйе соп1го!) 375 СОЧЕТ (СОМЕ) 89 СПИСОК (! 15Т) 147 Список (!!51) 58 — дважды связанный (бопЫу !!п1геб) 6! — свободный (1гее) 60 — смежностей (аб)асепсу) 66 Способность пропускная (сарзсцу) 448, 497 Сравнение (согпраызоп) 38 — ключевое (1геу) !21 СТ (ОЕО) 3!2 Стабильный (метод сортировки) (з1аЫе) 126 Статистики порядковые (огбег з1а(ой!сз) 93, 1!7 Стек (з1ас)г) 61 Степень (бейгее) — полинома 3!2, 49! — полинома от нескольких переменных (о1 а щпИгиаг!а1е ро!уп — узла 64 Стоимость (соз1) 223, 225 — пути (о! а ра1Л) 223 Структура данных (да1а з1гпс!пге) 58. См.
также Граф, Дерево, Список, Стек СУММАСТРОК ()(О!УЗОМ) 278 Сумматор (асснщн1а1ог) 16 Суффикс (зпййх) 355 Схемз логическая (!ой!с с!гспй) см. Сеть логическая — сдвигающвя (зй!!1)пй пеЬиогй) 497 Сцепление см. Коннатенация СЧЕТ (СООР)Т) 71, 153 Счетчик команд (!осаВоп соцп1ег) 16, 26 Сын (зоп) 67 — о 386 — левый (!еП) 68 — правый (НйЫ) 68 ПРЕДМЕТНЫИ УКАЗАТЕЛЬ Узел (чег1ех, попе) 64 — смежный (аб)асеп1) Умножение (пшРИрИсаИоп) — активное (ас1гяе) 484 — векторов (о! ТеЫогз) 493 — и/или (апб!ог) 352, 399 — комплексных чисел (о1 сошр!ех пшпЬегз) 478, 479, 489 — матриц (о! ша(г!сез) 259, 495 — матрицы нв вектор (о1 а ша1пх Ьу а чес1ог) 486, 494 — полиномов (о1 ро!упогп!а1з) 480, 487, 492, 493 — целых чисел (о! !п(ейегз) 77 — 80, 304 Уровень узла (!ете! о1 а тег1ех) 68 Устройство управляющее (ИпНе соп1го1) 40, 165, 356 Форма (!опп) — билинейная (ЫИпеаг) 495 — конъюнктивная нормальная (соп)нпсИче поппе!) 427 — нормальная Хомского (СЬошз)гу поппе!) 9! Формула булева (Воо!сап ехргеш!оп) 417 — выполнимзя (заИЕВаЫе) 4! 9 — Лагранжа интерполяционная (Енйгапй!Еп Ы1егро!нИоп !оппп1а) 329 Фрагмент стека (з1ас1г !гвше) 73 Функция (ЫпсИоп) 5! — булеза (Воо!енп) 498 — логарифмическая (1ойапИчппс) 23 — конструируемая по времени (1нпе-сопЫгос1аЫе) 47! — — — емкости (эрисе) 41! — — — памяти см.
Функция, конструируемая по емкости — отказав (1айнге) 368 — переходов (пех1-шоте) 4! — переходов (з(а1е !гапз!Иоп) 356 — расстановки (ЬазЫпй) !30 — стоимости (соз1) 130 — экспоненциальнан (ехропепыа!) 39 — элементарная (е1егпеп1агу) 466 Ханойские башни (1оиегз о1 Нзпо!) 88 Характеристический (еектор) (сйагас1ег!ЗИс) 63 Цвет (со!ог) 421 ЦЕПОЧКА (БТК1ЫСг) 99 Цепочка (Ыг!п6) 355 — допускземаи (автоматом, машиной) (эссер(ед) !66, 357, 376 — пустая (егпр1у) 165, 355 — с несущественными символами (чг!1Ь боп'1 сзгез) 399 Цепочка.
текст (1ех1-з(Нпй) 363 Цепь (сйа!п) 397 ЦИКЛ (СУСЕЕ) 457 Цикл (сус1е) 64 — гэмильтонов (НаппИоп) 421 — — ориентированный (РИгес1еб) 421 — эйлеров (Ен!ег) 249 Цнркулянт (с!гсо!ап1) 310 угрндыитный укАЭАтель ЧАСТИЧНО НАЙТИ (раг1!а! Р(ХО) !58 Черпак (Ьнс!ге1) 95 ЧИС (ХЫМ) 278 Число (пшпЬег) — Каталаиа (Са1а!ап) 9! — хранимое в регистре (Могеб !п а гей!з(ег) !4, 25, 37 — хроматическое (сйгоша1!с) 421 ЧН (РР) 158 Шаг (вычисления) (з1ер) 477 Шаг (работы автомата, машины) (шоте) — 2ДМА (Ьу а 2ОРРА) 376 — НМТ (Ьу а ХОТМ) 406 Эквивалентность (ейн!ча!енсе) — автоматов (о1 ан1шпа1а) 166 — векторов по модулю (о1 чес(огз шодйо) 480 — регулярных выражений (о1 тейп!аг ехргезз!опз) 356 — отношение (ге1а1!оп) 206 — состояний (о! з!а(ез) !66 Элем (!1еш) 58 ЭЛЕМЕНТ (Е1.ЕМЕХТ) 153 ЭЛЕМЕНТ (!ТЕМ) 59 Элемент единичный (гйепЕ1у) 224 — й-й наименьший (бйе й(Ь зша!!ез( е1ешеп1) 1!7 — обратный (шчегзе) 256 Элементы снежные матрицы (аб!асеп! епййез о! а ша(г!х) 252 Язык (!апяпайе) !9,355 — бесконтекстный (соп(ех(бгее) 401 — допускаемый автоматом (ассер1еб Ьу ап ао1оша(оп) 166, 357 — — 2ДМА (Ьу а 20РОА] 376 — — МТ (Ьу а ТМ) 42 — — НМТ (Ьу а ХОТМ) 407 — — программой (Ьу а ргойгаш) 19 — контекстный (соп1ех(-зелзП1че) 449 ХР-полный (ХР-сошр!е1е) 416 — полный для недетерминнрованного полиномиального времени (!ог пенде!ег.
ш!п!з(!с ро!упош1в! (ппе) см. Язык ХР-полный — порождаемый грамматикой (йепега(ед Ьу а йгапппаг) 91 — регулярный (гейи1аг) 356 СОДЕРЖАНИЕ 1 а МОДЕЛИ ВЫЧИСЛЕНИР 57 93 94 95 104 553 ПРЕДИСЛОВИЕ К РУССКОМУ ПЕРЕВОДУ ПРЕДИСЛОВИЕ !.1. Алгоритмы н их сложности 1.2. Машины с произвольным доступом к памяти 1.3. Вычислнтельнаи сложность РАМ-программ 1.4. Модель с хранимой программой 1.5. Модификация РАМ 1.6. Простейшая модель вычислений: машина Тьюринга 1.7. Связь машин Тьюринга и РАМ 1.8.
Язык высокого уровня — Упрощенный Алгол Упражнения Замечания по литературе 2 ° РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ 2.!. Структуры данных: списки, очереди н стеки 2.2. Представления множеств 2.3. Графы 2.4. Деревья 2.5. Рекурсия 2.6. Разделяй н властвуй 2.7. Балансировка 2.8. Динамическое программирование 2.9. Эпилог Упражнения Замечания по литературе 3, СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ 3.1. Задача сортировки 3.2. Цифровая сортировка З.З. Сортировка с помощью сравнений 11 15 22 26 32 39 45 47 54 56 58 63 64 67 70 75 81 83 85 86 92 106 !11 117 119 122 12? АЛГОРИТМЫ НА ТРАФАХ 197 238 247 254 3.4.
Сортдеревом — упорядочение с помощью 0(и 1ой и) сравнений 3.5. Быстрсорт — упорядочение за среднее время 0(п !ой и) 3.6. Порядковые статистики 3.7. Среднее время для порядковых статистик Упражнения Замечания по литературе СТРУКТУРЫ ДАННЫХ ДЛЯ ЗАДАЧ, КАСАЮЩИХСЯ РАЕОТЫ С МНОЖЕСТВАМИ 4.1. Основные операции над множествами 4.2. Метод расстановки 4.3.
Лвоичный поиск 4.4. Деревья двоичного поиска 4.5. Оптимальные деревья двоичного поиска 4.6. Простой алгоритм для яахождения объединения непересекающихся множеств 4.7. Лревовидные структуры для задачи ОБЪЕЛИНИТЬ вЂ” НАЙТИ 4.6. Приложения и обобщения алгоритма ОБЪЕЛИНИТЬ вЂ” НАЙТИ 4.9. Схемы сбалансированных деревьев 4.10. Словари и очереди с приоритетами 4.11. Сливаемые деревья 4.12. Сцепляемые очереди 4.13. Разбвение 4.!4.
Резюме Упражнения Замечания по литературе 5.1. Остовное дерево наименьшей стоимости 5.2. Метод поиска в глубину 5.3. Лвусвязность 5.4. Поиск в глубину в ориентированном графе 5,5. Сильная связность 5.6. Задачи нахождения путей 6,7. Алгоритм траизитввного замыкания 5.8. Алгоритм нахождении кратчайшего пути 5.9. Задачи о путях и умножение матриц 5.10. Задачи с одним источником 5.11. Ломннаторы в ориентированных ациклических графах: комбинирование понятий Упражнения Замечания по литературе УМНОЖЕНИЕ МАТРИЦ И СВЯЗАННЫЕ С НИ)ь ОПЕРАЦИИ 6.1. Основные понятия 6.2.
Алгоритм Штрассена для умножения матриц 6.3. Обращение матриц 6.4. НВП-разложение матрицы 6.5. Приложения НВП-разложения 6.6. Умножение булевых матриц Упражнении Замечания по литературе 128 132 135 136 14! 146 150 162 168 171 175 178 181 188 188 !95 197 202 206 2!4 2!6 223 227 229 230 235 255 255 259 262 263 272 274 279 283 3!1 3!2 313 8.4. Модульиаи арифметика 323 8.5.
Модульная арифметика полиномов и вычисление их значений 327 8.6. Применение китайской теоремы об остатках 329 8.7. Китайская теорема об остатках и интерполяция полиномов 333 8.8. Наибольшие общие делители и алгоритм Евклида 336 8.9, Асимптотически быстрый алгоритм нахождения НОД полнномов 339 8.10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
