Информатика

11
Сведение продуктов в HoTT к кодировкам церкви / Скотта

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

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

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

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

Мне дали следующую проблему во время интервью: Дает строку, которая содержит некоторую смесь символов (без скобок или фигурных скобок - только символы) с другими буквенно-цифровыми символами, идентифицирует все символы без соответствующих имен. Например, в строке ") (ab))" индексы 0 и 5 содержат...

11
Что означает «ширина» в поиске ширины?

Я узнавал о широте первого поиска и вопрос пришел в голову , что , почему BFS называется так. В книге Введение в алгоритмы по КСПС , я прочитал следующую причину этого: Поиск в ширину так назван потому, что он расширяет границы между открывшимся и неоткрытых вершин равномерно по всей ширине...

11
Может ли предварительный заказ двух разных деревьев быть одинаковыми, даже если они разные?

Эта вопрос в значительной степени объясняет, что они могут, но не показывает никаких примеров наличия двух разных деревьев с одним и тем же обходом предварительного заказа. Также упоминается, что обход по порядку двух разных деревьев может быть одинаковым, хотя они структурно разные. Есть ли пример...

10
Алгоритм для проверки, является ли двоичное дерево поисковым деревом и подсчитывает ли количество полных ветвей

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

10
Анализ и ссылки на топологии сетей типа Кох-снежинки (и других экзотических)

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

10
Устойчивость для пар в задаче стабильного соответствия

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

10
Являются ли двухуровневые планировщики полезными только для управления обменом?

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

10
Как получить инвариант цикла в этом алгоритме поиска границ?

Первоначально по математике. Но там без ответа. Рассмотрим следующий алгоритм. u := 0 v := n+1; while ( (u + 1) is not equal to v) do x := (u + v) / 2; if ( x * x <= n) u := x; else v := x; end_if end_while где u, v и n - целые числа, а операция деления - целочисленное деление. Объясните, что...

10
Список вводных книг по TCS для тех, кто мало знает о TCS [закрыто]

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

10
Учитывая строку и CFG, какие символы могут следовать за строкой (в предложениях форм CFG)?

Пусть множество терминального и N множества нетерминальных символов некоторой контекстно-свободная грамматика G .ΣΣ\SigmaNNNGGG Скажем , у меня есть строка такое , что х у ∈ S ( G ) , где х , у ∈ ( Е ∪ N ) * и S ( G ) являются сентенциальные формы G .a ∈(Σ∪N)+a∈(Σ∪N)+a \in (\Sigma \cup N)^+х аy∈ S(...

10
Вопрос, касающийся машины Тьюринга с бесполезным состоянием

Итак, вот вопрос из прошлого теста в моем классе теории вычислений: Бесполезное состояние в ТМ - это состояние, которое никогда не вводится ни в какую строку ввода. Пусть Докажите, что неразрешима.USELESSTM={⟨M,q⟩∣q is a useless state in M}.USЕLЕSSTMзнак равно{⟨M,Q⟩|Q бесполезное состояние...

10
Язык значений аффинной функции

Напишите для десятичного расширения (без начального ). Пусть и целые числа с . Рассмотрим язык десятичных разложений кратных плюс константа:n¯n¯\bar nnnn0aaabbba>0a>0a > 0aaa M={ax+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯∣x∈N}M={ax+b¯∣x∈N}M = \{ \overline{a\,x+b} \mid x\in\mathbb{N} \} Является регулярными?...

10
Скорость исправления ошибок вводит в заблуждение

В теории кодирования «насколько хорош код» означает, сколько ошибок канала можно исправить, или, лучше сказать, максимальный уровень шума, с которым может справиться код. Чтобы получить лучшие коды, коды разработаны с использованием большого алфавита (а не двоичного). И потом, код хорош, если он...

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

В трассировщике Whited ray каждое пересечение луч-объект порождает проходящий луч (если объект был полупрозрачным), отраженный луч и теневой луч. Теневой луч вносит вклад в компонент прямого освещения. Но что произойдет, если теневой луч пересекает прозрачный объект? Компонент прямого освещения...

10
Полиморфизм и индуктивные типы данных

Мне любопытно. Я работал над этим типом данных в OCaml : type 'a exptree = | Epsilon | Delta of 'a exptree * 'a exptree | Omicron of 'a | Iota of 'a exptree exptree Которым можно манипулировать, используя явно типизированные рекурсивные функции (функция, которая была добавлена ​​совсем недавно)....

10
В ограниченном программировании есть ли модели, учитывающие количество изменений переменных?

Рассмотрим модель CSP, где изменение значения конкретной переменной стоит дорого. Есть ли работа, в которой целевая функция также учитывает количество изменений в значении переменной в процессе поиска? Пример: переменная, дорогая к изменению, может находиться под контролем какого-либо другого...