Вопросы с тегом «sets»

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

33
В чем именно семантическая разница между множеством и типом?

РЕДАКТИРОВАТЬ: я теперь задавал аналогичный вопрос о разнице между категориями и сетами. Каждый раз, когда я читаю о теории типов (которая, по общему признанию, довольно неформальна), я не могу понять, чем она конкретно отличается от теории множеств . Я понимаю, что существует концептуальная...

29
Где взять графики для проверки моих алгоритмов поиска?

Я реализую набор алгоритмов поиска пути, таких как Dijkstra, Depth First и т. Д. Сначала я использовал пару самодельных графиков, но теперь я хотел бы пойти дальше, и поэтому я ищу либо графики, используемые в тестах; графики городов реального мира (или способ загрузки информации такого рода с карт...

29
Логический поиск объяснил

Моя мама проходит некоторые онлайн-курсы, чтобы быть своего рода библиотекарем, в этом курсе они охватывают булевы поиски, поэтому они могут эффективно выполнять поиск в базах данных, однако у нее возник вопрос, звучащий примерно так: Поиск "x ИЛИ y" приведет к 105 000 обращений, в то время как...

21
Структура данных для пересечения множества?

Существует ли какая-либо структура данных, которая поддерживает набор множеств (конечного наземного множества), поддерживающий следующие операции? Любое сублинейное время работы будет оценено? Инициировать пустой набор. Добавить элемент в набор. Учитывая два набора, сообщают, пересекаются ли они....

21
за время O (n): найти наибольший элемент в наборе, где сравнение не транзитивно

Название устанавливает вопрос. В качестве входных данных у нас есть список элементов, которые мы можем сравнить (определить, какой из них больше ). Ни один элемент не может быть равным. Ключевые моменты: Сравнение не является транзитивным (подумайте о бумажных ножницах): это может быть правдой:...

21
Частота процессора в год

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

20
Проблемы, для которых алгоритмы, основанные на уточнении разделов, работают быстрее, чем за логлиническое время

Уточнение разделов - это техника, в которой вы начинаете с конечного набора объектов и постепенно разбиваете набор. Некоторые проблемы, такие как минимизация DFA, могут быть достаточно эффективно решены с помощью уточнения разделов. Я не знаю никаких других проблем, которые обычно решаются с...

20
Насосная лемма для простых конечных регулярных языков

В Википедии есть следующее определение леммы прокачки для регулярных языков ... Пусть обычный язык. Тогда существует целое число ≥ 1, зависящее только от , так что каждая строка в длиной не менее ( называется «длиной накачки») может быть записана как = (т. можно разделить на три подстроки),...

15
По заданному набору наборов найдите наименьший набор (ы), содержащий хотя бы один элемент из каждого набора.

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

14
Вычислительная разница между двумя большими наборами

У меня есть два больших наборов целых чисел AAA и . Каждый набор содержит около миллиона записей, и каждая запись представляет собой положительное целое число длиной не более 10 цифр. BBB Каков наилучший алгоритм для вычисления и ? Другими словами, как я могу эффективно вычислить список записей ,...

14
Как найти максимальный набор элементов массива, такой, что каждый элемент в больше или равен количеству элементов в ?

У меня есть алгоритмическая проблема. Дан массив (или набор) из неотрицательных целых чисел. Найти максимальное множество из , что для всех ,,н STTTnNnSSSTTTa∈Sa∈Sa\in Sa⩾|S|a⩾|S|a\geqslant |S| Например: Если TTT = [1, 3, 4, 1, 3, 6], то SSS может быть [3, 3, 6] или [3, 4, 6] или [4, 3, 6]. В = [7,...

11
Поиск наборов «отпечатков пальцев»

Скажем, у нас есть 10 людей, каждый из которых со списком любимых книг. Для данного лица X, я хотел бы найти особое подмножество книг иксов понравившихся только X, т.е. нет другого человека, который любит все книги в специальном подмножестве Х. Я думаю, что этого специального подмножества в...

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

Существуют эффективные структуры данных для представления заданных разделов. Эти структуры данных имеют хорошие временные сложности для таких операций, как Union и Find, но они не особенно эффективны в использовании. Что такое эффективный для пространства способ представления раздела набора? Вот...

11
Что является дополнением к контекстно-свободным языкам?

Можно понять ваш вопрос двумя способами, согласно определению «дополнение КЛЛ». Случай A: Дополнение к CFL - это класс всех языков, которых нет в CFL. Формально, В этом случае намного больше, чем , у него даже есть языки, которых нет в и т. Д. Но, возможно, это не то, что вы имели в...

11
В чем именно заключается семантическая разница между категорией и множеством?

В этом вопросе я спросил, в чем разница между набором и типом . Эти ответы действительно проясняются (например, @AndrejBauer), поэтому в своей жажде знаний я подчиняюсь искушению задать то же самое о категориях: Каждый раз, когда я читаю о теории категорий (которая, по общему признанию, является...

10
Существует ли известный метод построения грамматики по конечному набору конечных строк?

Из моего чтения кажется, что большинство грамматик занимается созданием бесконечного числа строк. Что делать, если вы работали наоборот? Если задано n строк длиной m, должна быть возможность создать грамматику, которая будет генерировать эти строки и только эти строки. Есть ли известный способ...

9
Ищите комплексную реализацию с небольшим объемом памяти

Я ищу реализацию заданного типа данных. То есть мы должны поддерживать динамическое подмножество SSS (размера nnn ) из юниверса U={0,1,2,3,…,u–1}U={0,1,2,3,…,u–1}U = \{0, 1, 2, 3, \dots , u – 1\} размера uuu с операции insert(x)(добавить элемент xв SSS ) и find(x)(проверяет, xявляется ли элемент...