2020-09-24
143
1. Строки. Описание строковых классов. Шаблонный класс basic_string<>, конкретные строковые типы. Основные операции нал строками. Числовые преобразования. Поддержка итераторов для строк, функции для работы со строковыми итераторами. (Вопрос для самостоятельного изучения по [3, гл. 13]
2. Понятия алгоритма и экземпляра задачи. Корректный алгоритм. Структура данных. NP-полная задача, ее свойства.
3. Асимптотические обозначения. 
-, 
-, 
-, 
- и 
-обозначения. Свойства асимптотических обозначений.
4. Деревья. Определение (свободного) дерева. Теорема о свойствах свободных деревьев (без доказательства). Определения корневого дерева, предков, потомков, поддерева. Степень, глубина, высота корневого дерева. Определение упорядоченного дерева. Определение бинарного дерева и полностью бинарного дерева. Определение позиционно дерева, k-арного дерева и полного k-арного дерева, свойства полного k-арного дерева.
5. Красно-черные деревья. Свойства красно-черных деревьев. Лемма об оценке высоты красно-черного дерева с n внутренними узлами. Повороты.
6. Красно-черные деревья. Вставка и удаление.
Литература
1. Александреску А. Современное проектирование на C++. Серия C++ In-Depth, т. 3.: Пер. с англ. М.: Издательский дом «Вильямс», 2002. 336 с.
2. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений, 3-е изд.: Пер. с англ. М.: ООО «И.Д. Вильямс», 2008. 720 с.
3. Джосаттис Н.М. Стандартная библиотека C++: справочное руководство, 2-е изд.: Пер. с англ. М.: ООО «И.Д. Вильямс», 2014. 1136 с.
4. Кормен Т.Х. Алгоритмы: построение и анализ, 3-е изд.: Пер. с англ. М.: ООО «И.Д. Вильямс», 2013. 1328 с.
5. Мейерс С. Эффективный и современный С++: 42 рекомендации по использованию С++ 11 и С++14: Пер. с англ. М.: ООО «И.Д. Вильямс», 2016. 304. с
6. Павловская Т.А. C/C++. Программирование на языке высокого уровня. СПб.: Питер, 2003. 461 с.
7. Прата С. Язык программирования C++. Лекции и упражнения, 6-е изд.: Пер. с англ. М.: ООО «И.Д. Вильямс», 2012. 1248 с.
8. Страуструп Б. Язык программирования C++. Специальное издание: Пер. с англ. М.: Издательство Бином, 2011. 1136 с.
9. Шилдт Г. Самоучитель C++: Пер. с англ. 3-е изд. СПб.: БХВ-Петербург, 2005. 688 с.
10. Элджер Д. Библиотека программиста. СПб.: Питер, 2003. 320 с.
