Задача о рюкзаке

Комбинаторная оптимизационная задача, которая заключается в выборе подмножества предметов с определенными весами и стоимостями для помещения их в рюкзак с ограниченной вместимостью.

Алгоритм:
1. Создаем двумерный массив размером
2. Заполняем первую строку массива нулями.
3. Для каждого предмета, начиная с первого и до n-го, проходим по всем возможным вместимостям рюкзака от 0 до W:
- Если текущий предмет можно положить в рюкзак, то выбираем максимальное значение между суммой стоимости текущего предмета и стоимостью предметов, которые можно положить в рюкзак с ограниченной вместимостью.
- Если текущий предмет нельзя положить в рюкзак, то значение остается таким же, как и в предыдущей ячейке массива.
4. Значение в последней ячейке массива будет являться оптимальной стоимостью предметов в рюкзаке.
5. Чтобы восстановить решение, начиная с последней ячейки, проверяем, было ли значение обновлено.

Сложность: O(nW), где n - число предметов, а W - вместимость рюкзака.

Код Хаффмана

Метод без потерь для сжатия данных, который использует переменную длину кодирования. Он был разработан Дэвидом Хаффманом в 1952 году.

Алгоритм:
1. Создаем таблицу частот символов в исходном наборе данных.
2. Создаем листы дерева для каждого символа на основе их частоты, присваивая символам коды длиной 1.
3. Повторяем следующие шаги до тех пор, пока не будет создано дерево:
а. Выбираем два узла с наименьшей частотой и создаем новый узел-родитель.
б. Присваиваем новому узлу суммарную частоту своих потомков.
в. Дополняем левому потомку кодом "0" и правому потомку кодом "1".
4. Повторяем шаг 3 до тех пор, пока все узлы не будут объединены в один корневой узел.

Алгоритм выполняет сортировку и слияние символов, что требует O(n log n) операций. Однако, само кодирование и декодирование имеют сложность O(n) (n - размер исходной строки).

Эластичная чистая регрессия

Elastic Net — метод линейной регрессии, который сочетает преимущества двух регуляризаций: Лассо (L1) и Риджа (L2). Он помогает справиться с задачей отбора признаков и предотвращает переобучение, особенно когда данные содержат много коррелирующих признаков.

Эластичная сеть использует комбинацию штрафов:
L1-регуляризация (Лассо): способствует разреженности признаков (некоторые коэффициенты становятся нулевыми).
L2-регуляризация (Ридж): снижает величину коэффициентов, предотвращая переобучение.

Когда использовать эластичную чистую регрессию?
- Данные содержат множество признаков, часть из которых сильно коррелирует.
- Требуется и отбор признаков (как у Лассо), и уменьшение коэффициентов (как у Риджа).
- Простая линейная регрессия приводит к переобучению.

Градиентная повышающая регрессия

Gradient Boosting — это метод ансамблевого обучения, который объединяет несколько слабых моделей (обычно деревьев решений), чтобы получить мощную и точную модель. Идея заключается в том, чтобы каждое следующее дерево исправляло ошибки предыдущего.

Работа градиентного бустинга:
1) Инициализация: Создаем первое дерево, которое пытается предсказать целевое значение.
2) Оценка ошибки: Вычисляем разницу между фактическими значениями и предсказанными — это наши остатки.
3) Обучение следующего дерева: Строим следующее дерево на основе ошибок предыдущего, чтобы минимизировать остатки.
4) Комбинирование моделей: Итоговое предсказание — это сумма предсказаний всех деревьев с учетом их весов.

Каждое новое дерево учится на градиенте ошибки предыдущего, отсюда и название — градиентный бустинг.

Наивная байесовская классификация

Алгоритм машинного обучения, который основан на теореме Байеса. Он называется «наивным» потому, что предполагает независимость всех признаков друг от друга — даже если на практике это не всегда так. Несмотря на такое упрощение, алгоритм показывает отличные результаты в задачах классификации текста и фильтрации спама.

