Теормин по 2-й части (1123849)
Текст из файла
Страницы указаны для 2-го издания (печатного)Глава 3 Оценивание числа шагов алгоритма1. Алгоритм Евклида. (E) Число шагов в алгоритме Евклида <= минимального числа из 2-храссматриваемых (стр 73)Сложность по числу делений - ( )---- a1 – меньшее из чиселТочность этой оценки () доказывается через числа Фибоначи (стр 82)Ограничение снизу (стр 83)Ограничение снизу (стр 86)2.3.4.5.6.7.8.( )Расширенный алгоритм Евклида (EE) ( )Ограничение снизу (стр 83)()Бинарный поиск места элемента в упорядоченном массиве из n элементов (BS) (стр 77)(суть в делении массива пополам на каждом шаге)( )⌊⌋⌈⌉На этом алгоритме основан алгоритм определения принадлежности точки некоторомувыпуклому многоугольникуСложность сортировки Фон-Нейманом (Сортировки Слиянием) (стр 79)( )⌈⌉По числу сравнений меньше, а по числу присваиваний равна( )(стр. 107)Сложность по числу сравнений сортировки бинарными вставками (стр 81)( ) (⌉)⌈(стр 87) ( )Поиск корней уравнения (стр 81)Метод деления пополам (число итераций) –( )Метод Ньютона (касательных) (число итераций) – ()Завершимость работы алгоритма (стр 88)Вложенные циклы.
пример асимптотики при вложенных циклах (стр 93)Нецелые размеры входа (стр 95). Разрывность сложности для алгоритма Евклида (стр 96)Глава 4 Нижняя граница сложности алгоритмов некоторого класса. Оптимальные алгоритмы9. Сложность алгоритма поиска наименьшего элемента массива длинны n по числу (стр.105) сравнений – (n-1)10. Для всех алгоритмов сортировки выполнено: (стр. 106)( )( )⌈⌉, где T(n) – временная сложностьсортировки сравнениями11. Если сложность сортировки по числу сравнений не превосходит n*log2n +cn, тогда( )(стр. 107)12. Алгоритм поиска места элемента в массиве (нижняя граница) (стр 108)( )⌈()⌉13. Алгоритм вычисления an с помощью умножения (нижняя граница) (стр 108)( )⌈⌉14.
Остановился на странице 10815. Алгоритм одновременного выбора наибольшего и наименьшего элементов массивадлинны n (стр. 109)( )⌈ ⌉– сложность по числу сравнений, приведённый алгоритм - оптимален16. Вычисление значения полинома в данной точке (стр 111) (лишь упомянуто)Схема Горненра – оптимальный алгоритм17. Оптимального алгоритма может не существовать (стр.
111)18. Объяснение не оптимальности алгоритмов сортировки – бинарный алгоритм возведения встепень (стр. 112) (об оптимальной сортировке см приложение F)19. Достаточное условие оптимальности алгоритма: (стр 114)Если f(n) – является асимптотической нижней границей сложности, и если TA(n) = O(f(n)) тоэтот алгоритм оптимален по порядку сложности и TA(n) = Θ(f(n))20. Бинарный алгоритм возведения в степень (стр.
114) оптимален по порядку сложности вклассе алгоритмов вычисления an с помощью умножений21. Алгоритм построения Эйлерова цикла данного ориентированного графа (стр. 114) сосложностью O(|E|) - оптимален22. Алгоритм построения остовного дерева (Алгоритм Прима) (стр 115) – оптимален попорядку сложности, и его сложность – Θ(|V|2))23. Любая сортировка допускающая оценку (() явля6ется оптимальнойпо порядку сложности (стр. 116)24.
Сортировка Бинарными вставками – оптимальны по порядку сложности по числусравнений (стр. 116)25. Сортировка Фон-Неймана – оптимальны по порядку сложности по числу сравнений (стр.116)26. Функция log2n! Является нижней границей сложности в среднем для класса алгоритмовсортировки массивов длинны n с помощью представлений (стр 117)27. Сортировка Бинарными вставками и Сортировка фон-Неймана и Быстрая сортировка –оптимальны по порядку сложности в среднем по числу сравнений (стр.
119)28. Нижняя граница сложности в среднем алгоритмов одновременного выборанаибольшего и наименьшего элементов массива длинны n >= 2, с помощью сравнений(стр. 121)( ){Эта оценка – оптимальна, и алгоритм оптимален29. Принцип Яо (стр.
127)30. Для любой рандомизированной сортировки (которую теоретически можно задать, какконечное множество детерминированных алгоритмов сортировки) её сложность не можетбыть меньше, чем log2n! (стр. 128)31. Рандомизированная быстрая сортировка оптимальна по порядку сложности в класерандомизированных сортировок (стр. 128)Глава 5 Битовая сложность«*» - означает, что мы рассматриваем битовую сложность32. Алгоритм сложения столбиком при использовании m в качестве размера входа (число бит( )( )максимального из чисел)() (стр.
135)Этот алгоритм является оптимальным (ибо мы не можем игнорировать содержимоебитов)33. Сверхнаивное умножение (стр. 136) (умножение посредством сложения) битоваясложность = Θ(2mm)( )( )34. Наивное умножение () (стр. 137)( )( )( )( )()35.
Вычисление n! с помощью пошаговых наивных умножений имеет битовую временнуюсложность O((n log n)2) (стр. 139)36. Сложность умножения чисел a1 … an при пошаговом наивном умножении. Пусть M –суммарная битовая длинна этих чисел, тогда временная сложность допускает верхнююоценку O(M2) (стр. 139)( )( )37. Сложность наивного деления (стр. 140) – битовая сложность =()(())38. Построение k-ичной записи числа n (перевод из 2-ичной системы счисления в k-ичную)(стр. 141)битовая cложность = O(log2n)39. Алгоритм Евклида битовая сложность (стр.
142)O(log a0 log a1) или O(log2a0) или O(m2) при m = λ(a1)Если алгоритм Евклида (или расширенный Алгоритм Евклида) основывается на делении состатком, затраты которого оцениваются O(log v log u), то его битовая оценка имеет видΘ(log2a0)40. Обращение в поле (нахождение обратного элемента в поле) (стр. 147)Если расширенный алгоритм Евклида основывается на алгоритме деления и умножения сосложностью O(log v log u), то битовая сложность обращения числа в поле Zp допускаетоценку O(log2p)41. Малая теорема Ферма (стр. 147) – p – простое, a – произвольное, тогда ap==a (mod p)42. Пусть a – целое, p – натуральное, и они взаимно просты, тогда n – просто, тогда и толькотогда, когда (x-a)n=xn-a(mod n) (т.е.
числовые коэффициенты при одинаковых степенях вполиномах, расположенных в левой и правой части – сравнимы по модулю n) (стр. 148)43. Алгоритм AKS (Агравал, Кайал, Саксена) – алгоритм определения простоты числа,сложность – O с волной (m21/2), если ещё допустить некоторые, пока не доказанные вматематике гипотезы, то O с волной (m6) (стр 148)44. Возведение в степень булевой матрицы (стр 152) –Обычным умножением – Θ(n3log n)Если B(n) – сложность используемого алгоритма умножения булевых матриц, то сложностьвозведения в степень = n + B(n)( λ(n)+ λ*(n) -2) (первое λ – битовая длинна числа n, второе –количество единиц в его двоичной записи)45.
Построение транзитивно-рефлексивного замыкания ориентированного графа (АлгоритмУоршелла) (стр. 153) – (n вершин) затрачивая 2*n3+n битовых операцийПространственная сложность ограничена константойГлава 6. Рекуррентные соотношения, как средство анализа сложности алгоритмов46. Если мы будет добавлять по единице к некоторому числу начиная с нуля, то длядостижения 2n-1 потребуется 2n-n-1 переносов (стр. 158)47. Лучше если рекуррентная формула зависит независимо только от одного предыдущегозначения, потому что если она зависит от нескольких, то это приводит к повторнымвычислениям (хотя странно, почему нельзя просто сохранять значения) (стр.
160)48. Пусть дан рекурсивный алгоритм Yn=U(Yn-1, …, Yn-k) и k >= 2, тогда количество вычисленийэтой функции при нахождении Yn = Θ(αnk), где 2 – 1/k <= αnk < 2 (стр. 161)49. Рекурсивная сортировка слияниями (стр. 162) ⌋⌉(⌊⌋) ⌊( ) (⌈⌉) ⌈Пространственная сложность = Ω(n)50. Теорема о рекуррентном неравенстве (случай <=) (стр.
166)51. Теорема о рекуррентном неравенстве (случай >=) (стр. 167)52. Сложность рекурсивной сортировки слияниями (стр. 168) – (и по числу сравнений, и почислу перемещений) (стр. 168) Θ(n log n)53. Бинарное возведение в степень n (стр. 168) TRS(n)= Θ(log n)54. Построение выпуклой оболочки объединения 2-х выпуклых многоугольников (стр. 169)O(n log n)55. Умножение Карацубы (стр. 171)56. Умножение 2-х чисел методом Карацубы (стр. 173) TKM(m)= Θ(mlog2 3)57. Умножение 2-х матриц со стороной порядка 2k – (Метод Штрассена) (стр .
173) –TSt(n)= Θ(nlog2 7)58. Умножение 2-х булевых матриц с применением алгоритма Штрассена и арифметики помодулю n+1. (стр. 175) Битовая сложность O с волной (nlog2 7)59. Есть вроде бы что-то более зубодробительное начиная с стр 176, но вроде это лишнееГлава 7 Сводимость60. Сведение умножения к возведению в квадрат (стр. 184)61. Сведение задачи построения транзитивно-рефлексивного замыкания графа к задачеумножения 2-х булевых матриц порядка n (стр. 185)62. Нахождение транзитивно-рефлексивного замыкания ориентированного графа (стр. 188)Существует алгоритм со сложностью O(n2,82) а точнее O с волной (nlog2 7)⌉63. Нижняя грань сложности алгоритмов сортировки.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
