Съдържание

 

Предговор от научния редактор.. 13

 

Глава 0 Компютърна информатика, алгоритми, програмиране. 15

0.1. Перспективни направления в компютърната информатика.. 16

0.1.1. Връзка компютър-потребител. 16

0.1.2. Компютърни комуникации и сигурност.. 17

0.1.3. Новаторски компютърни архитектури. 18

0.1.4. Моделиране на сложни феномени. 18

0.1.5. Изкуствен интелект.. 19

0.1.6. Нетрадиционни методи за изчисление. 19

0.1.7. Фундаментална компютърна информатика. 20

0.2. Понятието леймър. 20

0.3. Развитие на алгоритмите. 22

0.3.1. Произход на думата “алгоритъм”. 22

0.3.2. Алгоритмите през вековете. 23

0.3.3. Анализ на алгоритмите. 23

0.3.4. Изчислимост.. 23

0.4. програмиране = ++алгоритми.. 24

0.4.1. За кого е предназначена книгата. 24

0.4.2. Кратко представяне на съдържанието. 25

0.4.3. Защо Cи?. 25

0.4.4. Конвенция на изходните текстове. 26

0.5. “Следговор”. 27

Посвещение. 27

0.5.1. Благодарности. 27

0.5.2. Коментари и въпроси. 28

 

Глава 1 Въведение в Алгоритмите. 29

1.1. Основни математически понятия и алгоритми.. 29

1.1.1. Основни математически понятия. 29

- Множества. 29

- Числа. 31

- Целочислено деление и остатък. Брой цифри на естествено число. 33

- Сума и произведение. 33

- Степен, логаритъм, n-ти корен. 35

- Факториел. Рекурентни функции. 36

- Матрици. 37

1.1.2. Намиране броя на цифрите на произведение. 39

1.1.3. Прости числа. 40

- Проверка дали дадено число е просто. 41

- Решето на Ератостен. Търсене на прости числа в интервал. 42

- Разлагане на число на прости делители. 45

- Намиране на броя на нулите, на които завършва произведение. 46

1.1.4. Мерсенови и съвършени числа. 47

- Мерсенови числа. 47

- Съвършени числа. “Големи” числа. 48

1.1.5. Биномни коефициенти, триъгълник на Паскал. Факторизация. 50

1.1.6. Бройни системи и преобразуване. 54

- Преминаване от десетична в p-ична бройна система. 56

- Преминаване от p-ична в десетична бройна система. Формула на Хорнер. 58

1.1.7. Римски цифри. 59

- Представяне на десетично число с римски цифри. 59

- Преобразуване на римско число в десетично. 60

1.2. Рекурсия и итерация.. 61

1.2.1. Факториел. 62

1.2.2. Редица на Фибоначи. 63

1.2.3. Най-голям общ делител. Алгоритъм на Евклид. 68

1.2.4. Най-малко общо кратно. 70

1.2.5. Връщане от рекурсията и използване на променливите. 71

1.3. Основни комбинаторни алгоритми.. 74

1.3.1. Пермутации. 74

- Генериране. 74

- Кодиране и декодиране. 77

- Пермутации с повторение. 79

1.3.2. Вариации. 80

- Видове, генериране. 80

- Сума нула. 82

1.3.3. Комбинации. 83

1.3.4. Разбиване на числа. 85

- Генериране на всички разбивания на число като сума от дадени числа. 85

- Генериране на всички разбивания на число като произведение от числа. 86

- Генериране на всички разбивания на число като сума от дадени числа. 87

1.3.5. Разбиване на множества. 88

- Числа на Бел и Стирлинг. 89

1.4. Оценка и сложност на алгоритми.. 90

1.4.1. Размер на входните данни. 92

1.4.2. Асимптотична нотация. 92

1.4.3. O(n): Свойства и примери. 93

1.4.4. W(n): Свойства и примери. 95

1.4.5. Q(n): Свойства и примери. 96

1.4.6. Асимптотични функции и реални числа. 98

1.4.7. Нарастване на основните функции. 99

