Programming = ++Algorithms;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0.4.3. Защо Cи?

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

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

Посвещение

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

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

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

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

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

• Множества
• Числа
• Целочислено деление и остатък. Брой цифри на естествено число
• Сума и произведение
• Степен, логаритъм, n-ти корен
• Факториел. Рекурентни функции
• Матрици

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

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

• Проверка дали дадено число е просто
• Решето на Ератостен. Търсене на прости числа в интервал
• Разлагане на число на прости делители
• Намиране на броя на нулите, на които завършва произведение

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

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

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

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

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

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

• Представяне на десетично число с римски цифри
• Преобразуване на римско число в десетично

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

1.2.1. Факториел

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

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

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

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

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

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

• Генериране
• Кодиране и декодиране
• Пермутации с повторение

1.3.2. Вариации

• Видове, генериране
• Сума нула

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

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

• Генериране на всички разбивания на число като сума от дадени числа
• Генериране на всички разбивания на число като произведение от числа
• Генериране на всички разбивания на число като сума от дадени числа

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

• Числа на Бел и Стирлинг

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

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

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

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

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

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

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

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

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

• Елементарна операция
• Последователност от оператори
• Композиция на оператори
• if-конструкции
• Цикли
• Вложени цикли
• Още примери от вложени цикли
• Логаритмична сложност
• Рекурсия

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

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

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

• Използване на барометър
• Амортизационен анализ
• Основна теорема

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

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

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

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

• Задачи от числа, редици, функции
• Задачи от матрици и общи задачи
• Комбинаторни задачи

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

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

• Стек
• Опашка
• Дек

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

• Стек
• Опашка

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

• Включване на елемент
• Обхождане на списък
• Включване след елемент, сочен от даден указател
• Включване пред елемент, сочен от даден указател
• Изтриване по зададен ключ и указател към начало на списъка
• Изтриване на елемент, сочен от даден указател

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

• Търсене по даден ключ
• Включване на нов връх
• Изключване на връх по даден ключ
• Обхождане

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

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

2.3.2. B-дървета

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

• Хеш-функция
• Колизии

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

• Остатък при деление с размера на таблицата
• Мултипликативно хеширане
• Хеш-функции върху части от ключа
• Сравнение на някои от разгледаните хеш-функции
• Хеш-функции върху символни низове

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

– Затворено хеширане

• Линейно пробване
• Квадратично пробване
• Двойно хеширане

– Отворено хеширане

• Допълнителна памет за колизии
• Списък на препълванията

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• най-кратък път между два върха по брой на върховете
• проверка дали граф е цикличен
• намиране на всички прости пътища между два върха

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

• неравенство на триъгълника
• алгоритъм на Форд-Белман
• алгоритъм на Флойд
• обобщен алгоритъм на Флойд
• алгоритъм на Дейкстра
• повдигане в степен на матрицата на съседство
• алгоритъм на Уоршал и матрица на достижимост
• най-дълъг път в ацикличен граф
• най-дълъг прост път между два върха в произволен граф

5.4.3. Цикли

• намиране на фундаментално множество от цикли
• минимален цикъл през връх

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

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

5.4.6. Потоци

• Максимален поток
• повече от един източник и консуматор
• капацитет на върховете

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• алгоритъм на Крускал
• алгоритъм на Прим
• частично минимално покриващо дърво

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

• максимални независими множества

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

5.7.4. База

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

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

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

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

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

• ограничаване отдолу на хроматичното число
• намиране на върховото хроматичното число

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

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

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

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

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

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

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

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

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

6.1.4. Примери

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

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

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

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

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

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

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

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

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

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

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

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

6.5.1. Игра “X”-чета и “O”

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

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

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

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

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

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

• NP-пълни задачи
• Изчерпващи задачи

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

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

7.2. Мажорант

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

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

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

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

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

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

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

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

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

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

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

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

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

8.1.Въведение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• проверка дали число е просто

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

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

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

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

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

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

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

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

10.1. Кодиране

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10.6.1. Ентропия

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

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

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

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

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

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

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

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

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

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

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

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

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

10.7.2. JPEG

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

10.7.4. Уейвлети

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

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

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

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

Литература

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

Изтеглете книгата “Програмиране ==++Алгоритми;” в PDF