-
Описание
Автор уроков и составитель заданий по программированию и информатике ЗФТШ
23 августа 2023 г.
Крайтчайший путь на карте 23.08.2023 16:24
Сейчас мы изучим алгоритм Форда-Беллмана, который реализует идеи динамического программированияФормулировкаПусть нам заданы города: $$1, \dots, n$$ и длины путей из одного в другой.Их хранить будем в двумерном массиве $$len[i][j]$$ - длина пути из $$i$...
140 просмотров
23 августа 2023 г.
Мемоизация 23.08.2023 16:10
Рекурсия и ДПКак можно было заметить, ДП напоминает использование рекурсии.Но рекурсия становится неоптимальной, если при дроблении на подзадачи происходят повторные вычисления.Динамическое программирование позволяет избежать этого, сохраняя уже вычисл...
142 просмотра
23 августа 2023 г.
Задача о рюкзаке 23.08.2023 16:03
ФормулировкаЕсть рюкзак, в который можно положить предметов на $$W$$ кг.Также имеется $$n$$ предметов с весами $$w_1, \dots, w_n$$ и полезностью $$u_1, \dots, u_n$$При заданном ограничении рюкзака по весу необходимо взять такие предметы, чтобы их сумма...
139 просмотров
23 августа 2023 г.
Задача о кузнечике 23.08.2023 15:52
ФормулировкаКузнечик прыгает вдоль прямой, изначально находясь в точке 0.Он может прыгать на 1 или на 2 деления вперед.Необходимо найти количество различных способов добраться до цели расположенной в точке $$n$$.РешениеМассив с решениями задач назовем ...
204 просмотра
23 августа 2023 г.
Введение 23.08.2023 15:40
Основная идеяДинамическое программирование (далее ДП) - это прием в разработке алгоритмов,который заключается в дроблении задачи на несколько мелких подзадач,имеющих оптимальное решение.Логику алгоритма, отвечающего динамическому программированию, можн...
132 просмотра
13 августа 2023 г.
Хэш таблицы 13.08.2023 14:09
В рамках курса "Алгоритмы 2" мы познакомились с понятием ассоциативного массива и его реализацией с помощью дерева поиска. Но асимптотика всех операций была логарифмическая, сейчас же мы рассмотрим структуру данных, работающую в среднем костантное врем...
150 просмотров
13 августа 2023 г.
Введение 13.08.2023 13:21
Программа курса
1. Деревья поиска
1. Бинарное ДП. Наивная реализация 2. Сбалансированное ДП. AVL
2. Сортировки
1. Квадратичные сортировки
2. Быстрые сортировки
3. Основа...
57 просмотров
13 августа 2023 г.
Списки 12.08.2023 21:53
Общая информация
Списком называется последовательность узлов (от англ. node), хранящих некоторые данные и ссылки на предыдущий и/или последующий узлы. Если ссылки только на предыдущий/последующий узлы, то такой список называется односвязным, е...
151 просмотр
11 августа 2023 г.
Массивы 11.08.2023 20:30
Общая информация
Массивом назовем последовательность данных одного типа, к которым можно обращаться по индексу.
Массивы делятся на статические (фиксированного размера) и динамические (можно изменять размер). Также ...
188 просмотров
11 августа 2023 г.
Асимптотический анализ 11.08.2023 20:19
Асимтотические классы функций
Нам понадобятся следующие классы функций: $$O$$, $$\Omega$$, $$\Theta$$.
$$O$$
$$f = O(g)$$, если $$\exists C \, \exists N : \forall n \geqslant N \hookrightarrow f(n) \leqslant C \cdot g(n)$$
...
217 просмотров
11 августа 2023 г.
Введение 11.08.2023 20:07
Программа курса
1. Введение в асимптотический анализ
2. Массивы: статические и динамические
3. Списки. Сравнение списков и массиво
4. Стек и очередь. Различные способы реализации
Обозначения в курсе
$$\exists$$ - квантор существ...
79 просмотров
Сообщение отправлено!
Сообщение не отправлено. Проверьте правильность введёных данных.