Програмиране = ++Алгоритми Преслав Наков → Обява 26883665

1968736
Програмиране = ++Алгоритми
Преслав Наков, Панайот Добриков

Книгата би могла да се ползва като продължение на книгите ”Въведение в програмирането със 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
Уейвлети
Компресиране с фрактали