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

62
Распространенные ложные убеждения в теоретической информатике

РЕДАКТИРОВАТЬ НА 10/12/08: Я постараюсь изменить вопрос, чтобы он мог заинтересовать больше людей поделиться своим мнением. Нам нужен ваш вклад! Этот пост вдохновлен тем, что в МО: Примеры распространенных ложных убеждений в математике . Большие списки иногда генерируют огромное количество ответов,...

55
Где и как компьютеры помогли доказать теорему?

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

10
Гипотеза Хартманиса-Стернса и вычислимые трансцендентные числа

В статье 1965 года " О вычислительной сложности алгоритмов " Хартманиса и Стернса авторы предполагают, что если машина Тьюринга в реальном времени вычисляет действительное число , например, в базе 10, то является либо рациональным числом, либо трансцендентное число.rrrrrr Существует ли вычислимое...

10
Легко оптимизировать, но сложно оценить

Существуют ли известные естественные примеры задач оптимизации, для которых гораздо проще найти оптимальное решение, чем оценить качество данного варианта решения? Для конкретности мы можем рассмотреть задачи оптимизации, решаемые за полиномиальное время, в форме: «заданный x, минимизируйте », где...

9
Примеры, в которых размер алфавита (

Позволять ΣΣ\Sigmaбыть алфавитом, то есть непустым конечным множеством. Строка - это любая конечная последовательность элементов (символов) изΣΣ\Sigma, Например,{0,1}{0,1} \{0, 1\} это двоичный алфавит и 011001100110 это строка для этого алфавита. Обычно, пока ΣΣ\Sigma содержит более 1 элемента,...