Информатика

21
Является ли выборка отклонения единственным способом получить действительно равномерное распределение случайных чисел?

Предположим, что у нас есть генератор случайных чисел, который выводит числа в диапазоне [0..R−1][0..R−1][0..R-1] с равномерным распределением, и нам нужно генерировать случайные числа в диапазоне [0..N−1][0..N−1][0..N-1] с равномерным распределением. Предположим, что N<RN<RN < R и NNN не...

21
Сжатие доменных имен

Мне любопытно, как можно очень компактно сжать домен произвольного имени хоста IDN (как определено в RFC5890 ), и подозреваю, что это может стать интересной задачей. Хост Unicode или доменное имя (U-метка) состоит из строки символов Unicode, обычно ограниченных одним языком в зависимости от домена...

21
Как показать, что две модели вычислений эквивалентны?

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

21
Когда я должен изучать искусственный интеллект? [закрыто]

Закрыто . Этот вопрос основан на мнении . В настоящее время не принимает ответы. Хотите улучшить этот вопрос? Обновите вопрос, чтобы ответить на него фактами и цитатами, отредактировав этот пост . Закрыто в прошлом году . Прямо к делу: я бы очень хотел выучить ИИ. Но я хочу получить совет от...

21
Каково значение обратной польской записи?

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

21
Уменьшить следующую проблему до SAT

Здесь проблема. Даны , где каждый T i ⊆ { 1 , … , n } . Существует ли подмножество S ⊆ { 1 , … , n } с размером не более k таким, что S ∩ T i ≠ ∅ для всех i ? Я пытаюсь свести эту проблему к SAT. Моя идея решения будет иметь переменную х яk,n,T1,…,Tmk,n,T1,…,Tmk, n, T_1, \ldots,...

21
Лямбда-исчисление вне функционального программирования?

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

21
Является ли проблема «подмножество продукта» NP-полной?

Задача подмножества сумм является классической NP-полной задачей: Учитывая список чисел и цель , есть ли подмножество чисел из которое суммирует к ?k L kLLLКkkLLLКkk Студент спросил меня, является ли этот вариант проблемы, называемый проблемой «подмножество продукта», NP-полным: Имея список чисел и...

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

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

21
Теория категорий (не) для программирования?

Изучив Haskell и другие не очень чистые языки FP, я решил прочитать о теории категорий. Получив хорошее понимание теории категорий, я начал думать о том, как концепции теории категорий могут быть использованы для разработки программ, но, как бы я ни старался, кажется, это не тот путь. Проведя много...

21
Классы сложности, где

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

21
Как смоделировать кубик с честной монетой

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

21
Как я могу преподавать информатику без использования компьютеров?

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

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

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

21
Машины для контекстно-свободных языков, которые не получают никакой дополнительной силы от недетерминизма

При рассмотрении компьютерных моделей вычислений иерархия Хомского обычно характеризуется (по порядку) конечными автоматами, автоматами со спуском, линейными связанными автоматами и машинами Тьюринга. Для первого и последнего уровней 1 (обычные языки и рекурсивно перечислимые языки) не имеет...

21
Может ли проблема остановки быть «решена» путем перехода к более высокоуровневому описанию вычислений?

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

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

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

21
Почему эти (без потерь) методы сжатия многих похожих изображений PNG неэффективны?

Я просто наткнулся на следующее: я положил несколько одинаковых копий png-изображения в папку, а затем попытался сжать эту папку следующими способами: tar czf folder.tar.gz folder/ tar cf folder.tar folder/ && xz --stdout folder.tar > folder.tar.xz (это хорошо работает для идентичных...