
EITC/IS/CCTF Computational Complexity Theory Fundamentals - гэта еўрапейская праграма сертыфікацыі ІТ па тэарэтычных аспектах асноў інфарматыкі, якія таксама з'яўляюцца асновай класічнай асіметрычнай крыптаграфіі з адкрытым ключом, якая шырока выкарыстоўваецца ў Інтэрнэце.
Вучэбная праграма EITC/IS/CCTF Computational Complexity Theory Fundamentals ахоплівае тэарэтычныя веды аб асновах інфарматыкі і вылічальных мадэлях на аснове такіх асноўных паняццяў, як дэтэрмінаваныя і недэтэрмінаваныя канечныя аўтаматы, звычайныя мовы, кантэкстна-свабодная граматыка і тэорыя моў, тэорыя аўтаматаў, Цьюрынг Машыны, вырашальнасць праблем, рэкурсія, логіка і складанасць алгарытмікі для фундаментальных прыкладанняў бяспекі ў межах наступная структура, якая ахоплівае ўсёабдымную і структураваную навучальную праграму сертыфікацыі EITCI, матэрыялы для саманавучання, падмацаваныя спасылкамі на відэадыдактычны кантэнт з адкрытым доступам у якасці асновы для падрыхтоўкі да атрымання гэтага сертыфіката EITC шляхам здачы адпаведнага экзамену.
Вылічальная складанасць алгарытму - гэта колькасць рэсурсаў, неабходных для яго працы. Асаблівая ўвага надаецца рэсурсам часу і памяці. Складанасць задачы вызначаецца як складанасць найлепшых алгарытмаў яе рашэння. Аналіз алгарытмаў - гэта вывучэнне складанасці відавочна зададзеных алгарытмаў, тады як тэорыя складанасці вылічэнняў - гэта вывучэнне складанасці рашэння задач з найбольш вядомымі алгарытмамі. Абедзве вобласці пераплятаюцца, таму што складанасць алгарытму заўсёды з'яўляецца верхнім абмежаваннем складанасці задачы, якую ён вырашае. Акрамя таго, часта неабходна параўнаць складанасць пэўнага алгарытму са складанасцю задачы, якую трэба вырашыць пры пабудове эфектыўных алгарытмаў. У большасці выпадкаў адзіная даступная інфармацыя аб складанасці праблемы заключаецца ў тым, што яна меншая, чым складанасць найбольш эфектыўных вядомых метадаў. У выніку існуе шмат супадзенняў паміж аналізам алгарытмаў і тэорыяй складанасці.
Тэорыя складанасці гуляе важную ролю не толькі ў асновах вылічальных мадэляў як асновы інфарматыкі, але і ў асновах класічнай асіметрычнай крыптаграфіі (так званай крыптаграфіі з адкрытым ключом), якая шырока распаўсюджваецца ў сучасных сетках, асабліва ў Інтэрнэце. Шыфраванне з адкрытым ключом заснавана на вылічальнай цяжкасці некаторых асіметрычных матэматычных задач, такіх як, напрыклад, разкладанне вялікіх лікаў на простыя множнікі (гэта аперацыя з'яўляецца складанай праблемай у класіфікацыі тэорыі складанасці, таму што не існуе вядомых эфектыўных класічных алгарытмаў для вырашэння гэта з рэсурсамі, якія маштабуюцца палінаміальна, а не экспанентна з павелічэннем памеру ўваходных дадзеных задачы, што ў адрозненне ад вельмі простай зваротнай аперацыі множання на вядомыя простыя множнікі для атрымання першапачатковага вялікага ліку). Выкарыстоўваючы гэтую асіметрыю ў архітэктуры крыптаграфіі з адкрытым ключом (вызначаючы вылічальна асіметрычную сувязь паміж адкрытым ключом, які можна лёгка вылічыць з прыватнага ключа, у той час як прыватны ключ не можа быць лёгка камп'ютэрны з адкрытага ключа, можна публічна абвясціць адкрыты ключ і дазволіць іншым бакам сувязі выкарыстоўваць яго для асіметрычнага шыфравання даных, якія потым могуць быць расшыфраваныя толькі з дапамогай спалучанага закрытага ключа, недаступнага вылічальна трэцім асобам, што робіць сувязь бяспечнай).
Тэорыя складанасці вылічэнняў была распрацавана ў асноўным на аснове дасягненняў піянераў інфарматыкі і алгарытмікі, такіх як Алан Ц'юрынг, чыя праца мела вырашальнае значэнне для ўзлому шыфра Enigma нацысцкай Германіі, які адыграў вялікую ролю ў перамогі саюзнікаў у Другой сусветнай вайне. Крыптааналіз, накіраваны на распрацоўку і аўтаматызацыю вылічальных працэсаў аналізу даных (у асноўным зашыфраванай камунікацыі) з мэтай выяўлення схаванай інфармацыі, быў выкарыстаны для ўзлому крыптаграфічных сістэм і атрымання доступу да змесціва зашыфраванай сувязі, як правіла, мае ваеннае стратэгічнае значэнне. Гэта быў таксама крыптааналіз, які каталізаваў распрацоўку першых сучасных кампутараў (якія першапачаткова былі ўжытыя для стратэгічнай мэты ўзлому кода). Брытанскаму Colossus (які лічыцца першым сучасным электронным і праграмным камп'ютарам) папярэднічала польская «бомба», электронная вылічальная прылада, спраектаваная Марыянам Рэеўскім для ўзлому шыфраў 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-машыны) з'яўляюцца папулярнай парадыгмай для мадэлявання рэальных кампутараў.
Калі мадэль вылічэнняў не вызначана, звычайна мяркуецца шматстужковая машына Цьюрынга. На шматстужковых машынах Цьюрынга часовая складанасць такая ж, як і на машынах з аператыўнай памяці для большасці алгарытмаў, хоць для дасягнення гэтай эквівалентнасці можа спатрэбіцца значная ўвага да таго, як дадзеныя захоўваюцца ў памяці.
Розныя выбары могуць быць зроблены на некаторых этапах вылічэнняў у недэтэрмінаванай мадэлі вылічэнняў, напрыклад, у недэтэрмінаваных машынах Цьюрынга. У тэорыі складанасці ўсе магчымыя варыянты разглядаюцца адначасова, а недэтэрмінаваная часовая складанасць - гэта колькасць часу, неабходнага, калі заўсёды робяцца лепшыя выбары. Іншымі словамі, вылічэнні выконваюцца адначасова на столькіх (ідэнтычных) працэсарах, колькі патрабуецца, а недэтэрмінаваны час вылічэнняў - гэта час, затрачаны першым працэсарам на завяршэнне вылічэнняў. Гэты паралелізм можа быць выкарыстаны ў квантавых вылічэннях з дапамогай накладзеных пераблытаных станаў пры запуску спецыялізаваных квантавых алгарытмаў, такіх як, напрыклад, разкладанне дробных цэлых лікаў Шора на множнікі.
Нават калі такая мадэль вылічэнняў у цяперашні час невыканальная, яна мае тэарэтычнае значэнне, асабліва ў дачыненні да праблемы P = NP, у якой задаецца пытанне, ці класы складанасці, атрыманыя з выкарыстаннем «паліномнага часу» і «недэтэрмінаванага паліномнага часу» ў якасці найменшага верхняга межы аднолькавыя. На дэтэрмінаваным кампутары мадэляванне NP-алгарытму патрабуе «экспанентнага часу». Калі задача можа быць вырашана за паліномны час у недэтэрмінаванай сістэме, яна належыць да класа складанасці NP. Калі праблема знаходзіцца ў NP і не прасцей, чым любая іншая задача NP, яна называецца NP-поўнай. Задача Ранца, задача камаўнічага і задача булева выканальнасці - усё гэта NP-поўныя камбінаторныя задачы. Найбольш вядомы алгарытм мае экспанентную складанасць для ўсіх гэтых задач. Калі любую з гэтых задач можна было б вырашыць за паліномны час на дэтэрмінаванай машыне, то ўсе задачы NP таксама можна было б вырашыць за паліномны час, і P = NP было б усталявана. Па стане на 2017 год шырока прынята лічыць, што P NP, маючы на ўвазе, што горшыя сітуацыі з праблемамі NP прынцыпова цяжкія для вырашэння, г.зн. займаюць значна больш часу, чым любы магчымы прамежак часу (дзесяцігоддзяў), улічваючы цікавыя даўжыні ўваходных дадзеных.
Паралельныя і размеркаваныя вылічэнні
Паралельныя і размеркаваныя вылічэнні ўключаюць дзяленне апрацоўкі на некалькі працэсараў, якія працуюць адначасова. Прынцыповым адрозненнем паміж рознымі мадэлямі з'яўляецца метад перадачы дадзеных паміж працэсарамі. Перадача даных паміж працэсарамі, як правіла, вельмі хуткая пры паралельных вылічэннях, у той час як перадача даных паміж працэсарамі ў размеркаваных вылічэннях ажыццяўляецца па сетцы і, такім чынам, істотна павольней.
Вылічэнне на N працэсарах займае, па меншай меры, частку N часу, якое займае адзін працэсар. На самай справе, паколькі некаторыя падзадачы не могуць быць паралелізаваны, а некаторым працэсарам, магчыма, прыйдзецца чакаць выніку ад іншага працэсара, гэта тэарэтычна ідэальнае абмежаванне ніколі не будзе дасягнута.
Такім чынам, ключавая праблема складанасці заключаецца ў распрацоўцы алгарытмаў, каб здабытак часу вылічэнняў на колькасць працэсараў быў як мага бліжэй да часу, неабходнага для выканання таго ж вылічэння на адным працэсары.
Квантавыя вылічэнні
Квантавы камп’ютар — гэта камп’ютар з мадэллю вылічэнняў, заснаванай на квантавай механіцы. Тэзіс Чэрча-Цьюрынга верны для квантавых кампутараў, маючы на ўвазе, што любая праблема, якую можа вырашыць квантавы кампутар, таксама можа быць вырашана машынай Цьюрынга. Аднак некаторыя задачы тэарэтычна могуць быць вырашаны з дапамогай квантавага кампутара, а не класічнага кампутара са значна меншай часовай складанасцю. Пакуль што гэта строга тэарэтычна, бо ніхто не ведае, як распрацаваць практычны квантавы кампутар.
Квантавая тэорыя складанасці была створана для даследавання розных тыпаў праблем, якія могуць быць вырашаны квантавымі кампутарамі. Ён выкарыстоўваецца ў постквантавай крыптаграфіі, якая ўяўляе сабой працэс стварэння крыптаграфічных пратаколаў, устойлівых да квантавых кампутарных нападаў.
Складанасць задачы (ніжнія межы)
Невялікая колькасць складанасці алгарытмаў, якія могуць вырашыць праблему, у тым ліку нераскрытых метадаў, - гэта складанасць задачы. У выніку складанасць задачы роўная складанасці любога алгарытму, які яе вырашае.
У выніку любая складанасць, зададзеная ў вялікім абазначэнні O, уяўляе складанасць як алгарытму, так і спадарожнай задачы.
З іншага боку, атрымаць нетрывіяльныя ніжнія межы складанасці пытання часта бывае складана, і для гэтага існуе некалькі стратэгій.
Для таго, каб вырашыць большасць праблем, усе ўваходныя даныя павінны быць прачытаны, што займае час, прапарцыйнае велічыні дадзеных. У выніку такія задачы маюць прынамсі лінейную складанасць, або, у вялікіх амегах, складанасць Ω(n).
Некаторыя задачы, напрыклад, па кампутарнай алгебры і вылічальнай алгебраічнай геаметрыі, маюць вельмі вялікія рашэнні. Паколькі вывад павінен быць запісаны, складанасць абмяжоўваецца максімальным памерам вываду.
Колькасць параўнанняў, неабходных для алгарытму сартавання, мае нелінейную ніжнюю мяжу Ω(nlogn). У выніку лепшыя алгарытмы сартавання з'яўляюцца найбольш эфектыўнымі, паколькі іх складанасць складае O(nlogn). Справа ў тым, што ёсць п! спосабаў арганізацыі п рэчаў прыводзіць да гэтай ніжняй мяжы. Таму што кожнае параўнанне падзяляе гэты збор н! замовы на дзве часткі, колькасць 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 спасылаецца на дыдактычныя матэрыялы з адкрытым доступам у выглядзе відэа. Працэс навучання падзелены на пакрокавую структуру (праграмы -> урокі -> тэмы), якая ахоплівае адпаведныя часткі вучэбнага плана. Удзельнікі могуць атрымаць доступ да адказаў і задаць больш актуальныя пытанні ў раздзеле "Пытанні і адказы" інтэрфейсу электроннага навучання па тэме праграмы EITC, якая зараз развіваецца. Прамыя і неабмежаваныя кансультацыі з экспертамі па дамене таксама даступныя праз інтэграваную сістэму абмену паведамленнямі ў Інтэрнэце, а таксама праз кантактную форму.
Падрабязна пра працэдуру сертыфікацыі глядзіце Як гэта працуе?.
Асноўныя дапаможныя матэрыялы для чытання
С. Арора, Б. Барак, Вылічальная складанасць: сучасны падыход
https://theory.cs.princeton.edu/complexity/book.pdf
Дапаможныя матэрыялы для сярэдняй школы
О. Голдрайх, Уводзіны ў тэорыю складанасці:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
Дапаможныя матэрыялы для чытання па дыскрэтнай матэматыцы
Дж. Аснес, Заўвагі па дыскрэтнай матэматыцы:
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 – пашыраная версія з пытаннямі для агляду