Каково стандартное рекуррентное соотношение задачи о рюкзаке 0/1 с целочисленной вместимостью W?

Пусть D[i,w] — наибольшая ценность первых i предметов при вместимости w и положительных целочисленных весах wᵢ. Положим D[0,w]=0. Если wᵢ>w, берём D[i−1,w]; иначе max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). Время O(NW) является псевдополиномиальным.

Чем различаются первичный и внешний ключи в PostgreSQL?

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

Как WAL в PostgreSQL обеспечивает долговечность при обычной синхронной фиксации?

Нужные записи журнала попадают в устойчивое хранилище до подтверждения фиксации и до записи изменённых страниц данных. После сбоя WAL может воспроизвести изменения, отсутствующие на страницах. Асинхронная фиксация допускает потерю недавно подтверждённых транзакций.

Почему динамическое программирование полезно для многих задач оптимизации?

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

Что такое топологический порядок и как алгоритм Кана его находит?

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

Что требуется для двоичного поиска и когда он работает за O(log n)?

Он последовательно делит пополам интервал поиска в данных, отсортированных согласно порядку сравнения. Для массива с доступом по индексу за O(1) и сравнением за постоянное время поиск среди n элементов занимает O(log n).

Когда корректен алгоритм Дейкстры и какова обычная оценка реализации с кучей?

При неотрицательных весах рёбер он последовательно фиксирует вершину с наименьшим предварительным расстоянием. Реализация со списками смежности и двоичной минимальной кучей требует O((V+E) log V). Отрицательные рёбра могут нарушить обоснование окончательности расстояния.

Что означают свойства транзакций ACID?

Атомарность: эффекты целиком или никак. Согласованность: корректные транзакции сохраняют ограничения и инварианты приложения. Изоляция: совместное выполнение подчиняется выбранному уровню изоляции. Долговечность: зафиксированные эффекты переживают сбои, охватываемые настроенными гарантиями базы.

Что такое грязное чтение и какой стандартный уровень изоляции первым его запрещает?

Чтение незафиксированных данных другой транзакции независимо от того, будет ли она затем отменена. READ COMMITTED и более строгие стандартные уровни изоляции запрещают грязное чтение.

Каково рекуррентное соотношение ДП для длины наибольшей общей подпоследовательности (LCS)?

Пусть L[i,j] — длина LCS префиксов длины i,j. Положим L[0,j]=L[i,0]=0. Если последние символы равны, L[i,j]=1+L[i−1,j−1]; иначе L[i,j]=max(L[i−1,j],L[i,j−1]). Полная таблица требует O(mn) времени и памяти.

Что такое фантомное чтение и как оно предотвращается?

Повторение запроса с предикатом обнаруживает другой набор подходящих строк после фиксации изменений другой транзакцией. SERIALIZABLE предотвращает фантомы в стандартной модели; некоторые реализации, включая PostgreSQL REPEATABLE READ, предотвращают их и на более низком уровне.

Каковы две фазы двухфазной блокировки (2PL)?

Рост: блокировки приобретаются без освобождения. Сокращение: освобождаются без приобретения новых. При подходящих конфликтующих блокировках чтения и записи 2PL гарантирует расписания, сериализуемые по конфликтам, но взаимные блокировки всё ещё возможны.

Как алгоритмы Краскала и Прима строят минимальное остовное дерево?

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

Как соотносятся матрица смежности и обычные списки смежности?

Для V вершин и E рёбер матрица требует O(V²) памяти и проверяет наличие ребра за O(1). Списки требуют O(V+E) памяти; поиск ребра (u,v) в неотсортированном списке занимает O(deg(u)), где deg(u) — длина этого списка.

Что требуют первая, вторая и третья нормальные формы?

1НФ: атомарные значения атрибутов. 2НФ: 1НФ и отсутствие зависимости неключевого атрибута от собственного подмножества атрибутов любого кандидатного ключа. 3НФ: 1НФ и в каждой нетривиальной зависимости X→A либо X — суперключ, либо A входит хотя бы в один кандидатный ключ. Неключевой атрибут не входит ни в один кандидатный ключ.