1.4.8. Определяне на сложност на алгоритъм.. 99

- Елементарна операция. 99

- Последователност от оператори. 100

- Композиция на оператори. 100

- if-конструкции. 100

- Цикли. 100

- Вложени цикли. 101

- Още примери от вложени цикли. 101

- Логаритмична сложност. 102

- Рекурсия. 102

1.4.9. Характеристични уравнения. 105

- Линейни хомогенни уравнения с прости корени. 105

- Линейни хомогенни уравнения с кратни корени. 107

- Линейни нехомогенни уравнения. 108

1.4.10. Специални техники за анализ на алгоритми. 109

- Използване на барометър. 109

- Амортизационен анализ. 110

- Основна теорема. 110

1.4.11. Проблеми на асимптотичната нотация. 112

1.5. Въпроси и задачи.. 112

1.5.1. Задачи от текста. 112

1.5.2. Други задачи. 124

- Задачи от числа, редици, функции. 124

- Задачи от матрици и общи задачи. 128

- Комбинаторни задачи. 130

 

Глава 2 Въведение в структурите от данни.. 133

2.1. Списък, стек, опашка.. 134

- Стек. 135

- Опашка. 136

- Дек. 137

2.1.1 Последователна (статична) реализация. 137

- Стек. 137

- Опашка. 139

2.1.2 Свързана (динамична) реализация. 141

- Включване на елемент. 142

- Обхождане на списък. 143

- Включване след елемент, сочен от даден указател. 143

- Включване пред елемент, сочен от даден указател. 144

- Изтриване по зададен ключ и указател към начало на списъка. 144

- Изтриване на елемент, сочен от даден указател. 145

2.2. Двоични дървета.. 148

- Търсене по даден ключ. 152

- Включване на нов връх. 152

- Изключване на връх по даден ключ. 153

- Обхождане. 156

2.3. Балансирани дървета.. 158

2.3.1. Ротация. Червено-черни дървета. 161

2.3.2. B-дървета. 163

2.4. Хеш-таблици.. 165

- Хеш-функция. 165

- Колизии. 166

2.4.1. Класически хеш-функции. 167

- Остатък при деление с размера на таблицата. 167

- Мултипликативно хеширане. 167

- Хеш-функции върху части от ключа. 167

- Сравнение на някои от разгледаните хеш-функции. 168

- Хеш-функции върху символни низове. 168

2.4.2. Справяне с колизии. 172

- Затворено хеширане. 172

- Линейно пробване. 172

- Квадратично пробване. 173

- Двойно хеширане. 173

- Отворено хеширане. 174

- Допълнителна памет за колизии. 174

- Списък на препълванията. 174

2.4.3. Реализации на хеш-таблица. 175

2.5. Въпроси и задачи.. 180

2.5.1. Задачи от текста. 180

2.5.2. Други задачи. 184

 

Глава 3 Сортиране. 187

3.1. Сортиране чрез сравнение. 188

3.1.1. Дърво на сравненията. 188

3.1.2. Сортиране чрез вмъкване. 189

3.1.3. Сортиране чрез вмъкване с намаляваща стъпка. Алгоритъм на  Шел. 191

3.1.4. Метод на мехурчето. 194

3.1.5. Сортиране чрез клатене. 195

3.1.6. Бързо сортиране на Хоор. 195

3.1.7. Метод на “зайците и костенурките”. 201

3.1.8. Сортиране чрез пряк избор. 203

3.1.9. Пирамидално сортиране на Уилямс. 204

3.1.10. Минимална времева сложност на сортирането чрез сравнение. 207

3.2. Сортиране чрез трансформация.. 208

3.2.1. Сортиране чрез множество. 208

3.2.2. Сортиране чрез броене. 210

3.2.3. Побитово сортиране. 213

3.2.4. Метод на бройните системи. 216

3.2.5. Сортиране чрез пермутация. 219

3.3. Паралелно сортиране. 220

3.3.1. Принцип на нулите и единиците. 222

3.3.2. Битонични последователности. 223

3.3.3. “Изчисти наполовина”. 223

