(no subject)
В 50-е годы, во время бурного развития компьютеров и их успешного применения для решения разнообразных прикладных задач, стали появляться,как грибы, различные новые компьютерные науки.
Обработка языков, обработка изображенй, искуственный интеллект и нейронные сети,криптология,биоинформатика.
Казалось,что вот-вот и компьютеры смогут делать всё.
Фантасты начинают обсуждать этические проблеммы связаные с "поумневшими машинами". Появляются первые страшилки о восстаниях машин.
Но тут, на волне всеобщей эйфории к ученым приходит некое понимание, что не всё так просто. Если до изобретения "программ" задачей программистов было "решить задачу", то сейчас на первое место выходит "решить задачу быстро и эффективно".
Вот простой пример: есть телефонный справочник миллионного города, где имена записаны по алфавиту.
Для того, чтоб найти телефон конкретного человека, можно начать просматривать справочник от начальной строчки по порядку, пока не найдем нужного человека. Тогда для того чтоб позвонить Яромиру Ягру нам понадобится просмотреть около миллиона строчек. С другй стороны, если мы откроем справочник ровно посередине и посмотрим, дошли ли мы до нужной буквы, а потом станем проверять только ту половину, в которой должна быть наша строчка, то нам понадобится всего около 10 таких проверок.
То есть существуют алгоритмы, которые решают задачу эффективнее чем другие алгоритмы.
И, конечно же, встал вопрос: " А все ли задачи можно решить одинаково быстро?" К сожалению, ответ на этот вопрос оказался сложнее, чем думали.
Так родилась теория сложности алгоритмов.
Не вдаваясь в математические подробности, можно сказать, что все алгоритмы можно разделить на классы, в которых количество работы пропорционально величине обьекта, с которым они работают.
Так,например, поиск телефона в телефонной книге относится к классу O(log n),потому что поиск занимает время, пропорциональное логарифму от количества телефонов.
А вот ,например распечатать телефонный справочник займет время пропорциональное (линейное) количеству телефонов, потому что каждый телефон мы должны "прочитать" хотябы один раз.
Теперь перейдем к очень важному вопросу.
существуют ли задачи "простые" и сложные".
Под простыми задачами я подразумеваю задачи,которые компьютер сможет решить за разумное время: день , месяц, год.
Если на решение задачи компьютеру понадобятся миллионы лет, то это задача "сложная".
Задача, которую алгоритм решает за время пропорциональное количеству элементов О(n)- простая. И задача пропорциональная квадрату,кубу и.т.д. элементов О(n^2), О(n^3)... тоже простая.
Официально можно определить класс "простых задач" P как задачи, решаемые за полиномиальное время.
Но оказывается, что большинство прикладных задач,которые стоят перед программистами решаются за время ,пропорциональное степенной функции EXP(n),то есть "сложные". Однако, то что мы не знаем простого решения задачи, не означает что его не существует.
Сейчас я вынужден сделать пасс руками, чтоб не углубляться в математикуи и определить сложные задачи без обьяснения.
Ученые заметили, что все задачи,которые мы можем решить, можно разделить на два больших класса- задачи проверки: если вам дали решение, проверить является ли это решение верным (задачи простые) и задачи нахождения ответа(задачи возможно "сложные").
Класс NP можно неформально определить,как класс задач, для которых проверка ответа занимает полиномиальное время.
Понятно,что задача из класса P принадлежит классу NP. Oднако вопрос тысячелетия: есть ли задача, которую нельзя решить за полиномиальное время или действительно ли решение задачи проверить не легче, чем его отыскать.
Вопрос о равенстве классов P и NP очен важен.
Например современная криптография базируется на предположении что расшифровка сообщения это задача поиска ответа- то есть из класса NP,а вот расшифровка сообщения,когда ты знаешь ключ -это задача проверки то есть P.
Если эти два класса равны, то расшифровать сообщение имея пароль и не имея одинаково легко.И тогда вся теория криптографии не имеет смысла.
И в заключении- Математический институт Клея даёт миллион долларов тому,кто сможет доказать неравенство классов (P!=NP)?.
так чт, можете попробовать.
Обработка языков, обработка изображенй, искуственный интеллект и нейронные сети,криптология,биоинформатика.
Казалось,что вот-вот и компьютеры смогут делать всё.
Фантасты начинают обсуждать этические проблеммы связаные с "поумневшими машинами". Появляются первые страшилки о восстаниях машин.
Но тут, на волне всеобщей эйфории к ученым приходит некое понимание, что не всё так просто. Если до изобретения "программ" задачей программистов было "решить задачу", то сейчас на первое место выходит "решить задачу быстро и эффективно".
Вот простой пример: есть телефонный справочник миллионного города, где имена записаны по алфавиту.
Для того, чтоб найти телефон конкретного человека, можно начать просматривать справочник от начальной строчки по порядку, пока не найдем нужного человека. Тогда для того чтоб позвонить Яромиру Ягру нам понадобится просмотреть около миллиона строчек. С другй стороны, если мы откроем справочник ровно посередине и посмотрим, дошли ли мы до нужной буквы, а потом станем проверять только ту половину, в которой должна быть наша строчка, то нам понадобится всего около 10 таких проверок.
То есть существуют алгоритмы, которые решают задачу эффективнее чем другие алгоритмы.
И, конечно же, встал вопрос: " А все ли задачи можно решить одинаково быстро?" К сожалению, ответ на этот вопрос оказался сложнее, чем думали.
Так родилась теория сложности алгоритмов.
Не вдаваясь в математические подробности, можно сказать, что все алгоритмы можно разделить на классы, в которых количество работы пропорционально величине обьекта, с которым они работают.
Так,например, поиск телефона в телефонной книге относится к классу O(log n),потому что поиск занимает время, пропорциональное логарифму от количества телефонов.
А вот ,например распечатать телефонный справочник займет время пропорциональное (линейное) количеству телефонов, потому что каждый телефон мы должны "прочитать" хотябы один раз.
Теперь перейдем к очень важному вопросу.
существуют ли задачи "простые" и сложные".
Под простыми задачами я подразумеваю задачи,которые компьютер сможет решить за разумное время: день , месяц, год.
Если на решение задачи компьютеру понадобятся миллионы лет, то это задача "сложная".
Задача, которую алгоритм решает за время пропорциональное количеству элементов О(n)- простая. И задача пропорциональная квадрату,кубу и.т.д. элементов О(n^2), О(n^3)... тоже простая.
Официально можно определить класс "простых задач" P как задачи, решаемые за полиномиальное время.
Но оказывается, что большинство прикладных задач,которые стоят перед программистами решаются за время ,пропорциональное степенной функции EXP(n),то есть "сложные". Однако, то что мы не знаем простого решения задачи, не означает что его не существует.
Сейчас я вынужден сделать пасс руками, чтоб не углубляться в математикуи и определить сложные задачи без обьяснения.
Ученые заметили, что все задачи,которые мы можем решить, можно разделить на два больших класса- задачи проверки: если вам дали решение, проверить является ли это решение верным (задачи простые) и задачи нахождения ответа(задачи возможно "сложные").
Класс NP можно неформально определить,как класс задач, для которых проверка ответа занимает полиномиальное время.
Понятно,что задача из класса P принадлежит классу NP. Oднако вопрос тысячелетия: есть ли задача, которую нельзя решить за полиномиальное время или действительно ли решение задачи проверить не легче, чем его отыскать.
Вопрос о равенстве классов P и NP очен важен.
Например современная криптография базируется на предположении что расшифровка сообщения это задача поиска ответа- то есть из класса NP,а вот расшифровка сообщения,когда ты знаешь ключ -это задача проверки то есть P.
Если эти два класса равны, то расшифровать сообщение имея пароль и не имея одинаково легко.И тогда вся теория криптографии не имеет смысла.
И в заключении- Математический институт Клея даёт миллион долларов тому,кто сможет доказать неравенство классов (P!=NP)?.
так чт, можете попробовать.