Чем различаются WHERE и HAVING в запросе с группировкой?

WHERE фильтрует входные строки до группировки. HAVING фильтрует полученные группы и может использовать условия с агрегатами, например COUNT(*)>1.

Каков упрощённый логический порядок обработки SQL-запроса SELECT?

Для запроса без CTE, оконных функций и операций над множествами: FROM/JOIN → WHERE → GROUP BY и агрегаты → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. Это логическая модель, не обязательно физический порядок выполнения оптимизатора.

Что делает алгоритм сортировки устойчивым?

Элементы с равными ключами сохраняют исходный взаимный порядок. Сортировка слиянием может быть устойчивой, если при равенстве сначала брать левый элемент; стандартная быстрая сортировка на месте обычно неустойчива. Устойчивость зависит от реализации.

Как алгоритм Беллмана–Форда работает с отрицательными рёбрами и обнаруживает достижимый отрицательный цикл?

Все рёбра релаксируются до V−1 раз. Дальнейшее улучшение через достижимую вершину выявляет отрицательный цикл, достижимый из источника. Худшее время — O(VE); для вершин, достижимых из такого цикла, нет конечной стоимости кратчайшего пути.

Почему быстрая сортировка может работать за Θ(n²) и как помогает рандомизация?

Повторяющиеся крайне неравномерные разбиения, например выбор минимального из различных ключей каждый раз, дают квадратичную работу. При различных ключах или подходящей обработке повторов случайные опорные элементы дают ожидаемое время O(n log n). Медиана трёх — полезная эвристика, а не гарантия для худшего случая.

Как работает стандартная сортировка массива слиянием и каковы её затраты времени и памяти?

Она рекурсивно сортирует две половины и сливает их за линейное время. Стандартный вариант требует Θ(n log n) времени и O(n) дополнительной памяти при сравнении за постоянное время.

Чем различаются кластеризованные и некластеризованные индексы строкового хранения в SQL Server?

Кластеризованный индекс хранит строки таблицы в порядке ключа, поэтому он может быть только один. Некластеризованный индекс содержит собственные ключи и указатели на строки, а также может включать другие столбцы. Термины и детали хранения различаются между СУБД.

Почему B+ деревья полезны для индексов баз данных и диапазонных запросов?

Большое число потомков уменьшает высоту дерева и число обращений к страницам. Упорядоченные ключи и связанные листья поддерживают просмотр диапазона. Хеш-индексы рассчитаны на поиск по равенству и сами по себе не дают такого упорядоченного доступа к диапазонам.

Как работает сортировка вставками и от чего зависит её время на почти отсортированных данных?

Каждый элемент вставляется в отсортированный префикс. Обычный вариант со сдвигами или обменами соседних элементов работает за Θ(n+I), где I — число инверсий. При I=O(n) время линейно; сам по себе малый размер входа не меняет худшую оценку Θ(n²).

Что такое неповторяемое чтение и какой стандартный уровень изоляции его запрещает?

Повторное чтение строки даёт изменённые данные либо строка исчезает после фиксации обновления или удаления другой транзакцией. REPEATABLE READ и SERIALIZABLE запрещают эту аномалию.

Чем жадный алгоритм отличается от динамического программирования?

Жадный алгоритм окончательно выбирает локальный вариант и требует доказательства, что такие выборы сохраняют оптимум. ДП сравнивает альтернативы по рекуррентному соотношению и повторно использует решения подзадач. Глобальный оптимум требует правильной модели и рекуррентного соотношения, а не просто названия «ДП».

Чем различаются INNER JOIN и LEFT JOIN?

INNER JOIN возвращает сочетания строк, удовлетворяющие условию соединения. LEFT JOIN также сохраняет каждую левую строку без совпадения, подставляя NULL в столбцы правой стороны. Несколько совпавших правых строк могут дать несколько результатов для одной левой строки.

Как поиск в глубину обнаруживает цикл в ориентированном графе?