3.3.4. Сортиране на битонична последователност.. 223

3.3.5. Сливаща схема. 224

3.3.6. Сортираща схема. 224

3.3.7. Транспозиционна сортираща схема. 225

3.3.8. Четно-нечетна сливаща схема на Бетчер. 225

3.3.9. Четно-нечетна сортираща схема. 225

3.3.10. Пермутационна схема. 226

3.4. Въпроси и задачи.. 227

3.4.1. Задачи от текста. 227

3.4.2. Други задачи. 230

 

Глава 4 Търсене.. 231

4.1. Последователно търсене. 232

4.1.1. Последователно търсене в сортиран списък. 234

4.1.2. Последователно търсене с преподреждане. 235

4.2. Търсене със стъпка. Квадратично търсене. 236

4.3. Двоично търсене. 238

4.4. Фибоначиево търсене. 241

4.5. Интерполационно търсене. 243

4.6. Въпроси и задачи.. 245

4.6.1. Задачи от текста. 245

4.6.2. Други задачи. 246

 

Глава 5 Теория на графите. 247

5.1. Основни понятия.. 247

5.2. Представяне и прости операции с граф.. 251

5.2.1. Списък на ребрата. 251

5.2.2. Матрица на съседство, матрица на теглата. 252

5.2.3. Списък на наследниците (списък на инцидентност). 252

5.2.4. Матрица на инцидентност между върхове и ребра. 253

5.2.5. Компоненти на свързаност.. 253

5.2.6. Построяване и прости операции с графи. 253

5.3. Обхождане на граф.. 255

5.3.1. Обхождане в ширина. 255

5.3.2. Обхождане в дълбочина. 258

5.4. Оптимални пътища, цикли и потоци в граф.. 260

5.4.1. Директни приложения на алгоритмите за обхождане. 260

- най-кратък път между два върха по брой на върховете. 260

- проверка дали граф е цикличен. 263

- намиране на всички прости пътища между два върха. 264

5.4.2. Екстремален път в граф.. 266

- неравенство на триъгълника. 267

- алгоритъм на Форд-Белман. 267

- алгоритъм на Флойд. 268

- обобщен алгоритъм на Флойд. 270

- алгоритъм на Дейкстра. 272

- повдигане в степен на матрицата на съседство. 275

- алгоритъм на Уоршал и матрица на достижимост. 275

- най-дълъг път в ацикличен граф.. 276

- най-дълъг прост път между два върха в произволен граф.. 279

5.4.3. Цикли. 279

- намиране на фундаментално множество от цикли. 279

- минимален цикъл през връх. 281

5.4.4. Хамилтонови цикли. Задача за търговския пътник. 282

5.4.5. Ойлерови цикли. 284

5.4.6. Потоци. 287

- Максимален поток. 288

- повече от един източник и консуматор. 292

- капацитет на върховете. 292

5.5.Транзитивност и построяване. Топологично сортиране. 293

5.5.1. Транзитивно затваряне. Алгоритъм на Уоршал. 293

5.5.2. Транзитивно ориентиране. 294

5.5.3. Транзитивна редукция. 297

5.5.4. Контрол на компании. 298

5.5.5. Топологично сортиране. 300

5.5.6. Пълно топологично сортиране. 302

5.5.7. Допълване на ацикличен граф до слабо свързан. 304

5.5.8. Построяване на граф по дадени степени на върховете. 305

5.6. Достижимост и свързаност.. 305

5.6.1. Компоненти на свързаност.. 306

5.6.2. Компоненти на силна свързаност в ориентиран граф.. 307

5.6.3. Разделящи точки в неориентиран граф. Двусвързаност.. 309

5.6.4. k-свързаност на неориентиран граф.. 312

5.7.Оптимални подмножества и центрове. 313

5.7.1. Минимално покриващо дърво. 313

- алгоритъм на Крускал. 313

- алгоритъм на Прим. 317

- частично минимално покриващо дърво. 319

5.7.2. Независими множества. 319

- максимални независими множества. 320

5.7.3. Доминиращи множества. 322

5.7.4. База. 324

