Как правильно сформулировать вычислительную задачу?

20

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

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

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

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

осветление

Чтобы сделать вопрос более конкретным, давайте предположим, что они знают базовую терминологию по математике / CS, такую ​​как наборы, функции, графики, списки и т. Д. На уровне студентов бакалавриата 1-го / 2-го курса (как в случае с людьми, которые у меня есть в разум). Например, они прочитали некоторый вводный учебник, такой как Aho и Ullman (хотя они, возможно, не поняли это полностью).

algorithms reference-request books Кава
источник
2
Я думаю, что это хороший вопрос, но я не знаю, есть ли хороший ответ. Я чувствую, что это своего рода вопрос: «Есть ли способ, которым мы можем научить кого-то, кто не является ученым, думать как компьютерный специалист?» И ответ на этот вопрос - «да, сделайте их компьютерным ученым». Тем не менее, некоторые разработчики программного обеспечения, возможно, провели исследования на такие вещи, как это.
jmite
3
Кроме того, я думаю, что это то, для чего в некоторой степени используются сценарии использования. Если кто-то не понимает, как правильно сформулировать свою проблему, перечислите ряд сценариев того, что он хотел бы сделать для данной программы, и ожидаемое поведение в каждом конкретном случае. Затем программист разрабатывает спецификацию из этого. Тем не менее, я человек теории, а не инженер, поэтому, если я ошибаюсь, не стесняйтесь поправлять меня.
jmite
@jmite, спасибо за комментарии. Вы правы в том, что частью разработки программного обеспечения является попытка понять, чего хочет клиент (я думаю, они называют это анализом требований ). Но это обычно для крупных проектов. Я не говорю о таких проектах, но о простых вопросах, подобных тем, которые мы получаем на этом сайте, которые не сформулированы строго. Я видел книги, обучающие людей тому, как формулировать утверждение в логике, на многих примерах. Я надеюсь, что есть что-то похожее для алгоритмов и вычислительных задач.
Каве
1
Тем не менее, я считаю, что это требует определенного мышления, который не легко усваивается, особенно взрослыми. Я пытался заставить людей отказаться от технических вещей и объяснить проблему как можно проще с точки зрения повседневных предметов. Проблема в том, что они обычно забывают какое-то ограничение, или они будут звучать так, как будто в их действительной системе O (N) - O (1) и т. Д. Таким образом, я получу нечто очень близкое к точному определению неправильной проблемы.
Свинья
2
В некотором смысле, то, о чем просят, противоречиво, потому что строгое формулирование проблем - это как раз один из ключевых приобретенных навыков, который отделяет мирян от специалистов / профессионалов ...
vzn

Ответы:

3

Хороший ресурс по этому вопросу, довольно известный ученым, но не столь широко известный за пределами специалистов, - « Математическое письмо » Дональда Кнута, Трейси Л. Ларраби и Пола М. Робертса. есть опубликованная книга, видео лекций и набор заметок. это больше написано с точки зрения людей, пытающихся овладеть математическим письмом, например, для создания статей, но все советы весьма применимы к случаю непрофессионалов, пытающихся точно сформулировать проблемы. Математическое письмо, в то время как трудным для изучения является научный подход к строгому определению / формулированию и, как подробно описано в книге, решению , например, с помощью алгоритмов или доказательств, вычислительных / алгоритмических задач.

Кроме того, классический текст Garey & Johnson, Computers & Intractability точно не описывает, как точно формулировать проблемы, но он дает много примеров и разнообразных теоретических / концептуальных / технических «шаблонов», организованных в разделы схожих проблем, которые могут быть используется в качестве «строительных блоков» для описания вычислительных / алгоритмических задач.

ВЗН
источник
Спасибо VZN, это хорошие ресурсы о написании математики, но я не ищу что-то другое. Проблема не в том, чтобы писать хорошо по математике, а в том, чтобы люди научились формулировать вычислительные задачи достаточно четко, чтобы эксперт мог понять, что ищет человек, задающий вопрос, и помочь им.
Каве
YW; Вы говорите, что это две разные вещи, и в словах / фразах они есть, но & я говорю, что они [заимствовать фразу разработки программного обеспечения] "тесно связаны"
vzn
3

только что наткнулся на этого милого / аккуратного, необычного, относительно нового / неизвестного референта на своей домашней странице Эммануэле Виолы , профессора (T) CS в Северо-Восточном университете), по-видимому, неопубликованного в другом месте. 41pp. он начинается с самых базовых математических понятий, например импликации, а затем охватывает все сложные темы, такие как теорема Эрдеша – Секереса и теория Рамсея .

ВЗН
источник
0

Купите книгу «Алгоритмы и структуры данных» у Роберта Лафора.

В этой книге каждый алгоритм объясняется как история, очень похожая на поэзию. Затем передайте человеку версию алгоритма Lafore, а затем версию CLRS.

Может быть, таким образом, человек почувствует, как перевести интуитивное описание на строгие.

user5193682
источник