-
Описание
Автор уроков и составитель заданий по программированию и информатике ЗФТШ
Этот преподаватель пока не ведёт курсы.
У этого преподавателя пока нет лекций.
23 августа
Крайтчайший путь на карте 23.08.2023 16:24
Сейчас мы изучим алгоритм Форда-Беллмана, который реализует идеи динамического программированияФормулировкаПусть нам заданы города: $$1, \dots, n$$ и длины путей из одного в другой.Их хранить будем в двумерном массиве $$len[i][j]$$ - длина пути из $$i$...
64 просмотра
23 августа
Мемоизация 23.08.2023 16:10
Рекурсия и ДПКак можно было заметить, ДП напоминает использование рекурсии.Но рекурсия становится неоптимальной, если при дроблении на подзадачи происходят повторные вычисления.Динамическое программирование позволяет избежать этого, сохраняя уже вычисл...
62 просмотра
23 августа
Задача о рюкзаке 23.08.2023 16:03
ФормулировкаЕсть рюкзак, в который можно положить предметов на $$W$$ кг.Также имеется $$n$$ предметов с весами $$w_1, \dots, w_n$$ и полезностью $$u_1, \dots, u_n$$При заданном ограничении рюкзака по весу необходимо взять такие предметы, чтобы их сумма...
59 просмотров
23 августа
Задача о кузнечике 23.08.2023 15:52
ФормулировкаКузнечик прыгает вдоль прямой, изначально находясь в точке 0.Он может прыгать на 1 или на 2 деления вперед.Необходимо найти количество различных способов добраться до цели расположенной в точке $$n$$.РешениеМассив с решениями задач назовем ...
83 просмотра
23 августа
Введение 23.08.2023 15:40
Основная идеяДинамическое программирование (далее ДП) - это прием в разработке алгоритмов,который заключается в дроблении задачи на несколько мелких подзадач,имеющих оптимальное решение.Логику алгоритма, отвечающего динамическому программированию, можн...
54 просмотра
13 августа
Дерево отрезков. Дерево Фенвика 13.08.2023 14:16
Дерево отрезков
Прежде чем говорить о самой структуре данных, рассмотрим некоторые свойства операций. Будем обозначать произвольную операцию (сложение, умножение, взятие остатка или любая операция, что вы можете придумать) символом $$*$$
&nbs...
97 просмотров
13 августа
Хэш таблицы 13.08.2023 14:09
В рамках курса "Алгоритмы 2" мы познакомились с понятием ассоциативного массива и его реализацией с помощью дерева поиска. Но асимптотика всех операций была логарифмическая, сейчас же мы рассмотрим структуру данных, работающую в среднем костантное врем...
72 просмотра
13 августа
Куча. Бинарная куча. Heap sort 13.08.2023 14:04
Общие сведения
Свойство кучи: у дочернего узла значение всегда не больше/не меньше родительского.
Будем называться кучу с минимумом в корне min-кучей, с максимумом - max-кучей
Кучей назовем структуру данных, для которой выпол...
94 просмотра
13 августа
Списки 12.08.2023 21:53
Общая информация
Списком называется последовательность узлов (от англ. node), хранящих некоторые данные и ссылки на предыдущий и/или последующий узлы. Если ссылки только на предыдущий/последующий узлы, то такой список называется односвязным, е...
84 просмотра
11 августа
Массивы 11.08.2023 20:30
Общая информация
Массивом назовем последовательность данных одного типа, к которым можно обращаться по индексу.
Массивы делятся на статические (фиксированного размера) и динамические (можно изменять размер). Также ...
94 просмотра
11 августа
Асимптотический анализ 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)$$
...
71 просмотр
Сообщение отправлено!
Сообщение не отправлено. Проверьте правильность введёных данных.