Заметки

Оглавление:

  • 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. Ответы на задачи
Next Previous

© Петр Калинин, 2008-н.в., GNU GPL

algoprog.ru — мой курс по алгоритмическому программированию

Built with Sphinx using a theme provided by Read the Docs.