Книгата “Програмиране = ++Алгоритми;” на Преслав Наков и Панайот Добриков, сочена от мнозина като “библията на състезателите по програмиране” има нов уеб сайт:

www.programirane.org

Книгата би могла да се ползва като продължение на книгите “Въведение в програмирането със C#” и “Въведение в програмирането с Java” и като допълнение към учебния план от безплатните курсове по програмиране за начинаещи, провеждани в Академията на Телерик, тъй като запознава читателя с по-сложни алгоритмични проблеми, често използвани по олимпиадите и състезанията по програмиране. Книгата може да бъде изтеглена безплатно в PDF формат.

Следва съкратено съдържание на обхванатия в книгата учебен материал:

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

• Основни математически понятия
• Намиране броя на цифрите на произведение
• Прости числа, мерсенови и съвършени числа
• Биномни коефициенти, триъгълник на Паскал. Факторизация
• Бройни системи и преобразуване, римски цифри
• Рекурсия и итерация: факториел, редица на Фибоначи
• Най-голям общ делител, алгоритъм на Евклид, най-малко общо кратно
• Връщане от рекурсията и използване на променливите
• Основни комбинаторни алгоритми: пермутации, вариации, комбинации
• Разбиване на числа
• Разбиване на множества
• Оценка и сложност на алгоритми
• Асимптотична нотация: O(n), W(n), Ɵ(n)
• Определяне на сложност на алгоритъм

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

• Списък, стек, опашка
• Последователна (статична) реализация
• Свързана (динамична) реализация
• Двоични дървета
• Балансирани дървета
• Ротация
• Червено-черни дървета
• B-дървета
• Хеш-таблици
• Класически хеш-функции
• Справяне с колизии
• Затворено хеширане
• Отворено хеширане
• Реализации на хеш-таблица

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

• Сортиране чрез сравнение
• Дърво на сравненията
• Сортиране чрез вмъкване
• Сортиране чрез вмъкване с намаляваща стъпка. Алгоритъм на Шел
• Метод на мехурчето
• Сортиране чрез клатене
• Бързо сортиране на Хоор (Quicksort)
• Метод на “зайците и костенурките”
• Сортиране чрез пряк избор
• Пирамидално сортиране на Уилямс
• Минимална времева сложност на сортирането чрез сравнение
• Сортиране чрез трансформация
• Сортиране чрез множество
• Сортиране чрез броене
• Побитово сортиране
• Метод на бройните системи
• Сортиране чрез пермутация
• Паралелно сортиране

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

• Последователно търсене
• Последователно търсене в сортиран списък
• Последователно търсене с преподреждане
• Търсене със стъпка. Квадратично търсене
• Двоично търсене
• Фибоначиево търсене
• Интерполационно търсене

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

• Графи – основни понятия
• Представяне и прости операции с граф: списък на ребрата, матрица на съседство, матрица на теглата, списък на наследниците (списък на инцидентност), матрица на инцидентност между върхове и ребра
• Компоненти на свързаност
• Построяване и прости операции с графи
• Обхождане на граф: обхождане в ширина, обхождане в дълбочина
• Оптимални пътища, цикли и потоци в граф
• Директни приложения на алгоритмите за обхождане
• Екстремален път в граф
• Цикли
• Хамилтонови цикли. Задача за търговския пътник
• Ойлерови цикли
• Потоци
• Транзитивност и построяване. Топологично сортиране
• Транзитивно затваряне. Алгоритъм на Уоршал
• Транзитивно ориентиране
• Транзитивна редукция
• Топологично сортиране
• Пълно топологично сортиране
• Допълване на ацикличен граф до слабо свързан
• Построяване на граф по дадени степени на върховете
• Достижимост и свързаност
• Компоненти на свързаност
• Компоненти на силна свързаност в ориентиран граф
• Разделящи точки в неориентиран граф. Двусвързаност
• k-свързаност на неориентиран граф
• Оптимални подмножества и центрове
• Минимално покриващо дърво
• Независими множества
• Доминиращи множества
• База на граф
• Център, радиус и диаметър
• Двойкосъчетание. Максимално двойкосъчетание
• Оцветявания и планарност
• Оцветяване на граф. Хроматично число
• Планарност на графи

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

