Тренировки по алгоритмам 3.0. Лекция 1: «Стеки»

• Михаил Густокашин представляет первую лекцию по тренировкам 3.0.  

• Курс включает лекции, задачи с автоматической проверкой и бонусы для участников.  

• В чате Telegram есть бот для помощи в решении задач.  

• Стек — это структура данных, где элемент добавляется последним и удаляется первым.  

• Стек поддерживает операции push и pop.  

• В простейшем виде стек поддерживает только эти две операции.  

• Стек можно реализовать с помощью динамически расширяемого массива или двусвязного списка.  

• В Python используется список для реализации стека.  

• Односвязный список также подходит для реализации стека.  

• Стек используется для проверки правильности скобочной последовательности.  

• Правильная скобочная последовательность определяется как пустая последовательность или окруженная круглыми скобками.  

• Проверка правильности скобочной последовательности осуществляется подсчетом баланса открывающих и закрывающих скобок.  

• Баланс должен быть неотрицательным и равным нулю в конце.  

• Примеры показывают, как баланс изменяется при обработке скобок.  

• Проверка правильности скобочной последовательности важна для редакторов кода.  

• Пример с неправильным балансом скобок.  

• Идея подсчета баланса для разных видов скобок не работает.  

• Пример с перемешанными круглыми и квадратными скобками.  

• Стек помогает решить задачу с несколькими видами скобок.  

• Проверка стека перед извлечением элемента.  

• Пример правильной скобочной последовательности и состояния стека.  

• Проверка корректности HTML-кода с помощью стека.  

• Пример с тегами и их валидацией.  

• Стек помогает избежать ошибок в HTML-коде.  

• Пример с выражением и его правильным вычислением.  

• Порядок действий в арифметических выражениях.  

• Правила вычисления выражений с вложенными скобками.  

• Инфиксная и префиксная записи арифметических выражений.  

• Постфиксная запись и её преимущества.  

• Пример вычисления постфиксного выражения с помощью стека.  

• Пример: 4 * 5 + 21 * 3 + 2.  

• Использование стека для хранения операндов и операций.  

• Выполнение операций в порядке приоритета.  

• Операнды сразу попадают в ответ.  

• Операции выталкивают операнды с большим приоритетом.  

• Скобки обрабатываются особым образом.  

• Преобразование выражения 6 + 3 * 2 * 2.  

• Операнды и операции обрабатываются посимвольно.  

• Скобки и операции выталкиваются в соответствии с приоритетом.  

• Преобразование инфиксной записи в постфиксную.  

• Использование стека для хранения операций.  

• Подсчет результата постфиксной записи.  

• Унарные минусы и плюсы в инфиксной записи.  

• Способы борьбы с унарными операциями.  

• Проверка корректности инфиксной записи.  

• Операции в стеке всегда располагаются в порядке возрастания приоритетов.  

• Невозможно, чтобы в стеке лежали два знака умножения подряд.  

• В реальных языках программирования около двадцати приоритетов операций.  

• Накапливать числа в отдельной переменной или списке.  

• Преобразование инфиксной записи в постфиксную возможно, но сложно.  

• Унарные операции, такие как косинус и синус, имеют приоритет и могут быть встроены в выражение.  

• Для каждого элемента найти ближайший меньший элемент справа или слева.  

• Решение задачи требует перебора всех элементов правее текущего.  

• Использование стека для хранения пар значений и индексов.  

• Стек хранит пары значений и индексов для элементов, для которых еще не найден ответ.  

• При поступлении нового элемента, он выталкивает из стека все элементы с большим значением.  

• Стек всегда содержит возрастающую последовательность элементов.  

• Пример с числами 7, 2, 4, 5, 3, 2, 5, 1, 5, 4.  

• Для каждого элемента находится ближайший меньший элемент справа.  

• Если для элемента нет меньшего элемента справа, записывается длина массива.  

• Сложность алгоритма составляет O(n) из-за прохода по массиву.  

• Внутри цикла происходит множество сложных операций, но все они укладываются в O(1).  

• Стек не всегда удаляет все элементы при выталкивании.  

• Элементы удаляются до тех пор, пока не встретится элемент, который нужно оставить.  

• В стеке всегда хранится неубывающая последовательность.  

• Можно узнать ближайший меньший элемент слева и справа.  

• Полезно для решения задач, особенно в спортивном программировании.  

• Студенты творчески применили эту идею для решения задач.  

• Функции можно разделить на код и состояние.  

• При вызове функции выделяется память в стеке для локальных переменных и параметров.  

• После завершения функции память очищается, и управление передается обратно.  

• Рекурсивная функция считает факториал.  

• При вызове функции выделяется место в стеке для локальных переменных.  

• Управление передается обратно по точке возврата.  

• При рекурсивном вызове выделяется память для локальных переменных.  

• Управление возвращается в ту же строку, откуда был вызван.  

• Важно, чтобы функция заканчивалась корректно, иначе произойдет переполнение стека.  

• При передаче сложных объектов в качестве параметров, хранятся только указатели.  

• Объекты могут храниться в стеке или в куче в зависимости от языка программирования.  

• Важно понимать, как работает стек и куча для обхода рекурсии.  

• Рекурсия может быть ограничена глубиной или системным размером стека.  

• Запуск функции требует выделения памяти и копирования данных, что замедляет процесс.  

• Оптимизация рекурсии вручную может уменьшить константу, но не изменит симптоматику решения.  

• Использование стека для моделирования рекурсии.  

• Создание локальных переменных и выделение памяти из стека.  

• Возвращение из функции требует меток для продолжения выполнения с нужного места.  

• Создание стека для хранения параметров и меток возврата.  

• Использование словарей для хранения локальных переменных.  

• Возвращение функции с нужного места с помощью меток.  

• Каждая функция знает, где она должна продолжить выполнение.  

• Использование глобальной переменной для возврата результатов.  

• Возвращение значений через стек или регистры процессора.  

• Запоминание текущего состояния функции.  

• Добавление параметров в стек для рекурсивного вызова.  

• Моделирование вызова рекурсивной функции через контини.  

• Восстановление локальных переменных из стека.  

• Продолжение выполнения функции с нужного места.  

• Использование меток для возврата к предыдущему состоянию.  

• Стек должен хранить локальные переменные, параметры и метки возврата.  

• Использование меток для понимания текущего состояния функции.  

• Создание нового элемента в стеке для рекурсивного вызова и заполнение его параметров.  

• Обсуждение процесса моделирования работы стека.  

• Сравнение с операционной системой и компилятором.  

• Проблемы и ограничения моделирования.  

• Обсуждение выделения стека для рекурсии.  

• Использование динамически расширяемого массива или односвязного списка.  

• Борьба с переполнением стека в разных языках программирования.  

• Примеры использования стека в реальных задачах.  

• Оптимизация производительности для больших объемов данных.  

• Рекурсия в реальных задачах программирования.  

• Понятие монотонного стека.  

• Возможность переписать рекурсию с использованием циклов.  

• Моделирование работы стека в операционной системе.  

• Обсуждение одинаковых временных ограничений для всех языков программирования.  

• Рекомендации по изучению алгоритмов на родном языке.  

• Различие между стеком и хэштегом.  

• Рекомендации по изучению первых и вторых тренировок.  

• Правила рейтинга участников.  

• Количество задач в каждом дивизионе и завершение лекции.