DFS идёт в глубину с помощью рекурсии или явного стека. Ребро к вершине, которая ещё активна на текущем пути DFS, является обратным и доказывает наличие ориентированного цикла; ребра к любой ранее посещённой вершине недостаточно.

Каковы худшие оценки времени и дополнительной памяти пирамидальной сортировки на месте?

Построение кучи требует O(n), а все извлечения — O(n log n). При итеративном просеивании вниз во входном массиве сортировка требует O(n log n) времени в худшем случае и O(1) дополнительной памяти.

Чем различаются мемоизация и динамическое программирование снизу вверх?

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

Когда сортировка подсчётом или поразрядная сортировка могут работать за линейное время?

Сортировка подсчётом требует O(n+k) для n ключей из диапазона k значений. Поразрядная сортировка с d устойчивыми проходами по разрядам и основанием b требует O(d(n+b)). Линейность возможна лишь при подходящих параметрах; алгоритмы используют структуру ключей, а не только сравнения.

Как поиск в ширину находит кратчайшие пути в невзвешенном графе?

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

Алгоритмы, графы, динамическое программирование и реляционные базы данных

32 карточки университетского уровня для повторения сортировок, алгоритмов на графах, динамического программирования, SQL, индексов и транзакций. Предполагаются основы программирования, структур данных и SQL.