• Класификация на задачите: сложност по време, сложност по памет, нерешими задачи, NP-пълни задачи
• Търсене с връщане
• Удовлетворимост на булева функция
• Оцветяване на граф
• Най-дълъг прост път в цикличен граф
• Разходка на коня
• Задача за осемте царици
• Разписание на училищна програма
• Побуквено превеждане
• Метод на разклоненията и границите
• Задача за раницата (оптимална селекция)
• Оптимални стратегии при игри
• Игра “X”-чета и “O”
• Принцип на минимума и максимума, алфа-бета отсичане, алфа-бета изследване до определена дълбочина

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

• Намиране на k-ия по големина елемент
• Мажорант
• Сливане на сортирани масиви
• Сортиране чрез сливане
• Бързо повдигане в степен
• Алгоритъм на Щрасен за бързо умножение на матрици
• Бързо умножение на дълги числа
• Задача за Ханойските кули
• Организиране на първенства
• Циклично изместване на елементите на масив
• Покриване с шаблон

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

• Динамично оптимиране – въведение
• Класически оптимизационни задачи
• Задача за раницата
• Братска подялба
• Умножение на матрици
• Триангулация на многоъгълник. Числа на Каталан
• Оптимално двоично дърво за претърсване
• Най-дълга обща подредица
• Най-дълга ненамаляваща подредица
• Сравнение на символни низове
• Задача за разделянето
• Неоптимизационни задачи
• Числа на Фибоначи
• Биномни коефициенти
• Спортни срещи
• Представяне на сума с неограничен брой монети
• Представяне на сума с ограничен брой монети
• Разбиване на естествено число
• Числа без две съседни нули
• Разпознаване на контекстно свободен език
• Хедонийски език
• Символно умножение
• Други интересни оптимизационни задачи
• Такси компания
• Билети за влак
• Числов триъгълник
• Представяне на сума с минимален брой монети
• Опроводяване на платка
• На опашка за билети
• Разпределение на ресурси
• Семинарна зала
• Крайпътни дървета
• Разрязване на материали
• Зациклен израз
• Домино-редица
• Трионообразна редица

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

• Алчни алгоритми
• Египетски дроби
• Максимално съчетание на дейности
• Минимално оцветяване на граф и дърво
• Алгоритми на Прим и Крускал
• Дробна задача за раницата
• Задача за магнитната лента
• Процесорно разписание
• Разходката на коня. Хиперкуб. Код на Грей
• Търсене с налучкване
• Алгоритми Монте Карло и Лас Вегас
• Числени алгоритми с приближение
• Генетични алгоритми
• Достигане на фиксирано приближение
• Върхово покритие на граф

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

• Кодиране
• Обща класификация
• Кодиране на последователности
• Премахване на нулите
• Компресиране с битови карти
• Полубайтово пакетиране
• Съвместно използване на битови карти и полубайтово пакетиране
• Двуатомно кодиране
• Замяна на шаблони
• Относително кодиране
• Математическо очакване. Кодиране с линейно предсказване
• Кодиране на последователности
• Един представителен пример: PackBits
• Статистически методи
• Алгоритъм на Шенън-Фано
• Алгоритъм на Хъфман
• Обобщен алгоритъм на Хъфман
• Kод с разделители
• Аритметично кодиране
• Адаптивно компресиране
• Адаптивно компресиране по Хъфман
• Модели на Марков
• Един представителен пример: MNP-5
• Речниково кодиране
• Ентропия
• Стандарти и патенти
• Статични срещу адаптивни методи
• LZ77. Компресиране с плъзгащ се прозорец
• LZSS. Едно подобрение
• FLZ. Друг вариант на LZ77
• LZW. Модификацията на Уелч
• GIF. Гледната точка на CompuServe
• Оптимални срещу алчни алгоритми
• Компресиране в реално време
• LZW срещу Марков
• Компресиране със загуба
• Изрязване и квантифициране
• JPEG
• Компресиране на видеоизображение. MPEG
• Уейвлети
• Компресиране с фрактали

Безплатно изтегляне на книгата “Програмиране=++Алгоритми;”

Книгата за алгоритми на Преслав и Панайот може да се изтегли безплатно от нейния сайт (programirane.org/download) или да се намери в хартиен вид на книжния пазар.