0
голосов
0
ответов
49 показов

Есть 2020 физиков и 2020 математиков. Некоторые из них знакомы между собой, знакомства взаимны. По итогам года 200 человек получили премии. При этом у ...
0
голосов
0
ответов
37 показов

Показать, что если множество ошибок $$C \subseteq B^n$$ состоит не более чем из $$n2^{n/2}$$ наборов, то найдется полиномиальный код, который исправля ...
0
голосов
1
ответ
104 показа

Докажите, что линейные порядки N × Z и Z × Z неизоморфны. (Упорядочение пар лексикографическое.)
0
голосов
0
ответов
62 показа

Дано множество U из n элементов. Каким числом способов в нем можно выбрать три подмножества A, B и C, так, чтобы выполнялись следующие условияn=7, |AU ...
1
голос
1
ответ
164 показа

Сколько существует монотонных булевых функций, зависящих от 4 переменных x1, x2, x3, x4?
0
голосов
1
ответ
149 показов

Определить коэффициент при x5 из разложения выражения (x3 + x - 2)8 степени
0
голосов
0
ответов
130 показов
0
голосов
0
ответов
82 показа

Докажите, что любое бесконечное рекурсивное множество A ⊆ N можно разбить на два непересекающихся бесконечных рекурсивных подмножества, т.е. существую ...
0
голосов
1
ответ
178 показов

Функция f : N → N называется строго возрастающей на множестве B ⊆ N, если f определена намножестве B (т.е. для любого x ∈ B значение f(x) определено) ...
0
голосов
1
ответ
183 показа

Докажите, что множество A = {<x,y> | Wx ∪ Wy != ∅} рекурсивно перечислимо и K <_m A, гдеK = {x | φx(x)↓}.
0
голосов
0
ответов
113 показов

Пусть f : N → N тотальная вычислимая функция. Докажите, что множество всех натуральныхчисел x таких, что f(y) < f(x) для некоторого y > x, являе ...
0
голосов
0
ответов
146 показов

Пусть A ⊆ N рекурсивно перечислимо, а B ⊆ N рекурсивно. Докажите, что множество A ∩ Bрекурсивно перечислимо. Приведите пример рекурсивно перечислимого ...
0
голосов
0
ответов
124 показа

Рассмотрим следующую частично рекурсивную функциюf(x) = μy (g(y) = x) = μy P(x, y),полученную минимизацией предиката P(x, y) ⇐⇒ (g(y) = x) по переменн ...
0
голосов
0
ответов
117 показов

Докажите, что множество всех “промежутков” между простыми числами, т.е. множество всех на-туральных чисел, которые представляются в виде разности двух ...
0
голосов
0
ответов
146 показов

Верно ли, что если машина Тьюринга M за время своего вычисления посещает одну и ту жеконфигурацию дважды, то это вычисление не завершается (т.е. машин ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru