Проблемы компьютерной науки, которые по-прежнему проблематичны

Помимо упомянутых в Википедии (Неразрешенных проблем в информатике), что еще предстоит решить проблемы компьютерной науки?

Я подумал о том, чтобы задать этот вопрос, потому что другие великие умы там могут не знать, что такие проблемы существуют.

(Установите для сообщества вики, одна проблема с CS за сообщение, пожалуйста)

Те, что размещены в Википедии:

Ответы

Ответ 1

Я до сих пор не понял, где находится Any Key.


Хорошо, со всей серьезностью (и для того, чтобы внести что-то стоящее), как насчет проблемы применения параллельных вычислений к "серийным" задачам? Достигнуты теоретические пределы последовательных вычислений, тогда как параллельные вычисления не имеют теоретического предела. Однако применение параллельных вычислений к серийным проблемам очень сложно. Например, для серийной задачи может потребоваться серия вычислений, при этом результаты каждого расчета в серии полагаются на результат предыдущего расчета. Как вы выполняете эту задачу параллельно?

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

Ответ 2

Поиск соглашения о том, какой язык программирования используется для решения каких-либо проблем.

Ответ 3

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

Ответ 5

Изоморфизм графов.

В основном, наиболее естественно возникающие проблемы либо легкие (P), либо, вероятно, жесткие (NP). Было, если память служит, 2 или 3 проблемы, которые упали "между ними". Прималтия была одной, но в последнее время она оказалась в P. Графический изоморфизм - еще один.

Изоморфизм графов - это вопрос: если G1 и G2, G2 просто G1, но "перемаркировано"? Одинаково, можем ли мы переставить G2 так, чтобы он был точно таким же, как G1?

Статьи в вики! Общий обзор, а также статья о проблеме его класса сложности здесь.

Изменить: мне действительно нужно запомнить, чтобы набирать ВСЕ слова.

Ответ 6

Динамическая оптимальность для splay trees.

Исправить набор запросов в двоичном дереве поиска. ( "Найти node 6. Найти node 13. Найти node 42"...) Splay-деревья статически оптимальны: если вы создаете фиксированное двоичное дерево поиска и запускаете запросы против него, оно больше не будет работать чем постоянный множитель быстрее, чем запуск запросов против дерева splay.

Это несколько сравнение яблок с апельсинами, поскольку дерево splay не является статическим деревом. Открытый вопрос заключается в том, являются ли splay деревья динамически оптимальными: находится ли он в постоянном факторе дерева, которое может изменять себя во время запросов?

Ответ 7

ORM - Вьетнам Информатики - Тед Ньювард

То есть, он не решен для удовлетворения многих народов.

Ответ 9

Связывание элементов пользовательского интерфейса с базой данных.

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

Ответ 10

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

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

Ответ 12

Заметим, что тезис Церкви-Тьюринга на самом деле не является, действительно, утверждением о математике. Это утверждение о физическом мире.

Ближе всего вы можете прийти к доказательству этого, что-то вроде "это верно при стандартной модели".

Это не означает, что это не может быть формализовано в большей степени, но лучшее, на что вы можете надеяться, это прояснить конкретные предположения о физическом мире.

Ответ 13

Проблема коммивояжера, которую я считаю, по-прежнему остается нерешенной.

Ответ 14

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

AI, вероятно, является областью исследований, где это было наиболее заметным, но, в конце концов, многие другие люди мечтали о том, что в основном означает "Делать то, что я имею в виду". (Я мог бы вписаться в эволюционные алгоритмы, нейронные сети, а в последнее время и семантические веб-люди здесь). Главным препятствием является то, что все, что делает компьютер, это смещение бит.

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

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

Ответ 15

P =? NC будет моим голосованием. Автоматическое многократное распараллеливание было бы возможно при P = NC, но оно полагало, что эти два разных, и, следовательно, есть P-полные проблемы, которые трудно распараллелить. Понимание того, какие проблемы относятся к этому классу, приобретает все большее значение.