Простыми словами
Когда я только начинала заниматься искусственным интеллектом, многое для меня, человека с классическим математическим образованием, было совершенно непонятно.
Некоторые термины теории алгоритмов вызывали едва не священный трепет.
Когда кто-то рядом произносил "NP-полнота", я даже приблизительно не могла представить, о чем идет речь.
Вообще, классы сложности алгоритмов — удивительно интересная вещь.
Вот, дам ссылку на статью.
www2.computerra.ru/xterra/253871/
Статья написана очень хорошо, но лично мне понятны там не все логические переходы.
Постараюсь рассказать об этом попроще, а кроме того, надеюсь, расскажу и о других классах сложности алгоритмов.
Некоторые термины теории алгоритмов вызывали едва не священный трепет.
Когда кто-то рядом произносил "NP-полнота", я даже приблизительно не могла представить, о чем идет речь.
Вообще, классы сложности алгоритмов — удивительно интересная вещь.
Вот, дам ссылку на статью.
www2.computerra.ru/xterra/253871/
Статья написана очень хорошо, но лично мне понятны там не все логические переходы.
Постараюсь рассказать об этом попроще, а кроме того, надеюсь, расскажу и о других классах сложности алгоритмов.
-
-
10.06.2008 в 19:55Прямо как я сейчас)) Однако статья и правда написана очень хорошо!
Но лучше рассказать попроще))
-
-
10.06.2008 в 21:21статья действительно лучшее, что я встречала на эту тему.
Потому что казалось бы всё довольно прозрачно, но как только пытаешься это как-то уложить в голове, у меня, например, получается полная каша.
То есть даже не так: схематично всё ясно. В двух словах можно рассказать.
Но вот как ДОКАЗАТЬ NP-полноту для определенного алгоритма???
И вообще как оценить его сложность?
Хорошо, когда там, предположим, обычные вложенные циклы. А если что-то куда более сложное?