5.7.5. Център, радиус и диаметър. 326

- p-център и p-радиус. 328

5.7.6. Двойкосъчетание. Максимално двойкосъчетание. 331

5.8. Оцветявания и планарност.. 332

5.8.1. Оцветяване на граф. Хроматично число. 332

- ограничаване отдолу на хроматичното число. 333

- намиране на върховото хроматичното число. 333

5.8.2. Планарност на графи. 333

5.9. Въпроси и задачи.. 335

5.9.1. Задачи от текста. 335

5.9.2. Други задачи. 341

 

Глава 6 Търсене с връщане. NP-пълни задачи.. 347

6.1. Класификация на задачите. 347

6.1.1. Сложност по време. 347

6.1.2. Сложност по памет.. 348

6.1.3. Нерешими задачи. 348

6.1.4. Примери. 348

6.2. NP-пълни задачи.. 351

6.3. Търсене с връщане. 352

6.3.1. Удовлетворимост на булева функция. 353

6.3.2. Оцветяване на граф.. 358

6.3.3. Най-дълъг прост път в цикличен граф.. 360

6.3.4. Разходка на коня. 362

6.3.5. Задача за осемте царици. 365

6.3.6. Разписание на училищна програма. 368

6.3.7. Побуквено превеждане. 372

6.4. Метод на разклоненията и границите. 374

6.4.1. Задача за раницата (оптимална селекция). 375

6.5. Оптимални стратегии при игри.. 377

6.5.1. Игра "X"-чета и "O". 378

6.5.2. Принцип на минимума и максимума. 382

6.5.3. Алфа-бета отсичане. 382

6.5.4. Алфа-бета изследване до определена дълбочина. 384

6.6. Въпроси и задачи.. 385

6.6.1. Задачи от текста. 385

6.6.2. Други задачи. 389

- NP-пълни задачи. 389

- Изчерпващи задачи. 400

 

Глава 7 Разделяй и владей.. 403

7.1. Намиране на k-ия по големина елемент.. 403

7.2. Мажорант.. 410

7.3. Сливане на сортирани масиви.. 420

7.4. Сортиране чрез сливане. 424

7.5. Бързо повдигане в степен.. 430

7.6. Алгоритъм на Щрасен за бързо умножение на матрици.. 432

7.7. Бързо умножение на дълги числа.. 435

7.8. Задача за Ханойските кули.. 438

7.9. Организиране на първенства.. 440

7.10. Циклично изместване на елементите на масив.. 444

7.11. Покриване с шаблон.. 448

7.12. Въпроси и задачи.. 449

7.12.1. Задачи от текста. 449

7.12.2. Други задачи. 451

 

Глава 8 Динамично оптимиране. 453

8.1.Въведение. 453

8.2.Класически оптимизационни задачи.. 456

8.2.1. Задача за раницата. 456

8.2.2. Братска подялба. 466

8.2.3. Умножение на матрици. 469

8.2.4. Триангулация на многоъгълник. Числа на Каталан. 474

8.2.5. Оптимално двоично дърво за претърсване. 479

8.2.6. Най-дълга обща подредица. 483

8.2.7. Най-дълга ненамаляваща подредица. 487

8.2.8. Сравнение на символни низове. 491

8.2.9. Задача за разделянето. 495

8.3.Неоптимизационни задачи.. 497

8.3.1. Числа на Фибоначи. 498

8.3.2. Биномни коефициенти. 501

8.3.3. Спортни срещи. 502

8.3.4. Представяне на сума с неограничен брой монети. 505

8.3.5. Представяне на сума с ограничен брой монети. 507

8.3.6. Разбиване на естествено число. 509

8.3.7. Числа без две съседни нули. 510

8.3.8. Разпознаване на контекстно свободен език. 512

8.3.9. Хедонийски език. 516

8.3.10. Символно умножение. 518

8.4. Други интересни оптимизационни задачи.. 519

8.4.1. Такси компания. 520

8.4.2. Билети за влак. 521

8.4.3. Числов триъгълник. 523

