1. дома
  2. Вопрос и ответ
  3. Проблемы компьютерных наук, которые по-прежнему проблематичны

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

2009-07-28 4 views
17

Помимо упомянутых в Википедии (Unsolved problems in computer science), что еще предстоит решить проблемы компьютерной науки?Проблемы компьютерных наук, которые по-прежнему проблематичны

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

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

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

источник

2009-07-28 Randell

+0

Обратите внимание, что односторонние функции означают P! = NP. –

ответ

25

Я до сих пор не понял, где Любой ключ есть.


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

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

источник

2009-07-28 08:11:58 zombat

+5

HAHA, так много ответов. Но мне интересно, как вы, ребята, пропустили это: Браузер, который следует за каждым правилом CSS, присутствующим в наборе правил CSS для W3C. И почему это конкретное сообщение не позволяет мне отправить ответ, я получаю сообщение об ошибке страницы. – pokrate

+4

+1 для любого ключа. –

+0

@pokrate: потому что это не проблема с CS, и вы имеете в виду «спецификацию CSS», и существует более одной спецификации CSS (поэтому ваш ответ неоднозначен), но в основном это плохой ответ, потому что решение мыслимо. Мы даже не знаем, разрешены ли некоторые из проблем CS. @zombat: законы Амдаля и Густафсона относятся к делу. – outis

1

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

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

источник

2009-07-28 08:13:58

+4

Хотя это интересная проблема, на самом деле это не связано с информатикой. Возможно, разработка программного обеспечения. Но CS? –

+3

И, аналогично, как в базе данных под контролем источника. Определенно не проблема CS, но определенно не решена. – Unsliced

1

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

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

источник

2009-07-28 08:20:00

10

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

источник

2009-07-28 08:28:11

+4

Невозможно ... ;-) – peSHIr

+1

Ответ «Emacs». ... Какие? – zombat

1

Как улучшить NetFlix algorithm СЛЕДУЮЩИЙ 10% :) (поздравляю с Ансамблем!)

источник

2009-07-28 08:31:03 pageman

+1

Не считайте свою курицу, они могут или не иметь лучшего теста. ;) – KTC

+0

@ KTC действительно? они продлевали срок? http://www.netflixprize.com/closed – pageman

+0

@pageman: «RMSE для первого подпрограммы« викторины »будет публиковаться на Сайте, RMSE для второго подмножества« тест »не будет публиковаться публично, но будет чтобы квалифицировать подачу, как описано ниже ». Рейтинг публичного рейтинга лидеров на основе первого набора может соответствовать или не соответствовать окончательному ранжированию на основе второго второго набора. – KTC

3

Открытый Проблема Сад имеет небольшой список, который вы могли бы быть заинтересованы в:

источник

2009-07-28 09:04:53 ars

+0

Ух, возможности для бесконечных часов творческих проволочек. Мой босс не будет счастлив ... –

3

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

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

Этот изоморфизм представляет собой этот вопрос: учитывая, что G1 и G2 являются G2 просто G1, но «перемаркированы»? Одинаково, можем ли мы переставить G2 так, чтобы он был таким же, как G1?

Wiki articles! A overview и статья, касающаяся вопроса о классе сложности here.

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

источник

2009-07-28 16:38:39 agorenst

2

Успешно выигрывает против людей в игре Go. Wiki Article about computers and go.

источник

2009-07-28 16:42:02 Smandoli

+0

.... хотя, возможно, это слишком общее. Это зависит от значения «проблемы», я полагаю. Если тест Тьюринга имеет значение, я думаю, это тоже. – Smandoli

+0

Когда я прочитал статью wiki, я убедился, что это будет больше в категории Grand Challenge. Интересно, что он не найден в http://en.wikipedia.org/wiki/Grand_Challenge_problem. Теперь, как это может быть? – Smandoli

+0

в 2016 году, это было достигнуто. (: – mauris

1

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

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

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

источник

2009-07-28 23:59:31

+0

Как это так? Это утверждение о вычислимости некоторых функций. Конечно, тезис изложен в терминах разрешимости с помощью машины Тьюринга, но это не то же самое, что физический компьютер. Например, TM разрешено имеют бесконечную память.Она может иметь только конечный набор состояний, но число состояний строго ограничено, поэтому вы можете иметь «столько, сколько хотите». – Clayton

+0

В теории вычислимости, однако, существуют различные конструкции, позволяющие различные миры вычислений. Самый простой пример - это то, где Turing Machines имеют доступ к так называемому «Oracle», который, как следует из названия, просто дает ответ на определенную проблему. Если у TM есть оракул для проблемы с остановкой, вы в совершенно другом мире вычислений, и возможны даже более сумасшедшие проблемы (и всегда есть более бескомпромиссные). Вот несчастно-техническая вики-артика le: http://en.wikipedia.org/wiki/Arithmetical_hierarchy – agorenst

+0

@Clayton В неофициальном сообщении говорится, что любой физический компьютер, который вы можете создать, может быть смоделирован машиной для turing. С чисто математической точки зрения легко представить контрпримеры к тезису - в качестве простого примера - ТМ с прерывистым оракулом. Единственное, что делает такие контрпримеры недействительными, - это физический мир. –

3

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

Исправить набор запросов в двоичном дереве поиска. («Найти узел 6. Найти узел 13. Найти узел 42» ...) Деревья Splay: Статически оптимальный: если вы создадите фиксированное двоичное дерево поиска и запустите с ним запросы, он будет работать не более, чем с постоянным коэффициентом быстрее, чем запускать запросы против дерева splay.

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

источник

2009-07-29 00:14:00

+0

+1 - интересный. Я никогда не слышал об этом раньше. – zombat

3

ОРМ является Вьетнам компьютерных наук -Ted Neward

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

источник

2009-07-29 00:25:49 CoderTao

+1

Или это дорогое и по сути бессмысленное упражнение без надежды на успех? – Clayton

+0

Да, это тоже ... – CoderTao

8

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

источник

2009-07-29 00:33:06 ehsanul

+1

Если вы можете сделать алгоритм, который может сравнить, какой из двух алгоритмов НЛП «на самом деле работает» или просто «работает лучше», это было бы началом! –

1

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

источник

2009-07-29 00:41:44

+4

Это не нерешенная проблема. Было доказано, что NP-Complete, но это не то же самое, что и нераскрытое. Решение грубой силы состоит в том, чтобы просто рассчитать длину всех возможных маршрутов, а затем выбрать самый короткий. Это вычислительно дорого до такой степени, что это непрактично, но это решение. – Clayton

+1

Он по-прежнему не удовлетворяет формальным стандартам эффективности, но вы правы, технически он решен. – 2009-07-29 01:40:27

+0

Это полностью разрешено в том смысле, что он, как известно, является NP-полным. –

1

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

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

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

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

источник

2009-08-05 08:28:23

0

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

источник

2011-09-22 05:58:50 Charles

Смежные вопросы

 Смежные вопросы