Заметки
Оглавление:
1. Предисловие
1.1. Об этих заметках
1.2. О лицензии на эти заметки
1.2.1. Дополнительные замечания
1.3. Про задачи
2. Основы программирования на питоне
2.1. Начало работы в Python 3 и Wing IDE 101
2.1.1. О версиях Python
2.1.2. Установка Python
2.1.3. Установка Wing IDE
2.1.4. Проверка установки
2.1.5. Первая программа
2.1.6. Ошибки в программе
2.1.7. Как работает эта программа
2.1.8. Использование питона как калькулятора
2.1.9. Простейший ввод и вывод. Переменные
2.1.10. Присваивания
2.1.11. Комментарии
2.1.12. Язык программирования как конструктор
2.1.13. Примеры решения задач
2.1.14. Что дальше?
2.2. Условный оператор (if)
2.2.1. Базовый синтаксис
2.2.2. Условия
2.2.3. Логические операторы
2.2.4. Тело условного оператора
2.2.5. else и elif
2.2.6. Примеры решения задач
2.3. Циклы
2.3.1. Цикл while
2.3.1.1. Примеры
2.3.2. Цикл for
2.3.3. Про команды break и continue
2.3.3.1. Понятие тела цикла и итерации
2.3.3.2. Команда break
2.3.3.3. Команда continue
2.3.3.4. while True и break
2.3.4. Примеры решения задач
2.4. Массивы
2.4.1. Общее представление о массиве
2.4.2. Обход массива
2.4.3. Операции на массиве
2.4.4. Ввод-вывод массива
2.4.5. Двумерные массивы
2.4.6. Операции над двумерным массивом
2.4.7. Обход двумерного массива
2.4.8. Создание двумерного массива
2.4.9. Ввод-вывод двумерного массива
2.4.10. Многомерные массивы
2.4.11. Примеры решения задач
2.5. Символы и строки
2.5.1. Символьный тип данных
2.5.2. Коды символов
2.5.3. Сравнения символов
2.5.4. Массивы и циклы
2.5.5. Строки
2.5.6. int и т.п.
2.5.7. Другие операции
2.5.8. Примеры решения задач
2.6. Вещественные числа
2.6.1. Запись чисел с плавающей точкой
2.6.2. Как компьютер хранит вещественные числа
2.6.3. Типы данных
2.6.4. Про «значащие цифры»
2.6.5. Про дырки между числами
2.6.6. Базовые операции
2.6.7. Про вывод подробнее
2.6.8. Полезные функции
2.6.9. Погрешности
2.6.9.1. Два правила работы с вещественными числами
2.6.9.2. Необходимость использования
eps
2.6.9.3. Выбор
eps
2.6.10. Дополнительный материал. «Грубые» задачи: когда
eps
не нужно
2.6.11. Примеры решения задач
2.7. Функции
2.7.1. Общее представление
2.7.2. Как объявлять функции
2.7.3. Аргументы функции
2.7.4. Локальные переменные
2.7.5. Возвращаемое значение
2.7.6. Зачем нужны функции
2.8. Работа с файлами
2.8.1. Ввод данных
2.8.1.1. Чтение по аналогии с input
2.8.1.2. Чтение до конца файла
2.8.2. Вывод
2.8.3. Как это использовать в олимпиадах
2.9. Дополнительные типы данных и прочие замечания
2.9.1. int
2.9.2. bool
2.9.3. Кортежи, они же tuple
2.9.4. Массивы и цикл
for
2.9.5. Словари
3. Основы программирования на C++
3.1. Общая информация про язык C++
3.1.1. Про языки С и C++
3.1.2. Статическая типизация и компилируемость
3.1.2.1. Компилируемость
3.1.2.2. Статическая типизация
3.1.3. Стандарты и компиляторы
3.2. Среды разработки (IDE)
3.2.1. Code::Blocks
3.2.2. Microsoft Visual Studio
3.2.3. Параметры компиляции и компиляция из командной строки
3.3. Синтаксис C++
3.3.1. Простейшая программа
3.3.2. Основные принципы синтаксиса
3.3.3. Целочисленные типы данных и переполнения
3.3.4. Арифметические операции
3.3.5. Присваивания, auto и ++
3.3.6. Ввод-вывод
3.3.7. Условный оператор (if) и логические операции
3.3.8. Циклы
3.3.9. Массивы
3.3.10. Символы и строки
3.3.11. Вещественные числа
3.3.12. Логический тип данных
3.3.13. Функции
3.3.14. Файловый ввод-вывод
3.4. Дополнительные замечания
3.4.1. Быстрый ввод-вывод
3.4.2. Установка стека
3.4.3. Порядок вычислений
3.4.4. Undefined behavior
4. Тестирование программ
4.1. Стратегия тестирования
4.2. Какие тесты надо использовать
4.2.1. Минимальные тесты
4.2.2. Простые маленькие тесты
4.2.3. Тест из условия
4.2.4. Разные тесты
4.2.5. «Подлые» тесты
4.2.6. Пороговые тесты
4.2.7. Крайние случаи
4.2.8. Частные случаи
4.2.9. Максимальные тесты
4.2.10. Максимальные тесты для вещественных чисел
4.2.11. Все возможные тесты
4.3. Дополнительные комментарии по процессу тестирования
4.3.1. Тестируйте даже идею!
4.3.2. Знайте ответ на тест заранее
4.3.3. Вспомните условие задачи
4.3.4. Разнообразие тестов
4.3.5. Ориентируйтесь не на формальность условия, а на смысл
4.3.6. «Белый ящик» и «чёрный ящик»
4.3.7. Не теряйте тесты
4.3.8. Мультитест
4.3.9. Использование команды
assert
4.4. Пример: задача сортировки массива
4.5. Стресс-тестирование
4.5.1. Общие принципы
4.5.2. Организация стресс-тестирования
4.5.3. Стратегия стресс-тестирования
4.5.4. Что должен из себя представлять чекер?
4.5.5. Стресс-тестирование без тупого решения и/или без чекера
4.5.6. Стресс-тестирование с заранее известным ответом
4.6. Отладка программы
4.6.1. Что делать, если вы нашли тест, на котором ваша программа не работает?
4.6.2. Про тест из условия
4.6.3. Как отлаживать программу, когда тест уже известен
4.6.4. Что делать, когда вы уже нашли ошибку в коде
4.7. Дополнительные замечания
4.7.1. Думайте во время написания кода
4.7.2. Упрощайте код
4.7.3. Не исправляйте код, если не нашли тест
4.7.4. Проверяйте типы и границы массивов
4.7.5. Перечитывайте задачу
4.7.6. Перечитывайте программу
4.8. Переполнение массивов в C++: Valgrind и AddressSanitizer
4.8.1. Valgrind
4.8.2. AddressSanitizer
4.8.3. Общие замечания
5. Сложность алгоритмов
5.1. Простейшие основы
5.2. Формальные определения
5.2.1. Пример 1: сложность алгоритма Флойда
5.2.2.
\(O\)
-обозначение
5.2.3.
\(O\)
-обозначение для оценки сложности алгоритмов
5.2.4. Еще немного про обозначение
5.2.5. Примеры
5.2.6. Последовательность сложностей
5.3. Дополнительные замечания
5.3.1. Сложность переборных решений
5.3.2. Про QSort подробнее
5.3.3. О константе
5.3.4. Сложные случаи
5.4. Классы
\(P\)
и
\(NP\)
.
\(NP\)
-полнота
5.4.1. Естественный параметр теста
5.4.2. Полиномиальные алгоритмы и класс сложности
\(P\)
5.4.3. Сводимость задач
5.4.4. Задачи, рассматриваемые в теории про
\(NP\)
5.4.5. Класс
\(NP\)
5.4.6. Примеры
\(NP\)
-задач
5.4.7. Пример не-
\(NP\)
-задачи
5.4.8.
\(NP\)
-полнота
5.4.9. Проблема
\(P=NP\)
и вообще зачем все это нужно
5.4.10.
\(NP\)
-трудные задачи
5.4.11. Дополнительные замечания
5.4.12. Перечень задач
5.4.13. Все задачи
5.4.14. Подсказки к задачам
6. Различные около-программистские идеи и замечания
6.1. Кодировки и работа с ними
6.1.1. Собственно кодировки
6.1.2. Работа с кодировками в языках программирования
6.1.2.1. Классические языки
6.1.2.2. Юникодные языки
6.1.3. Использование кодировок в олимпиадах
6.1.4. Что такое «символ»?
6.2. Ключи компилятора
6.3. Битовые операции
6.4. Время выполнения различных элементарных операций
6.5. Изменение тестов
6.6. Быстрое возведение в степень и умножение
6.7. Префиксные суммы и смежные темы
6.7.1. Основное
6.7.2. Нулевые элементы
6.7.3. Суффиксные суммы
6.7.4. Префиксные/суффискные максимумы
6.7.5. Двумерные префиксные суммы
6.8. НОД без деления
6.9. Работа с массивом без инициализации
6.10. Поиск зацикливания в последовательности
6.11. О названиях переменных, отступах и т.д.
6.12. Все задачи
7. Перебор с возвратом
7.1. Элементарные примеры
7.1.1. Перебор всех
\(2^k\)
двоичных чисел из
\(k\)
разрядов
7.1.2. Почему это работает?
7.1.3. Дерево решений
7.1.4. О процедуре
\(check\)
7.1.5. Общая идеология поиска
7.1.6. Перебор всех
\(k\)
-значных чисел в
\(n\)
-ичной системе счисления
7.1.7. Разложение числа
\(N\)
в степени двойки
7.1.8. Перебор всех сочетаний из
\(n\)
по
\(k\)
(т.е. всех
\(C_n^k\)
)
7.1.9. Перебор всех
\(n!\)
перестановок из
\(n\)
чисел (от
\(0\)
до
\(n-1\)
)
7.1.9.1. Откат состояния
7.1.10. Совсем общая концепция перебора
7.1.11. Дополнительные задачи
7.2. Отсечения
7.2.1. Разложение числа
\(N\)
в сумму
\(k\)
степеней двойки
7.2.2. Виды отсечений
7.2.3. Пример на отсечения при подсчёте количества объектов
7.2.4. Отсечения в задачах на оптимизацию
7.3. Эвристики
7.3.1. Эвристики до перебора
7.3.2. Эвристики во время перебора
7.3.3. Локальная оптимизация
7.4. Дополнительные идеи
7.4.1. Отсечение по времени
7.4.2. Перебор двумерного массива
7.4.3. Вариации порядка выбора элементов
7.5. Все задачи
7.6. Подсказки к задачам
7.7. Ответы на задачи
8. Поиск в глубину
8.1. Элементарная реализация и общие замечания
8.1.1. Реализация
8.1.2. Как вызывать процедуру
\(find\)
8.1.3. Пример работы
8.1.4. Дерево поиска в глубину
8.1.5. Оценка сложности
8.1.6. Дополнительные замечания
8.2. Простые задачи, решаемые поиском в глубину
8.2.1. Компоненты связности графа
8.2.2. Проверка графа на двудольность
8.2.3. Проверка, является ли граф деревом
8.2.4. Нахождение эйлерова пути и цикла
8.3. Поиск в глубину для ориентированных графов: топологическая сортировка и смежные вопросы
8.3.1. Топологическая сортировка
8.3.2. Проверка графа на ацикличность
8.3.3. Компоненты сильной связности
8.3.4. Конденсация графа
8.3.5. Времена входа и выхода
8.4. Мосты и точки сочленения
8.4.1. Перекрёстные ребра
8.4.2. Поиск точек сочленения
8.4.3. Поиск мостов
8.5. Все задачи
8.6. Подсказки к задачам
8.7. Ответы на задачи
9. Динамическое программирование
9.1. Элементарные примеры
9.1.1. Задачи про черепашку
9.1.2. Последовательности из нулей и единиц без двух единиц подряд
9.1.3. Задача о наборе данной суммы данным набором монет
9.2. Фундаментальные основы ДП
9.2.1. Общий алгоритм решения задач на ДП
9.2.2. Принцип перекрытия подзадач как причина быстрой работы ДП
9.2.3. Принцип оптимальности для подзадач
9.2.4. Дополнительные замечания
9.2.4.1. Введение нулевых элементов
9.2.4.2. Хранение только последних строк таблицы
9.3. Восстановление решения в задачах на ДП
9.3.1. Примеры вывода решения
9.3.2. Общая концепция написания процедуры
\(out\)
9.3.3. Вывод лексикографически первого решения
9.3.4. Пример с массивом
\(from\)
: задача про наибольшую возрастающую подпоследовательность
9.3.5. Пример на нетривиальную процедуру
\(out\)
: алгоритм Флойда с сохранением промежуточной вершины
9.4. Определение объекта по номеру и номера по объекту
9.4.1. Вывод
\(k\)
-ого объекта
9.4.2. Определение номера по объекту
9.4.3. Нахождение следующего или предыдущего объекта
9.4.4. Перебор всех решений
9.5. Способы написания ДП
9.5.1. ДП с просмотром назад
9.5.2. ДП с просмотром вперёд
9.5.3. Рекурсия с запоминанием результата
9.6. Виды задач на ДП
9.6.1. Линейное ДП
9.6.2. Многомерное ДП
9.6.3. ДП на подотрезках
9.6.4. ДП по полной сумме
9.6.5. ДП на ациклических графах
9.6.6. ДП на деревьях
9.6.7. Игры
9.6.8. ДП на подмножествах
9.6.9. ДП по профилю
9.6.10. Динамика по изломанному профилю
9.7. Дополнительные задачи
9.8. Все задачи
9.9. Подсказки к задачам
9.10. Ответы на задачи
10. Бинарный поиск
10.1. Вещественный двоичный поиск
10.1.1. Прочность нити на разрыв
10.1.2. Общая идея
10.1.3. Поиск корня функции
10.1.4. А если функция не монотонна или не непрерывна?
10.1.5. Что выводить?
10.1.6. Решение без
\(\varepsilon\)
10.1.7. Выбор
\(l\)
и
\(r\)
10.2. Целочисленный двоичный поиск
10.2.1. Опять порог разрыва нити
10.2.2. Риск зацикливания
10.2.3. Общий случай
10.2.4. Что же является ответом?
10.3. Поиск элемента в отсортированном массиве
10.3.1. Постановка задачи
10.3.2. А что является тут ответом?
10.3.3. Левый и правый двоичные поиски
10.3.4. Бинарный поиск как поиск места вставки
10.3.5. Ошибки в целочисленном бинарном поиске
10.4. Деление пополам по ответу
10.4.1. Деление пополам по ответу и инвертирование задачи
algoprog.ru
Заметки
»
8. Поиск в глубину
GitHub
8. Поиск в глубину
¶
Оглавление:
8.1. Элементарная реализация и общие замечания
8.1.1. Реализация
8.1.2. Как вызывать процедуру
\(find\)
8.1.3. Пример работы
8.1.4. Дерево поиска в глубину
8.1.5. Оценка сложности
8.1.6. Дополнительные замечания
8.2. Простые задачи, решаемые поиском в глубину
8.2.1. Компоненты связности графа
8.2.2. Проверка графа на двудольность
8.2.3. Проверка, является ли граф деревом
8.2.4. Нахождение эйлерова пути и цикла
8.3. Поиск в глубину для ориентированных графов: топологическая сортировка и смежные вопросы
8.3.1. Топологическая сортировка
8.3.2. Проверка графа на ацикличность
8.3.3. Компоненты сильной связности
8.3.4. Конденсация графа
8.3.5. Времена входа и выхода
8.4. Мосты и точки сочленения
8.4.1. Перекрёстные ребра
8.4.2. Поиск точек сочленения
8.4.3. Поиск мостов
8.5. Все задачи
8.6. Подсказки к задачам
8.7. Ответы на задачи