8.4.4. Представяне на сума с минимален брой монети. 527

8.4.5. Опроводяване на платка. 529

8.4.6. На опашка за билети. 531

8.4.7. Разпределение на ресурси. 533

8.4.8. Семинарна зала. 535

8.4.9. Крайпътни дървета. 538

8.4.10. Разрязване на материали. 540

8.4.11. Зациклен израз. 542

8.4.12. Домино-редица. 545

8.4.13. Трионообразна редица. 548

8.5. Въпроси и задачи.. 550

8.5.1. Задачи от текста. 550

8.5.2. Други задачи. 557

 

Глава 9 Евристични и вероятностни алгоритми.. 561

9.1. Алчни алгоритми.. 561

9.1.1. Египетски дроби. 562

9.1.2. Максимално съчетание на дейности. 564

9.1.3. Минимално оцветяване на граф и дърво. 567

9.1.4. Алгоритми на Прим и Крускал. 570

9.1.5. Дробна задача за раницата. 571

9.1.6. Задача за магнитната лента. 573

9.1.7. Процесорно разписание. 574

9.1.8. Разходката на коня. Хиперкуб. Код на Грей. 576

9.2. Търсене с налучкване. 581

9.2.1. Алгоритми Монте Карло и Лас Вегас. 582

- проверка дали число е просто. 583

9.2.2. Числени алгоритми с приближение. 586

9.2.3. Генетични алгоритми. 587

9.3. Достигане на фиксирано приближение. 592

9.3.1. Върхово покритие на граф.. 592

9.4. Въпроси и задачи.. 594

9.4.1. Задачи от текста. 594

9.4.2. Други задачи. 597

 

Глава 10 Компресиране. 601

10.1. Кодиране. 601

10.2. Обща класификация.. 602

10.3. Кодиране на последователности.. 603

10.3.1. Премахване на нулите. 603

10.3.2. Компресиране с битови карти. 605

10.3.3. Полубайтово пакетиране. 607

10.3.4. Съвместно използване на битови карти и полубайтово пакетиране. 609

10.3.5. Двуатомно кодиране. 610

10.3.6. Замяна на шаблони. 611

10.3.7. Относително кодиране. 612

10.3.8. Математическо очакване. Кодиране с линейно предсказване. 614

10.3.9. Кодиране на последователности. 616

10.3.10. Един представителен пример: PackBits. 618

10.4. Статистически методи.. 619

10.4.1. Алгоритъм на Шенън-Фано. 619

10.4.2. Алгоритъм на Хъфман. 623

10.4.3. Обобщен алгоритъм на Хъфман. 633

10.4.4. Kод с разделители. 634

10.4.5. Аритметично кодиране. 635

10.5. Адаптивно компресиране. 643

10.5.1. Адаптивно компресиране по Хъфман. 645

10.5.2. Модели на Марков. 647

10.5.3. Един представителен пример: MNP-5. 650

10.6. Речниково кодиране. 652

10.6.1. Ентропия. 653

10.6.2. Малко история. 657

10.6.3. Стандарти и патенти. 658

10.6.4. Статични срещу адаптивни методи. 658

10.6.5. LZ77. Компресиране с плъзгащ се прозорец. 659

10.6.6. LZSS. Едно подобрение. 660

10.6.7. FLZ. Друг вариант на LZ77. 661

10.6.8. LZW. Модификацията на Уелч. 661

10.6.9. GIF. Гледната точка на CompuServe. 667

10.6.10. Оптимални срещу алчни алгоритми. 668

10.6.11. Компресиране в реално време. 669

10.6.12. LZW срещу Марков. 670

10.7. Компресиране със загуба.. 671

10.7.1. Изрязване и квантифициране. 671

10.7.2. JPEG.. 672

10.7.3. Компресиране на видеоизображение. MPEG.. 674

10.7.4. Уейвлети. 676

10.7.5. Компресиране с фрактали. 677

10.8. Въпроси и задачи.. 678

10.8.1. Задачи от текста. 678

10.8.2. Други задачи. 685

 

Литература.. 687

Предметен указател.. 692