Nakov-Dobrikov-Programming++Algorithms-eBook-10-Feb-2013
Сумата се прибавя директно в кошницата
45.60 лв.
.
Съдържание
СЪДЪРЖАНИЕ 3
ПРЕДГОВОР ОТ НАУЧНИЯ РЕДАКТОР 13
ПРЕДГОВОР КЪМ ТРЕТОТО ИЗДАНИЕ 15
ГЛАВА 0 КОМПЮТЪРНА ИНФОРМАТИКА, АЛГОРИТМИ, ПРОГРАМИРАНЕ 17
0.1. Перспективни направления в компютърната информатика 18
0.1.1. Връзка компютър-потребител 18
0.1.2. Компютърни комуникации и сигурност 19
0.1.3. Новаторски компютърни архитектури 20
0.1.4. Моделиране на сложни феномени 20
0.1.5. Изкуствен интелект 21
0.1.6. Нетрадиционни методи за изчисление 21
0.1.7. Фундаментална компютърна информатика 22
0.2. ПОНЯТИЕТО ЛЕЙМЪР 23
0.3. Развитие на алгоритмите 24
0.3.1. Произход на думата “алгоритъм " 24
0.3.2. Алгоритмите през вековете 25
0.3.3. Анализ на алгоритмите 25
0.3.4. Изчислимост 26
0.4. ПРОГРАМИРАНЕ = ++АЛГОРИТМИ 26
0.4.1. За кого е предназначена книгата 26
0.4.2. Кратко представяне на съдържанието 27
0.4.3. Защо Cu? 28
0.4.4. Конвенция на изходните текстове 29
0.5. “СЛЕДГОВОР” 29
Посвещение 29
0.5.1. Благодарности 29
0.5.2. Търсене на грешки 30
0.5.3. Коментари и въпроси 30
ГЛАВА 1 ВЪВЕДЕНИЕ В АЛГОРИТМИТЕ 33
1.1. Основни математически понятия и алгоритми 33
1.1.1. Основни математически понятия 33
- Множества 33
- Числа 35
- Целочислено деление и остатък. Брой цифри на естествено число 37
- Сума и произведение 38
- Степен, логаритъм, n-ти корен 39
- Факториел. Рекурентни функции 40
- Матрици 41
1.1.2. Намиране броя на цифрите на произведение 43
1.1.3. Прости числа 44
- Проверка дали дадено число е просто 45
- Решето на Ератостен. Търсене на прости числа в интервал 47
- Разлагане на число на прости делители 50
- Намиране на броя на нулите, на които завършва произведение 51
1.1.4. Мерсенови и съвършени числа 52
- Мерсенови числа 52
- Съвършени числа. “Големи” числа 54
1.1.5. Биномни коефициенти, триъгълник на Паскал. Факторизация 56
1.1.6. Бройни системи и преобразуване 59
- Преминаване от десетична в p-ична бройна система 61
- Преминаване от p-ична в десетична бройна система. Формула на Хорнер 63
1.1.7. Римски цифри 65
- Представяне на десетично число с римски цифри 65
- Преобразуване на римско число в десетично 66
1.2. РЕКУРСИЯ И ИТЕРАЦИЯ 67
1.2.1. Факториел 68
1.2.2. Редица на Фибоначи 69
1.2.3. Най-голям общ делител. Алгоритъм на Евклид 74
1.2.4. Най-малко общо кратно 76
1.2.5. Връщане от рекурсията и използване на променливите 77
1.3. Основни комбинаторни алгоритми 80
1.3.1. Пермутации 80
- Генериране 81
- Кодиране и декодиране 84
- Пермутации с повторение 86
1.3.2. Вариации 86
- Видове, генериране 86
- Сума нула 88
1.3.3. Комбинации 90
1.3.4. Разбиване на числа 92
- Генериране на всички разбивания на число като сума от дадени числа 92
- Генериране на всички разбивания на число като произведение от числа 93
- Генериране на всички разбивания на число като сума от дадени числа 94
1.3.5. Разбиване на множества 96
- Числа на Бел и Стирлинг 96
1.4. ОЦЕНКА И СЛОЖНОСТ НА АЛГОРИТМИ 97
1.4.1. Размер на входните данни 99
1.4.2. Асимптотична нотация 99
1.4.3. O(F): Свойства и примери 100
1.4.4. O(F): Свойства и примери 102
1.4.5. ©(F): Свойства и примери 103
1.4.6. Асимптотични функции и реални числа 105
1.4.7. Нарастване на основните функции 106
1.4.8. Определяне на сложност на алгоритъм 107
- Елементарна операция 107
- Последователност от оператори 107
- Композиция на оператори 107
- if-конструкции 107
- Цикли 108
- Вложени цикли 108
- Още примери от вложени цикли 109
- Логаритмична сложност 110
- Рекурсия 110
1.4.9. Характеристични уравнения 112
- Линейни хомогенни уравнения с прости корени 112
- Линейни хомогенни уравнения с кратни корени 114
- Линейни нехомогенни уравнения 114
1.4.10. Специални техники за анализ на алгоритми 117
- Използване на барометър 117
- Амортизационен анализ 118
- Основна теорема 118
1.4.11. Проблеми на асимптотичната нотация 120
1.5. Въпроси и задачи 120
1.5.1. Задачи от текста 120
1.5.2. Други задачи 133
- Задачи от числа, редици, функции 133
- Задачи от матрици и общи задачи 137
- Комбинаторни задачи 138
ГЛАВА 2 ВЪВЕДЕНИЕ В СТРУКТУРИТЕ ОТ ДАННИ 143
2.1. Списък, стек, опашка 144
- Стек 145
- Опашка 146
- Дек 147
2.1.1 Последователна (статична) реализация 147
- Стек 147
- Опашка 149
2.1.2 Свързана (динамична) реализация 151
- Включване на елемент 152
- Обхождане на списък 153
- Включване след елемент, сочен от даден указател 153
- Включване пред елемент, сочен от даден указател 154
- Изтриване по зададен ключ и указател към начало на списъка 154
- Изтриване на елемент, сочен от даден указател 155
2.2. Двоични дървета 158
- Търсене по даден ключ 163
- Включване на нов връх 164
- Изключване на връх по даден ключ 164
- Обхождане 168
2.3. Балансирани дървета 169
2.3.1. Ротация. Червено-черни дървета 172
2.3.2. B-дървета 174
2.4. Хеш-таблици 176
- Хеш-функция 176
- Колизии 177
2.4.1. Класически хеш-функции 178
- Остатък при деление с размера на таблицата 178
- Мултипликативно хеширане 178
- Хеш-функции върху части от ключа 179
- Сравнение на някои от разгледаните хеш-функции 179
- Хеш-функции върху символни низове 180
2.4.2. Справяне с колизии 184
- Затворено хеширане 184
- Линейно пробване 184
- Квадратично пробване 185
- Двойно хеширане 185
- Отворено хеширане 185
- Допълнителна памет за колизии 185
- Списък на препълванията 186
2.4.3. Реализации на хеш-таблица 186
2.5. Въпроси и задачи 192
2.5.1. Задачи от текста 192
2.5.2. Други задачи 196
ГЛАВА 3 СОРТИРАНЕ 199
3.1. СОРТИРАНЕ ЧРЕЗ СРАВНЕНИЕ 200
3.1.1. Дърво на сравненията 200
3.1.2. Сортиране чрез вмъкване 201
3.1.3. Сортиране чрез вмъкване с намаляваща стъпка. Алгоритъм на Шел 203
3.1.4. Метод на мехурчето 206
3.1.5. Сортиране чрез клатене 207
3.1.6. Бързо сортиране на Хоор 208
3.1.7. Метод на “зайците и костенурките” 213
3.1.8. Сортиране чрез пряк избор 215
3.1.9. Пирамидално сортиране на Уилямс 216
3.1.10. Минимална времева сложност на сортирането чрез сравнение 219
3.2. СОРТИРАНЕ ЧРЕЗ ТРАНСФОРМАЦИЯ 221
3.2.1. Сортиране чрез множество 221
3.2.2. Сортиране чрез броене 223
3.2.3. Побитово сортиране 226
3.2.4. Метод на бройните системи 229
3.2.5. Сортиране чрез пермутация 232
3.3. Паралелно сортиране 233
3.3.1. Принцип на нулите и единиците 235
3.3.2. Битонични последователности 236
3.3.3. “Изчисти наполовина” 237
3.3.4. Сортиране на битонична последователност 237
3.3.5. Сливаща схема 237
3.3.6. Сортираща схема 238
3.3.7. Транспозиционна сортираща схема 238
3.3.8. Четно-нечетна сливаща схема на Бетчер 239
3.3.9. Четно-нечетна сортираща схема 239
3.3.10. Пермутационна схема 239
3.4. Въпроси и задачи 240
3.4.1. Задачи от текста 240
3.4.2. Други задачи 243
ГЛАВА 4 ТЪРСЕНЕ 245
4.1. Последователно търсене 246
4.1.1. Последователно търсене в сортиран списък 248
4.1.2. Последователно търсене с преподреждане 249
4.2. Търсене със стъпка. Квадратично търсене 251
4.3. Двоично търсене 252
4.4. ФИБОНАЧИЕВО ТЪРСЕНЕ 256
4.5. Интерполационно търсене 258
4.6. Въпроси и задачи 260
4.6.1. Задачи от текста 260
4.6.2. Други задачи 261
ГЛАВА 5 ТЕОРИЯ НА ГРАФИТЕ 263
5.1. Основни понятия 263
5.2. Представяне и прости операции с граф 267
5.2.1. Списък на ребрата 267
5.2.2. Матрица на съседство, матрица на теглата 268
5.2.3. Списък на наследниците (списък на инцидентност) 268
5.2.4. Матрица на инцидентност между върхове и ребра 269
5.2.5. Компоненти на свързаност 269
5.2.6. Построяване и прости операции с графи 270
5.3. Обхождане на граф 271
5.3.1. Обхождане в ширина 271
5.3.2. Обхождане в дълбочина 274
5.4. Оптимални пътища, цикли и потоци в граф 276
5.4.1. Директни приложения на алгоритмите за обхождане 277
- най-кратък път между два върха по брой на върховете 277
- проверка дали граф е цикличен 279
- намиране на всички прости пътища между два върха 281
5.4.2. Екстремален път в граф 283
- неравенство на триъгълника 284
- алгоритъм на Форд-Белман 284
- алгоритъм на Флойд 285
.
