EITC/IS/CCTF Computational Complexity Theory Fundamentals е европейската програма за ИТ сертифициране върху теоретичните аспекти на основите на компютърните науки, които също са основа на класическата асиметрична криптография с публичен ключ, широко използвана в Интернет.
Учебната програма на EITC/IS/CCTF Основи на теорията на изчислителната сложност обхваща теоретични знания за основите на компютърните науки и изчислителните модели върху основни понятия като детерминирани и недетерминирани машини с крайни състояния, регулярни езици, свободни от контекста граматици и теория на езиците, теория на автоматите, Тюринг Машини, разрешаване на проблемите, рекурсия, логика и сложност на алгоритмите за фундаментални приложения за сигурност в рамките на следната структура, включваща изчерпателно видеодидактическо съдържание като референция за това EITC сертифициране.
Изчислителната сложност на алгоритъма е количеството ресурси, необходими за неговата работа. На ресурсите за време и памет се отделя специално внимание. Сложността на даден проблем се определя като сложността на най-добрите алгоритми за решаването му. Анализът на алгоритмите е изследване на сложността на изрично дадени алгоритми, докато теорията на изчислителната сложност е изследване на сложността на решенията на проблеми с най-известните алгоритми. И двата домейна са преплетени, тъй като сложността на алгоритъма винаги е горно ограничение за сложността на проблема, който решава. Освен това, често е необходимо да се сравнява сложността на определен алгоритъм със сложността на проблема, който трябва да бъде решен, докато се конструират ефективни алгоритми. В повечето случаи единствената налична информация относно трудността на проблема е, че той е по-малък от сложността на най-ефективните известни техники. В резултат на това има много припокриване между анализа на алгоритмите и теорията на сложността.
Теорията на сложността играе важна роля не само в основите на изчислителните модели като основа за компютърните науки, но и в основите на класическата асиметрична криптография (т.нар. криптография с публичен ключ), която е широко разпространена в съвременните мрежи, особено в Интернет. Шифроването с публичен ключ се основава на изчислителна трудност на определени асиметрични математически проблеми, като например разлагане на големи числа в неговите прости фактори (тази операция е труден проблем в класификацията на теорията на сложността, тъй като не са известни ефективни класически алгоритми за решаване то с ресурсите, които се мащабират полиномно, а не експоненциално с увеличаването на входния размер на проблема, което е в контраст с много проста обратна операция на умножение по известни прости множители, за да се получи оригиналното голямо число). Използвайки тази асиметрия в архитектура на криптографията с публичен ключ (чрез дефиниране на изчислително асиметрична връзка между публичния ключ, който може лесно да бъде изчислен от частен ключ, докато частният ключ не може лесно да бъде компютър от публичен ключ, човек може публично оповестяват публичния ключ и позволяват на други комуникационни страни да го използват за асиметрично криптиране на данни, които след това могат да бъдат декриптирани само със свързания частен ключ, който не е достъпен изчислително за трети страни, което прави комуникацията сигурна).
Теорията на изчислителната сложност е разработена главно върху постиженията на пионерите в компютърните науки и алгоритмите, като Алън Тюринг, чиято работа е от решаващо значение за разбиването на шифъра Enigma на нацистка Германия, който изигра дълбока роля в съюзниците, спечелени във Втората световна война. Криптоанализът, насочен към разработване и автоматизиране на изчислителните процеси за анализиране на данни (главно криптирана комуникация) с цел разкриване на скритата информация, беше използван за нарушаване на криптографските системи и получаване на достъп до съдържанието на криптирана комуникация, обикновено от стратегическо военно значение. Също така криптоанализът катализира развитието на първите съвременни компютри (които първоначално бяха приложени за стратегическа цел за разбиване на код). Британският Колос (считан за първия модерен електронен и програмен компютър) е предшестван от полската „бомба“, електронно изчислително устройство, проектирано от Мариан Реевски за подпомагане на разбиване на шифри на Enigma, и предадено на Великобритания от полското разузнаване заедно с заловената германска криптираща машина Enigma, след като Полша е нападната от Германия през 1939 г. На базата на това устройство Алън Тюринг разработи своя по-усъвършенстван аналог за успешно прекъсване на немската криптирана комуникация, която по-късно е разработена в съвременни компютри.
Тъй като количеството ресурси, необходими за изпълнение на алгоритъм, варира в зависимост от размера на входа, сложността обикновено се изразява като функция f(n), където n е размерът на входа, а f(n) е или сложността в най-лошия случай ( максималното количество ресурси, необходими за всички входове с размер n) или средната сложност на случая (средната стойност на количеството ресурси за всички входни данни с размер n). Броят на необходимите елементарни операции на вход с размер n обикновено се посочва като времева сложност, където се смята, че елементарните операции отнемат постоянно време на конкретен компютър и се променят само с постоянен коефициент, когато се изпълняват на различна машина. Количеството памет, изисквано от алгоритъм за вход с размер n, е известно като сложност на пространството.
Времето е най-често разглежданият ресурс. Когато терминът „сложност“ се използва без квалификатор, той обикновено се отнася до сложността на времето.
Традиционните единици за време (секунди, минути и т.н.) не се използват в теорията на сложността, тъй като са твърде зависими от избрания компютър и напредъка на технологиите. Например, днес компютърът може да изпълнява алгоритъм значително по-бързо от компютър от 1960-те години на миналия век, но това се дължи по-скоро на технологични пробиви в компютърния хардуер, отколкото на присъщо качество на алгоритъма. Целта на теорията на сложността е да определи количествено присъщите времеви нужди на алгоритмите или основните времеви ограничения, които един алгоритъм би наложил на всеки компютър. Това се постига чрез броене на колко основни операции се извършват по време на изчислението. Тези процедури обикновено се наричат стъпки, тъй като се счита, че отнемат постоянно време на определена машина (т.е. те не се влияят от количеството на входа).
Друг важен ресурс е количеството компютърна памет, необходима за изпълнение на алгоритми.
Друг често използван ресурс е количеството аритметични операции. В този сценарий се използва терминът „аритметична сложност“. Времевата сложност обикновено е продукт на аритметичната сложност с постоянен коефициент, ако е известно горно ограничение за размера на двоичното представяне на числата, които се появяват по време на изчисление.
Размерът на използваните по време на изчисление цели числа не е ограничен за много методи и е нереалистично да се приеме, че аритметичните операции изискват фиксиран период от време. В резултат на това времевата сложност, известна още като битова сложност, може да бъде значително по-висока от аритметичната сложност. Аритметичната трудност при изчисляване на детерминанта на матрица с цели числа nn, например, е O(n^3) за стандартни техники (елиминиране на Гаус). Тъй като размерът на коефициентите може да се разшири експоненциално по време на изчислението, битовата сложност на същите методи е експоненциална в n. Ако тези техники се използват във връзка с мултимодулна аритметика, сложността на битовете може да бъде намалена до O(n^4).
Формално битовата сложност се отнася до броя на операциите с битове, необходими за изпълнение на алгоритъм. Той е равен на времевата сложност до постоянен фактор в повечето изчислителни парадигми. Броят на операциите върху машинните думи, изисквани от компютрите, е пропорционален на сложността на битовете. Следователно за реалистичните модели на изчисление времевата сложност и битовата сложност са идентични.
Ресурсът, който често се взема предвид при сортиране и търсене, е количеството сравнения на записи. Ако данните са добре подредени, това е добър индикатор за сложността на времето.
На всички потенциални входове преброяването на броя на стъпките в алгоритъма е невъзможно. Тъй като сложността на входа нараства с неговия размер, той обикновено се представя като функция на размера на входа n (в битове) и така сложността е функция на n. За входове със същия размер обаче сложността на алгоритъма може да варира значително. В резултат на това рутинно се използват различни функции за сложност.
Сложността в най-лошия случай е сумата от цялата сложност за всички входове с размер n, докато сложността на средния случай е сумата от цялата сложност за всички входове с размер n (това има смисъл, тъй като броят на възможните входове с даден размер е краен). Когато терминът „сложност” се използва без допълнително дефиниране, се взема предвид времевата сложност в най-лошия случай.
Известно е, че сложността на най-лошия и средния случай е трудно да се изчисли правилно. Освен това, тези точни стойности имат малко практическо приложение, тъй като всяка промяна в машината или парадигмата на изчисление би променила леко сложността. Освен това, използването на ресурси не е от решаващо значение за малки стойности на n, поради което лекотата на изпълнение често е по-привлекателна от ниската сложност за малки n.
Поради тези причини най-голямо внимание се отделя на поведението на сложността при високо n, тоест асимптотичното й поведение, когато n се приближава до безкрайността. В резултат на това, голяма O нотация обикновено се използва за обозначаване на сложността.
Изчислителни модели
Изборът на изчислителен модел, който се състои от определяне на основните операции, които се извършват за единица време, е от решаващо значение за определяне на сложността. Това понякога се нарича многолентова машина на Тюринг, когато изчислителната парадигма не е описана конкретно.
Детерминистичен модел на изчисление е този, при който следващите състояния на машината и операциите, които трябва да бъдат извършени, са изцяло определени от предишното състояние. Рекурсивните функции, ламбда изчислението и машините на Тюринг бяха първите детерминирани модели. Машините с произволен достъп (известни също като RAM машини) са популярна парадигма за симулиране на компютри в реалния свят.
Когато изчислителният модел не е дефиниран, обикновено се приема многолентова машина на Тюринг. При многолентови машини на Тюринг времевата сложност е същата като при RAM машините за повечето алгоритми, макар че може да се изисква значително внимание в начина, по който данните се съхраняват в паметта, за да се постигне тази еквивалентност.
Различни избори могат да бъдат направени на някои стъпки от изчислението в недетерминиран модел на изчисление, като например недетерминирани машини на Тюринг. В теорията на сложността всички възможни опции се разглеждат едновременно, а недетерминираната времева сложност е количеството време, необходимо, когато винаги се правят най-добрите избори. Казано по друг начин, изчислението се извършва едновременно на толкова (идентични) процесори, колкото са необходими, а недетерминираното време за изчисление е времето, необходимо на първия процесор, за да завърши изчислението. Този паралелизъм може да се използва в квантовите изчисления чрез използване на насложени заплетени състояния, когато се изпълняват специализирани квантови алгоритми, като например факторизацията на Шор на малки цели числа.
Дори ако такъв изчислителен модел в момента не е практически приложим, той има теоретично значение, особено във връзка с проблема P = NP, който пита дали класовете на сложност, произведени чрез използване на „полиномно време“ и „недетерминирано полиномно време“ като най-малка горна границите са еднакви. На детерминиран компютър симулирането на NP-алгоритъм изисква „експоненциално време“. Ако дадена задача може да бъде решена за полиномно време на недетерминирана система, тя принадлежи към класа на трудност NP. Ако проблемът е в NP и не е по-лесен от всеки друг проблем с NP, се казва, че е NP-завършен. Проблемът с раницата, проблемът с пътуващия търговец и проблемът за булева задоволимост са всички NP-пълни комбинаторни проблеми. Най-известният алгоритъм има експоненциална сложност за всички тези проблеми. Ако някой от тези проблеми може да бъде решен за полиномиално време на детерминирана машина, тогава всички NP проблеми могат да бъдат решени и за полиномно време и P = NP ще бъде установено. От 2017 г. широко се приема, че P NP, което предполага, че най-лошите ситуации на NP проблеми са фундаментално трудни за решаване, т.е. отнемат много повече време от всеки възможен период от време (десетилетия), като се имат предвид интересни входни дължини.
Паралелни и разпределени изчисления
Паралелните и разпределени изчисления включват разделяне на обработка между множество процесори, които работят едновременно. Основната разлика между различните модели е методът за изпращане на данни между процесорите. Предаването на данни между процесорите обикновено е много бързо при паралелно изчисление, докато преносът на данни между процесорите при разпределените изчисления се извършва в мрежа и по този начин е значително по-бавен.
Едно изчисление на N процесора отнема поне частното по N от времето, което отнема на един процесор. В действителност, тъй като някои подзадачи не могат да бъдат паралелизирани и някои процесори може да трябва да изчакат резултат от друг процесор, тази теоретично идеална граница никога няма да бъде постигната.
По този начин основният проблем със сложността е да се разработят алгоритми, така че продуктът на времето за изчисление на броя на процесорите да е възможно най-близо до времето, необходимо за извършване на същото изчисление на един процесор.
Квантово изчисление
Квантовият компютър е компютър с изчислителен модел, базиран на квантовата механика. Тезата на Чърч-Тюринг важи за квантовите компютри, което предполага, че всеки проблем, който може да реши квантовият компютър, може да бъде решен и от машина на Тюринг. Въпреки това, някои задачи теоретично могат да бъдат решени с помощта на квантов компютър, а не на класически компютър със значително по-ниска времева сложност. За момента това е строго теоретично, тъй като никой не знае как да разработи практически квантов компютър.
Теорията на квантовата сложност е създадена, за да изследва различните видове проблеми, които могат да бъдат решени от квантовите компютри. Използва се в пост-квантовата криптография, която е процес на създаване на криптографски протоколи, които са устойчиви на квантови компютърни атаки.
Сложност на проблема (долни граници)
Най-малкото от сложността на алгоритмите, които могат да решат проблема, включително неоткрити техники, е сложността на проблема. В резултат на това сложността на даден проблем е равна на сложността на всеки алгоритъм, който го решава.
В резултат на това всяка сложност, дадена в голяма O нотация, представлява сложност както на алгоритъма, така и на придружаващия го проблем.
От друга страна, получаването на нетривиални долни граници на сложността на проблема често е трудно и има малко стратегии за това.
За да се решат повечето проблеми, всички входни данни трябва да бъдат прочетени, което отнема време, пропорционално на големината на данните. В резултат на това такива проблеми имат най-малко линейна сложност или, в голяма омега нотация, сложност от Ω(n).
Някои проблеми, като тези в компютърната алгебра и изчислителната алгебрична геометрия, имат много големи решения. Тъй като изходът трябва да бъде написан, сложността е ограничена от максималния размер на изхода.
Броят на сравненията, необходими за алгоритъм за сортиране, има нелинейна долна граница на Ω(nlogn). В резултат на това най-добрите алгоритми за сортиране са най-ефективни, тъй като тяхната сложност е O(nlogn). Фактът, че има n! начини за организиране на n неща води до тази долна граница. Защото всяко сравнение разделя тази колекция от n! поръчки на две части, броят на N сравнения, необходими за разграничаване на всички поръчки, трябва да бъде 2N > n!, което предполага O(nlogn) по формулата на Стърлинг.
Свеждането на проблема до друг проблем е обща стратегия за получаване на ограничения за намалена сложност.
Разработване на алгоритъм
Оценяването на сложността на алгоритъма е важен елемент от процеса на проектиране, тъй като предоставя полезна информация за производителността, която може да се очаква.
Често недоразумение е, че в резултат на закона на Мур, който предвижда експоненциален растеж на съвременните компютърни мощности, оценката на сложността на алгоритмите ще стане по-малко уместна. Това е неправилно, тъй като увеличената мощност позволява обработка на огромни количества данни (големи данни). Например, всеки алгоритъм трябва да функционира добре за по-малко от секунда, когато сортира по азбучен ред списък от няколко стотици записи, като например библиографията на книга. От друга страна, за един милион вписвания (например телефонни номера на голям град), основните алгоритми, които изискват O(n2) сравнения, ще трябва да извършат трилион сравнения, което ще отнеме три часа при скорост 10 милион сравнения в секунда. Бързото сортиране и сортирането чрез сливане, от друга страна, изискват само nlogn сравнения (като средна сложност за първия, като сложност в най-лошия случай за втория). Това произвежда около 30,000,000 1,000,000 3 сравнения за n = 10 XNUMX XNUMX, което ще отнеме само XNUMX секунди при XNUMX милиона сравнения в секунда.
В резултат на това оценката на сложността може да позволи елиминирането на много неефективни алгоритми преди внедряването. Това може да се използва и за фина настройка на сложни алгоритми, без да се налага да се тестват всички възможни варианти. Изследването на сложността позволява фокусиране на усилията за повишаване на ефективността на дадена реализация чрез определяне на най-скъпите стъпки на сложен алгоритъм.
За да се запознаете в детайли с учебната програма за сертифициране, можете да разширите и анализирате таблицата по-долу.
Учебната програма за сертифициране на основите на теорията на изчислителната сложност на EITC/IS/CCTF препраща към дидактически материали с отворен достъп във видео форма. Процесът на обучение е разделен на структура стъпка по стъпка (програми -> уроци -> теми), обхващащи съответните части от учебната програма. Предоставят се и неограничени консултации с експерти по домейни.
За подробности относно процедурата за сертифициране проверете Как работи.
Основни помощни учебни материали за четене
С. Арора, Б. Барак, Изчислителна сложност: модерен подход
https://theory.cs.princeton.edu/complexity/book.pdf
Материали за четене на учебната програма за средно ниво
О. Голдрайх, Въведение в теорията на сложността:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Поддържащи учебни материали за четене по дискретна математика
J. Aspnes, Бележки по дискретна математика:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
Поддържащи учебни материали за четене по теория на графите
Р. Дистел, Теория на графите:
https://diestel-graph-theory.com/
Изтеглете пълните офлайн подготвителни материали за самообучение за програмата EITC/IS/CCTF Computational Complexity Theory Fundamentals в PDF файл
Подготвителни материали за EITC/IS/CCTF – стандартна версия
Подготвителни материали за EITC/IS/CCTF – разширена версия с въпроси за преглед