Основная идея — вычислить вероятность того, что объект принадлежит определенному классу, учитывая его признаки. Для этого используется формула Байеса.

Алгоритм наивного Байеса оценивает вероятность для каждого класса и выбирает тот, у которого вероятность выше.

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

Кластеризация k-средних — Группировка по схожести

Алгоритм k-средних (k-Means) — метод кластеризации без учителя, который делит набор данных на заранее заданное количество кластеров (k). Точки данных группируются вокруг центров кластеров на основе их схожести.

Цель алгоритма — минимизировать сумму квадратов расстояний от каждой точки до ближайшего центра кластера. Проще говоря, он старается сделать кластеры как можно более плотными и четко отделенными друг от друга.

Алгоритм выполняется в несколько шагов:
1) Инициализация центров кластеров: случайным образом выбираются k точек данных в качестве начальных центров.
2) Назначение точек: каждая точка данных привязывается к ближайшему центру на основе расстояния (обычно евклидового).
3) Обновление центров: вычисляются новые центры кластеров как среднее всех точек в каждом кластере.
4) Повтор: процесс назначения и обновления продолжается до тех пор, пока центры не перестанут меняться или не достигнется максимальное количество итераций.

DBSCAN — Кластеризация на основе плотности

Density-Based Spatial Clustering of Applications with Noise — алгоритм кластеризации, объединяющий точки данных в группы на основе их плотности. Если точки находятся близко друг к другу, они считаются частью одного кластера. Если точка сильно удалена от других, она считается выбросом (шумом).

Как работает DBSCAN
DBSCAN не опирается на сложные математические формулы — он использует два основных параметра:
Эпсилон (ε) — это радиус вокруг точки, в пределах которого алгоритм ищет ближайших соседей. Этот радиус называют "окрестностью".
Минимум точек (minPts) — минимальное количество точек в пределах радиуса ε, чтобы считать точку "основной".

Алгоритм выделяет три типа точек:
1) Основные точки — точки, вокруг которых находится не меньше minPts соседей в пределах радиуса ε. Они формируют "ядро" кластера.
2) Пограничные точки — точки, которые сами по себе не образуют кластер (меньше minPts соседей), но лежат в окрестности основной точки. Они как бы "пристегнуты" к кластеру.
3) Точки шума — точки, которые не принадлежат ни к одному кластеру и не попадают в окрестность основных точек. Это выбросы, которые игнорируются при построении кластеров.

Поиск самой длинной общей подпоследовательности (Longest Common Subsequence)

Используется для нахождения наибольшей общей подпоследовательности между двумя строками или последовательностями.

Алгоритм:

1. Создание таблицы. Создаем таблицу размером (n+1) на (m+1), где n и m - длины строк или последовательностей.

2. Итеративно проходимся по каждой ячейке таблицы слева направо и сверху вниз, сравнивая символы текущей позиции.
-Если символы совпадают, увеличиваем значение ячейки на 1 и переходим диагонально влево-вверх.
-Если символы не совпадают, выбираем максимальное значение из ячейки слева и сверху и записываем его в текущую ячейку.

3. Восстановление подпоследовательности. Начинаем с нижней правой ячейки таблицы и движемся влево или вверх, выбирая ячейки с максимальным значением. Если значения ячеек совпадают, добавляем символ к подпоследовательности и двигаемся диагонально влево-вверх. Повторяем этот процесс до тех пор, пока не достигнем левой верхней ячейки таблицы.

Сложность: O(n*m)

Поиск Фибоначчи

Метод, основанный на сравнении, который использует числа Фибоначчи для поиска элемента в отсортированном массиве.

Последовательность Фибоначчи начинается с чисел 0 и 1, а каждое следующее число равно сумме двух предыдущих чисел. Вот первые несколько чисел последовательности: 0, 1, 1, 2, 3, 5, 8, 13 и т.д.

Сложность: O(log n)

Судоку

