Главная » 2019 » Январь » 16 » Кузюрин Н.Н., Фомин С.А. - Сложность комбинаторных алгоритмов. Курс лекций
13:48
Кузюрин Н.Н., Фомин С.А. - Сложность комбинаторных алгоритмов. Курс лекций
Понятие алгоритма в математике используется давно, но различные его формализации были предложены только в середине 30-х годов прошлого столетия, когда и стала складываться теория алгоритмов. Классическая теория алгоритмов вообще не интересуется сложностными аспектами (временем решения задач на реальных вычислителях). В рамках классической теории алгоритмов, ставятся и решаются задачи о разрешимости различных задач, однако вычислительная сложность полученных решений принципиально не исследуется. Однако с практической точки зрения, может не быть никакой разницы между неразрешимой задачей и задачей, решаемой за время Ω(exp(n)), где n — длина входа. Таким образом реализации алгоритмов на реальных вычислитель- ных машинах обязательно требуют анализа сложности их выполнения. Анализом задач с точки зрения вычислительной сложности занимается раздел теории алгоритмов — теория сложности вычислений, активно развивающийся с 50х годов — с момента создания вычислительной техники. Теория сложности вычислений занимает промежуточное положение между строгой математикой и реальным программированием. Для математика это в первую очередь математическая теория, строящаяся на основе фундаментальных понятий полиномиальной вычислимости и полиномиальной сводимости. Для программиста-практика — это набор общих методов, парадигм и конструкций, позволяющий в ряде случаев существенно минимизировать прямолинейный перебор вариантов, а в ряде случаев — показать, что эта задача в рассматриваемой постановке скорее всего неразрешима (и, следовательно, следует искать более реалистичные постановки).
Xemera.At.Ua - информационный портал! Все ссылки на файлы, указанные на сайте взяты из открытых источников интернета и предоставлены пользователями нашего сайта исключительно в ознакомительных целях.
Если вы являетесь правообладателем какого либо материала и не желаете его свободного распространения, или считаете, что какой-либо из материалов нарушает Ваши авторские права - свяжитесь с Администрацией.
Владельцы и создатели данного сайта не несут ответственность за использование и содержание ссылок и информации, представленных на этом сайте.
Сайт оптимизирован для просмотра с разрешением 1024x768, 1280x800, 1280x1024 и 1600x1200 браузером FireFox или Opera