Level: basic
Languages: ru → ru
Cards: 32
Markdown: Алгоритмы, графы, динамическое программирование и реляционные базы данных (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	Каково стандартное рекуррентное соотношение задачи о рюкзаке 0/1 с целочисленной вместимостью W?	Пусть D[i,w] — наибольшая ценность первых i предметов при вместимости w и положительных целочисленных весах wᵢ. Положим D[0,w]=0. Если wᵢ>w, берём D[i−1,w]; иначе max(D[i−1,w],vᵢ+D[i−1,w−wᵢ]). Время O(NW) является псевдополиномиальным.
2	Чем различаются первичный и внешний ключи в PostgreSQL?	Первичный ключ идентифицирует строки уникальными значениями без NULL. Внешний ключ требует совпадения с указанными ключевыми значениями с учётом правил NULL. Он может ссылаться на подходящий ключ UNIQUE или первичный ключ в той же или другой таблице.
3	Как WAL в PostgreSQL обеспечивает долговечность при обычной синхронной фиксации?	Нужные записи журнала попадают в устойчивое хранилище до подтверждения фиксации и до записи изменённых страниц данных. После сбоя WAL может воспроизвести изменения, отсутствующие на страницах. Асинхронная фиксация допускает потерю недавно подтверждённых транзакций.
4	Почему динамическое программирование полезно для многих задач оптимизации?	Оптимальная подструктура позволяет выразить оптимум через оптимумы подзадач. Если подзадачи перекрываются, хранение ответов устраняет повторную работу. Определения состояний и рекуррентное соотношение должны верно описывать исходную задачу.
5	Что такое топологический порядок и как алгоритм Кана его находит?	В ориентированном ациклическом графе каждое ребро u→v требует расположить u перед v. Поочерёдно выводят вершину с нулевой входящей степенью и удаляют её исходящие рёбра, добавляя новые вершины нулевой входящей степени в очередь. Если выведено меньше V вершин, в ориентированном графе есть цикл.
6	Что требуется для двоичного поиска и когда он работает за O(log n)?	Он последовательно делит пополам интервал поиска в данных, отсортированных согласно порядку сравнения. Для массива с доступом по индексу за O(1) и сравнением за постоянное время поиск среди n элементов занимает O(log n).
7	Когда корректен алгоритм Дейкстры и какова обычная оценка реализации с кучей?	При неотрицательных весах рёбер он последовательно фиксирует вершину с наименьшим предварительным расстоянием. Реализация со списками смежности и двоичной минимальной кучей требует O((V+E) log V). Отрицательные рёбра могут нарушить обоснование окончательности расстояния.
8	Что означают свойства транзакций ACID?	Атомарность: эффекты целиком или никак. Согласованность: корректные транзакции сохраняют ограничения и инварианты приложения. Изоляция: совместное выполнение подчиняется выбранному уровню изоляции. Долговечность: зафиксированные эффекты переживают сбои, охватываемые настроенными гарантиями базы.
9	Что такое грязное чтение и какой стандартный уровень изоляции первым его запрещает?	Чтение незафиксированных данных другой транзакции независимо от того, будет ли она затем отменена. READ COMMITTED и более строгие стандартные уровни изоляции запрещают грязное чтение.
10	Каково рекуррентное соотношение ДП для длины наибольшей общей подпоследовательности (LCS)?	Пусть L[i,j] — длина LCS префиксов длины i,j. Положим L[0,j]=L[i,0]=0. Если последние символы равны, L[i,j]=1+L[i−1,j−1]; иначе L[i,j]=max(L[i−1,j],L[i,j−1]). Полная таблица требует O(mn) времени и памяти.
11	Что такое фантомное чтение и как оно предотвращается?	Повторение запроса с предикатом обнаруживает другой набор подходящих строк после фиксации изменений другой транзакцией. SERIALIZABLE предотвращает фантомы в стандартной модели; некоторые реализации, включая PostgreSQL REPEATABLE READ, предотвращают их и на более низком уровне.
12	Каковы две фазы двухфазной блокировки (2PL)?	Рост: блокировки приобретаются без освобождения. Сокращение: освобождаются без приобретения новых. При подходящих конфликтующих блокировках чтения и записи 2PL гарантирует расписания, сериализуемые по конфликтам, но взаимные блокировки всё ещё возможны.
13	Как алгоритмы Краскала и Прима строят минимальное остовное дерево?	В связном неориентированном взвешенном графе Краскал рассматривает рёбра по возрастанию веса и использует систему непересекающихся множеств для отклонения циклов. Прим растит одно дерево, каждый раз выбирая ребро минимального веса между деревом и внешней вершиной.
14	Как соотносятся матрица смежности и обычные списки смежности?	Для V вершин и E рёбер матрица требует O(V²) памяти и проверяет наличие ребра за O(1). Списки требуют O(V+E) памяти; поиск ребра (u,v) в неотсортированном списке занимает O(deg(u)), где deg(u) — длина этого списка.
15	Что требуют первая, вторая и третья нормальные формы?	1НФ: атомарные значения атрибутов. 2НФ: 1НФ и отсутствие зависимости неключевого атрибута от собственного подмножества атрибутов любого кандидатного ключа. 3НФ: 1НФ и в каждой нетривиальной зависимости X→A либо X — суперключ, либо A входит хотя бы в один кандидатный ключ. Неключевой атрибут не входит ни в один кандидатный ключ.
16	Чем различаются WHERE и HAVING в запросе с группировкой?	WHERE фильтрует входные строки до группировки. HAVING фильтрует полученные группы и может использовать условия с агрегатами, например COUNT(*)>1.
17	Каков упрощённый логический порядок обработки SQL-запроса SELECT?	Для запроса без CTE, оконных функций и операций над множествами: FROM/JOIN → WHERE → GROUP BY и агрегаты → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET. Это логическая модель, не обязательно физический порядок выполнения оптимизатора.
18	Что делает алгоритм сортировки устойчивым?	Элементы с равными ключами сохраняют исходный взаимный порядок. Сортировка слиянием может быть устойчивой, если при равенстве сначала брать левый элемент; стандартная быстрая сортировка на месте обычно неустойчива. Устойчивость зависит от реализации.
19	Как алгоритм Беллмана–Форда работает с отрицательными рёбрами и обнаруживает достижимый отрицательный цикл?	Все рёбра релаксируются до V−1 раз. Дальнейшее улучшение через достижимую вершину выявляет отрицательный цикл, достижимый из источника. Худшее время — O(VE); для вершин, достижимых из такого цикла, нет конечной стоимости кратчайшего пути.
20	Почему быстрая сортировка может работать за Θ(n²) и как помогает рандомизация?	Повторяющиеся крайне неравномерные разбиения, например выбор минимального из различных ключей каждый раз, дают квадратичную работу. При различных ключах или подходящей обработке повторов случайные опорные элементы дают ожидаемое время O(n log n). Медиана трёх — полезная эвристика, а не гарантия для худшего случая.
21	Как работает стандартная сортировка массива слиянием и каковы её затраты времени и памяти?	Она рекурсивно сортирует две половины и сливает их за линейное время. Стандартный вариант требует Θ(n log n) времени и O(n) дополнительной памяти при сравнении за постоянное время.
22	Чем различаются кластеризованные и некластеризованные индексы строкового хранения в SQL Server?	Кластеризованный индекс хранит строки таблицы в порядке ключа, поэтому он может быть только один. Некластеризованный индекс содержит собственные ключи и указатели на строки, а также может включать другие столбцы. Термины и детали хранения различаются между СУБД.
23	Почему B+ деревья полезны для индексов баз данных и диапазонных запросов?	Большое число потомков уменьшает высоту дерева и число обращений к страницам. Упорядоченные ключи и связанные листья поддерживают просмотр диапазона. Хеш-индексы рассчитаны на поиск по равенству и сами по себе не дают такого упорядоченного доступа к диапазонам.
24	Как работает сортировка вставками и от чего зависит её время на почти отсортированных данных?	Каждый элемент вставляется в отсортированный префикс. Обычный вариант со сдвигами или обменами соседних элементов работает за Θ(n+I), где I — число инверсий. При I=O(n) время линейно; сам по себе малый размер входа не меняет худшую оценку Θ(n²).
25	Что такое неповторяемое чтение и какой стандартный уровень изоляции его запрещает?	Повторное чтение строки даёт изменённые данные либо строка исчезает после фиксации обновления или удаления другой транзакцией. REPEATABLE READ и SERIALIZABLE запрещают эту аномалию.
26	Чем жадный алгоритм отличается от динамического программирования?	Жадный алгоритм окончательно выбирает локальный вариант и требует доказательства, что такие выборы сохраняют оптимум. ДП сравнивает альтернативы по рекуррентному соотношению и повторно использует решения подзадач. Глобальный оптимум требует правильной модели и рекуррентного соотношения, а не просто названия «ДП».
27	Чем различаются INNER JOIN и LEFT JOIN?	INNER JOIN возвращает сочетания строк, удовлетворяющие условию соединения. LEFT JOIN также сохраняет каждую левую строку без совпадения, подставляя NULL в столбцы правой стороны. Несколько совпавших правых строк могут дать несколько результатов для одной левой строки.
28	Как поиск в глубину обнаруживает цикл в ориентированном графе?	DFS идёт в глубину с помощью рекурсии или явного стека. Ребро к вершине, которая ещё активна на текущем пути DFS, является обратным и доказывает наличие ориентированного цикла; ребра к любой ранее посещённой вершине недостаточно.
29	Каковы худшие оценки времени и дополнительной памяти пирамидальной сортировки на месте?	Построение кучи требует O(n), а все извлечения — O(n log n). При итеративном просеивании вниз во входном массиве сортировка требует O(n log n) времени в худшем случае и O(1) дополнительной памяти.
30	Чем различаются мемоизация и динамическое программирование снизу вверх?	Мемоизация вычисляет подзадачи по необходимости, обычно рекурсивно, и сохраняет результаты. ДП снизу вверх вычисляет состояния в порядке, при котором зависимости уже известны, обычно заполняя таблицу.
31	Когда сортировка подсчётом или поразрядная сортировка могут работать за линейное время?	Сортировка подсчётом требует O(n+k) для n ключей из диапазона k значений. Поразрядная сортировка с d устойчивыми проходами по разрядам и основанием b требует O(d(n+b)). Линейность возможна лишь при подходящих параметрах; алгоритмы используют структуру ключей, а не только сравнения.
32	Как поиск в ширину находит кратчайшие пути в невзвешенном графе?	BFS использует очередь FIFO и обходит вершины по расстоянию в рёбрах. Пометка вершины при добавлении в очередь предотвращает повторные посещения. Первый найденный путь к достижимой вершине содержит минимальное число рёбер.