Алгоритм:
1. Создайте функцию, которая проверяет, действительна ли данная матрица судоку или нет. Сохраните Hashmap для строки, столбца и полей. Если какое-либо число имеет частоту больше 1 в hashMap, верните false, иначе верните true;
2. Создайте рекурсивную функцию, которая принимает сетку и текущий индекс строки и столбца.
3. Проверьте базовые случаи:
⁃ Если индекс находится в конце матрицы, т.е. i=N-1 и j=N, тогда проверьте, безопасна ли сетка или нет, если безопасно, распечатайте сетку и верните true, иначе верните false.
⁃ Другой базовый случай — когда значение столбца равно N, т. е. j = N, затем происходит переход к следующей строке, т. е. i++ и j = 0.
4. Если текущий индекс не присвоен, то заполняем элемент от 1 до 9 и повторяем для всех 9 случаев индекс следующего элемента, т.е. i, j+1. если рекурсивный вызов возвращает true, разорвите цикл и верните true.
5. Если присвоен текущий индекс, вызовите рекурсивную функцию с индексом следующего элемента, т. е. i, j+1.

Сложность: O(9^(n*n)

Проверка строки-палиндрома

Строка называется палиндромом, если обратная сторона строки совпадает с ней. Например, «abba» является палиндромом, потому что обратная сторона «abba» будет равна «abba».

Алгоритм:
1. Инициализируйте две переменные: l с начала и h с конца данной строки.
2. Теперь мы сравним символы с индексами l и h друг с другом.
3. Если символы не равны, строка не является палиндромом.
4. Если символы равны, мы увеличим l и уменьшим h.
5. Шаги 2,3 и 4 будут повторяться до тех пор, пока (l < h) или мы не обнаружим неравные символы.
6. Если мы достигнем условия ( l < h ), это означает, что все соответствующие символы равны и строка является палиндромом.

Сложность: O(n)

Самая длинная палиндромная подпоследовательность (Longest Palindromic Subsequence)

LPS — это самая длинная последовательность символов, которая является палиндромом.

Алгоритм поиска LPS:
1. Создаем матрицу dp размером n x n, где n - длина исходной строки.
2. Заполняем главную диагональ матрицы значениями 1, так как каждый символ сам по себе является палиндромом длины 1.
3. Перебираем подпоследовательности строки разной длины и заполняем матрицу dp с помощью следующих правил:
- Если символы на текущих позициях равны, увеличиваем значение dpij на 2 и переходим к следующим символам (i+1, j-1).
- Если символы не равны, выбираем максимальное значение из dpi+1j и dpij-1 и записываем его в dpij.
4. Возвращаем значение dp0n-1, которое представляет длину самой длинной палиндромной подпоследовательности.

Сложность: O(n^2), где n - длина исходной строки.

Ханойская башня

Головоломка, состоящая из трех стержней и набора дисков разного размера. Изначально диски располагаются на одном стержне в порядке убывания размера (больший диск находится ниже меньшего).
1. За один раз можно переместить только один диск.
2. Нельзя помещать больший диск на меньший.

Алгоритм:
1. Если на исходном стержне есть только один диск, переместите его на целевой стержень.
2. Если на исходном стержне есть больше одного диска, выполните следующие шаги:
- Переместите все диски, кроме самого большого, с исходного стержня на вспомогательный стержень.
- Переместите самый большой диск с исходного стержня на целевой стержень.
- Переместите все оставшиеся диски с вспомогательного стержня на целевой стержень.

Алгоритм: O(2^n), где n - количество дисков.

Алгоритмы замены страниц в операционных системах (FIFO)

Цель алгоритма: уменьшение количества ошибок страниц.

Ошибка страницы возникает, когда работающая программа обращается к странице памяти, которая отображается в виртуальное адресное пространство, но не загружена в физическую память. Поскольку фактическая физическая память намного меньше виртуальной, возникают страничные ошибки. В случае ошибки страницы операционной системе, возможно, придется заменить одну из существующих страниц новой необходимой страницей.

FIFO это простейший алгоритм замены страниц. В этом алгоритме операционная система отслеживает все страницы в памяти в очереди, самая старая страница находится в начале очереди. Когда страницу необходимо заменить, страница в начале очереди выбирается для удаления.

Сложность: O(n), где n — количество страниц.

Алгоритм оптимальной замены страниц

Цель алгоритма: уменьшение количества ошибок страниц. В этом алгоритме заменяются страницы, которые не будут использоваться в течение длительного времени в будущем.

Идея проста: для каждой ссылки мы делаем:
⁃ Если указанная страница уже существует, увеличьте количество обращений.
⁃ Если нет, найдите страницу, на которую никогда не будут ссылаться в будущем. Если такая страница существует, замените ее новой страницей. Если такой страницы не существует, найдите страницу, на которую в будущем будут чаще всего ссылаться. Замените эту страницу новой страницей.

Оптимальная замена страниц идеальна, но на практике невозможна, поскольку операционная система не может знать будущие запросы. Использование замены оптимальной страницы предназначено для установки эталона, позволяющего анализировать другие алгоритмы замены.

Сложность: O(n × f), где n — количество страниц, а f — количество кадров.

Least Recently Used алгоритм замены страниц

Наименее недавно использованный (LRU) — это алгоритм замены кэша, который заменяет кэш, когда пространство заполнено. Играет решающую роль, поскольку его можно использовать в качестве алгоритма замены страниц, чтобы минимизировать их ошибки.

Ошибка страницы возникает, когда работающая программа обращается к странице памяти, которая отображается в виртуальное адресное пространство, но не загружена в физическую память. Поскольку фактическая физическая память намного меньше виртуальной, возникают страничные ошибки. В случае ошибки страницы операционной системе, возможно, придется заменить одну из существующих страниц новой необходимой страницей.

Most Recently Used алгоритм замены страниц

Используется в качестве алгоритма замены страниц, чтобы минимизировать их ошибки.

MRU работает лучше всего среди всех алгоритмов замены страниц для особого типа последовательности запросов ссылок на страницы, когда одна и та же последовательность одних и тех же ссылок на страницы повторяется (в цикле).

Матрица

Двумерная структура данных, состоящая из набора элементов, расположенных в строках и столбцах.

Каждый элемент матрицы идентифицируется индексами строки и столбца.

Преимущества:
⁃ Матрицы обеспечивают краткий и эффективный способ представления структурированных данных, особенно когда важны отношения между элементами.
⁃ Матрицы являются фундаментальными в линейной алгебре и используются в различных математических операциях.
⁃ При обработке изображений матрицы используются для представления значений пикселей, что позволяет выполнять преобразования и манипуляции.

Поворот элементов матрицы

Идея состоит в том, чтобы поочередно вращать все кольца элементов, начиная с самого дальнего.

Чтобы повернуть кольцо, нам нужно сделать следующее.
1. Переместить элементы верхнего ряда.
2. Переместить элементы последнего столбца.
3. Переместить элементы нижнего ряда.
4. Переместите элементы первого столбца.

Повторить вышеуказанные шаги для внутреннего кольца, пока оно есть.

Сложность: O(m*n), где m — количество строк, а n — количество столбцов.

Как узнать, является ли число степенью 2?

Чтобы определить, является ли число степенью 2, можно использовать следующий метод:

Проверьте, равно ли число 0. Если да, то 0 не является степенью 2.
Проверьте, является ли число положительным.
Если число положительное, используйте битовую операцию AND с числом (n - 1), где n - это число, которое вы проверяете.
Если результат операции AND равен 0, то число n является степенью 2.

Этот метод основан на том факте, что числа, являющиеся степенями 2, имеют только один бит, установленный в 1 в двоичном представлении (например, 2^3 = 8 в двоичном виде 1000, 2^4 = 16 в двоичном виде 10000). При вычитании единицы из таких чисел, все биты после первого устанавливаются в 1. Таким образом, если вы примените операцию AND к числу и его предшественнику, результат будет равен 0 только в том случае, если число является степенью 2.