Заметки по алгоритмическому программированию

Автор: Петр Калинин, 2008—н.в.

Этот документ можно распространять по лицензии GNU General Public License версии 3 или более поздней. Последнюю версию документа, а также исходный код в формате restructuredtext можно скачать с https://github.com/petr-kalinin/progtexts2.

Оглавление:

• 1. Предисловие
  • 1.1. Об этих заметках
  • 1.2. О лицензии на эти заметки
  • 1.3. Про задачи
• 2. Основы программирования на питоне
  • 2.1. Начало работы в Python 3 и Wing IDE 101
  • 2.2. Условный оператор (if)
  • 2.3. Циклы
  • 2.4. Массивы
  • 2.5. Символы и строки
  • 2.6. Вещественные числа
  • 2.7. Функции
  • 2.8. Работа с файлами
  • 2.9. Дополнительные типы данных и прочие замечания
• 3. Основы программирования на C++
  • 3.1. Общая информация про язык C++
  • 3.2. Среды разработки (IDE)
  • 3.3. Синтаксис C++
  • 3.4. Дополнительные замечания
• 4. Тестирование программ
  • 4.1. Стратегия тестирования
  • 4.2. Какие тесты надо использовать
  • 4.3. Дополнительные комментарии по процессу тестирования
  • 4.4. Пример: задача сортировки массива
  • 4.5. Стресс-тестирование
  • 4.6. Отладка программы
  • 4.7. Дополнительные замечания
  • 4.8. Переполнение массивов в C++: Valgrind и AddressSanitizer
• 5. Сложность алгоритмов
  • 5.1. Простейшие основы
  • 5.2. Формальные определения
  • 5.3. Дополнительные замечания
  • 5.4. Классы \(P\) и \(NP\). \(NP\)-полнота
• 6. Различные около-программистские идеи и замечания
  • 6.1. Кодировки и работа с ними
  • 6.2. Ключи компилятора
  • 6.3. Битовые операции
  • 6.4. Время выполнения различных элементарных операций
  • 6.5. Изменение тестов
  • 6.6. Быстрое возведение в степень и умножение
  • 6.7. Префиксные суммы и смежные темы
  • 6.8. НОД без деления
  • 6.9. Работа с массивом без инициализации
  • 6.10. Поиск зацикливания в последовательности
  • 6.11. О названиях переменных, отступах и т.д.
  • 6.12. Все задачи
• 7. Перебор с возвратом
  • 7.1. Элементарные примеры
  • 7.2. Отсечения
  • 7.3. Эвристики
  • 7.4. Дополнительные идеи
  • 7.5. Все задачи
  • 7.6. Подсказки к задачам
  • 7.7. Ответы на задачи
• 8. Поиск в глубину
  • 8.1. Элементарная реализация и общие замечания
  • 8.2. Простые задачи, решаемые поиском в глубину
  • 8.3. Поиск в глубину для ориентированных графов: топологическая сортировка и смежные вопросы
  • 8.4. Мосты и точки сочленения
  • 8.5. Все задачи
  • 8.6. Подсказки к задачам
  • 8.7. Ответы на задачи
• 9. Динамическое программирование
  • 9.1. Элементарные примеры
  • 9.2. Фундаментальные основы ДП
  • 9.3. Восстановление решения в задачах на ДП
  • 9.4. Определение объекта по номеру и номера по объекту
  • 9.5. Способы написания ДП
  • 9.6. Виды задач на ДП
  • 9.7. Дополнительные задачи
  • 9.8. Все задачи
  • 9.9. Подсказки к задачам
  • 9.10. Ответы на задачи
• 10. Бинарный поиск
  • 10.1. Вещественный двоичный поиск
  • 10.2. Целочисленный двоичный поиск
  • 10.3. Поиск элемента в отсортированном массиве
  • 10.4. Деление пополам по ответу