Информатика

20
Как правильно сформулировать вычислительную задачу?

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

20
Существуют ли полностью оптимизирующие компиляторы для завершающих программ?

В книге Эндрю У. Аппеля « Реализация современного компилятора в ML» он говорит в главе 17, что теория вычислимости показывает, что всегда можно изобрести новые оптимизирующие преобразования, и продолжает доказывать, что полностью оптимизирующий компилятор решит проблему остановки: Программа Q,...

20
Появляются ли функции с более медленным ростом, чем обратный Аккерманн, в границах времени выполнения?

Некоторые сложные алгоритмы ( объединение-поиск ) имеют почти постоянную обратную функцию Аккермана, которая появляется при асимптотической сложности времени, и являются оптимальными по времени в худшем случае, если почти постоянный обратный член Аккермана игнорируется. Существуют ли примеры...

20
Почему диплоидные (доминантные / рецессивные) гены не используются широко в генетических алгоритмах?

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

20
Используя людей в качестве компонентов для создания компьютера?

Хорошо, прежде чем я начну, я понимаю, что это на периферии по теме (я прочитал справку Вопросы для этого сайта), особенно потому, что это не является реальной проблемой. Тем не мение: Я не могу найти ничего релевантного в Google С пуристической точки зрения, безусловно, это должно входить в...

20
Что именно вычисление?

Я знаю, что такое вычисления в некотором расплывчатом смысле (это то, что делают компьютеры), но я бы хотел более строгое определение. Dictionary.comОпределения вычислений, вычислений, вычислений и вычислений являются круговыми, поэтому это не помогает. Wikipediaопределяет вычисление как «любой тип...

20
Какие темы делятся вообще?

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

20
Каковы основные различия между полиморфизмом строк и подтипом

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

20
Как эффективно найти элемент последовательности Digit Sum?

Просто ради интереса я попытался решить проблему из категории «Недавние» Project Euler ( последовательность цифр суммы ). Но я не могу придумать, как решить проблему эффективно. Проблема заключается в следующем (в исходной последовательности вопросов в начале есть две, но она не меняет...

20
Сжатие двух целых чисел без учета порядка

Сравнивая упорядоченную пару (x, y) с неупорядоченной парой {x, y} (set), затем теоретически определяем, что разница составляет всего один бит, так как x идет первым или y требуется ровно один бит для представления. Итак, если нам дан набор {x, y}, где x, y - два разных 32-разрядных целых числа,...

20
Существует ли нетривиальный тип, равный его собственной производной?

Статья под названием «Производный регулярного типа - это тип контекста с одним отверстием» показывает, что «молния» типа - его контексты с одним отверстием - следуют правилам дифференцирования в алгебре типов. У нас есть:...

20
Существует ли существующая структура данных фиксированного размера, которая вытеснит самый старый / последний элемент, если будет добавлен новый элемент?

Я ищу структуру данных, которая вытолкнет его самый старый / последний элемент, если новый элемент будет вставлен. Например, давайте Dпредставим структуру. Dсодержит 3 элемента типа Number Dзначения по умолчанию будут инициализированы в 1, 2и 3. D = [ 1 , 2 ,3 ]Dзнак равно[1,2,3]D = [1, 2, 3] Если...

19
Добавляет ли операция «разница» выразительность к языку запросов, который уже включает «соединение»?

Оператор разности множеств (например, EXCEPTв некоторых вариантах SQL) является одним из многих фундаментальных операторов реляционной алгебры. Тем не менее, существуют некоторые базы данных, которые не поддерживают оператор разности множеств напрямую, но поддерживают LEFT JOIN(своего рода внешнее...

19
Совместное планирование приостанавливает процессы, когда они выполняют операцию ввода-вывода?

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

19
Алгоритмы проверки типов

Я начинаю личное библиографическое исследование по алгоритмам проверки типов и хочу несколько советов. Какие алгоритмы, стратегии и общие методы проверки типов наиболее часто используются? Меня особенно интересуют сложные алгоритмы проверки типов, которые были реализованы в широко известных строго...

19
Различие в кейсе при динамическом программировании: пример необходим!

Я работал над динамическим программированием в течение некоторого времени. Канонический способ оценить рекурсию динамического программирования - создать таблицу всех необходимых значений и заполнять ее построчно. См., Например, Cormen, Leiserson и др .: «Введение в алгоритмы» для введения. Я...

19
Простое сокращение от 3SAT до задачи о гамильтоновом пути

В книге Сипсера «Введение в теорию вычислений» на стр. 286 приведено сокращение от 3SAT до задачи о гамильтоновом пути. Есть ли более простое сокращение? Проще говоря, я имею в виду сокращение, которое было бы легче понять (для студентов). Есть ли сокращение, использующее линейное число переменных?...

19
Стратегии неприкосновенности в понимании TCS

Я аспирант, изучающий курс теории вычислений, и у меня возникли серьезные проблемы с созданием контента, как только меня об этом попросят. Я могу следовать учебнику (Введение в теорию вычислений Майкла Сипсера) и лекциям; однако когда меня просят что-то доказать или придумать формальное описание...

19
Функция ML типа 'a ->' b

Наш профессор попросил нас подумать о функции в OCaml, которая имеет тип 'a -> 'b т.е. функция одного аргумента, которая может быть чем угодно, и которая может возвращать что угодно другое. Я думал об использовании raiseв функции, которая игнорирует ее аргумент: let f x = raise Exit Но профессор...

19
Решение задачи таково, что любой алгоритм допускает экспоненциально более быстрый алгоритм

В Алгоритмике Хромковича для сложных задач (2-е издание) есть эта теорема (2.3.3.3, стр. 117): Существует (разрешимая) задача решения такая, что для каждого алгоритма A, который решает P, существует другой алгоритм A ′, который также решает P и дополнительно выполняетпPPAAAпPPA′A′A'PPP...