×
1 Выберыце сертыфікаты EITC/EITCA
2 Вучыцеся і здавайце онлайн-экзамены
3 Атрымайце сертыфікат навыкаў ІТ

Пацвердзіце свае ІТ-навыкі і кампетэнцыі ў адпаведнасці з Еўрапейскай рамкай ІТ-сертыфікацыі з любой кропкі свету цалкам онлайн.

Акадэмія EITCA

Стандарт атэстацыі лічбавых навыкаў Еўрапейскім інстытутам сертыфікацыі ІТ, накіраваны на падтрымку развіцця лічбавага грамадства

Увайдзіце ў свой уліковы запіс

СТВАРЫЦЬ КОШТ Забыліся пароль?

Забыліся пароль?

AAH, пачакайце, я ўспомніў!

СТВАРЫЦЬ КОШТ

УЖО ЁСЦЬ КОШТ?
ЕЎРАПЕЙСКАЯ IT СЕРТЫФІКАЦЫЙНАЯ АКАДЭМІЯ - ЗАСВЯДЖЕННЕ ВАШЫХ ПРАФЕСІЙНЫХ ВЫКАРЫСТАННЯЎ ДЫГІТАЛІ
  • ЗАРЭГІСТРАВАЦЦА
  • LOGIN
  • INFO

Акадэмія EITCA

Акадэмія EITCA

Еўрапейскі інстытут сертыфікацыі інфармацыйных тэхналогій - EITCI ASBL

Пастаўшчык сертыфікацыі

Інстытут EITCI ASBL

Брусэль, Еўрапейскі саюз

Кіруючая Еўрапейская сістэма ІТ-сертыфікацыі (EITC) у падтрымку ІТ-прафесіяналізму і лічбавага грамадства

  • СЕРТЫФІКАТ
    • Акадэміі EITCA
      • КАТАЛОГ АКАДЭМІІ EITCA<
      • ГРАФІКА КАМПУТАРНАЙ ГРАФІКА EITCA/CG
      • EITCA/ІНФАРМАЦЫЙНАЯ Бяспека
      • EITCA/BI ІНФАРМАЦЫЯ БІЗНЕСУ
      • KITY COMPETENCIES EITCA/KC
      • EITCA/EG E-ПРАВА
      • EITCA/WD ВЕБ-РАЗВІЦЦЁ
      • Штучны інтэлект EITCA/AI
    • Сертыфікаты EITC
      • КАТАЛОГ EITC CERTIFICATES<
      • СЕРТЫФІКАТЫ ГРАФІЧНЫХ ГРАФІКАЎ
      • СЕРТЫФІКАТЫ Вэб-дызайну
      • СЕРТЫФІКАТЫ 3D-дызайну
      • ОФІСНЫЯ СЕРТЫФІКАТЫ
      • СЕРТЫФІКАТ БІТКОЙНА
      • WORDPRESS СЕРТЫФІКАТ
      • АБЛАКАВЫ ПЛАТФОРМНЫ СЕРТЫФІКАТNEW
    • Сертыфікаты EITC
      • ІНТЭРНЕТ СЕРТЫФІКАТЫ
      • КРЫПТАГРАФІЧНЫЯ СЕРТЫФІКАТЫ
      • БІЗНЕС ІТ-СЕРТЫФІКАТЫ
      • СЕРТЫФІКАТЫ РАБОТЫ
      • СЕРТЫФІКАТЫ ПРАГРАММАННІ
      • СЕРТЫФІКАТ ДЫГІТАЛЬНАГА ПОРТРЭЙТА
      • СЕРТЫФІКАТЫ ВЕБ-РАЗВІЦЦЯ
      • СЕРТЫФІКАТЫ Глыбокага навучанняNEW
    • СЕРТЫФІКАТЫ ДЛЯ
      • ГРАМАДСКАЯ АДМІНІСТРАЦЫЯ ЕС
      • Настаўнікі і выхавальнікі
      • Прафесіяналы бяспекі
      • ДЫЗАЙНЕРЫ ГРАФІКІ І МАСТАКІ
      • Бізнэсоўцы і кіраўнікі
      • BLOKCHAIN ​​РАЗВІЦЦІ
      • ВЭБ-РАЗВІЦЦЁ
      • ЭКСПЕРТЫ АБЛАЧНАЙ ІІNEW
  • НОВЫЯ
  • СУБСІДЫЯ
  • ЯК ГЭТА ПРАЦУЕ
  •   IT ID
  • Аб
  • КАНТАКТ
  • Мой заказ
    Ваш бягучы заказ замоўлены.
EITCIINSTITUTE
CERTIFIED

Асновы тэорыі складанасці вылічэнняў EITC/IS/CCTF

by Акадэмія EITCA / Панядзелак, 03 мая 2021 / Апублікавана ў

Бягучы статус

Не залічаны
Зарэгіструйцеся ў гэтай праграме, каб атрымаць доступ

цана

€110.00

Пачатак працы

Запісацца на гэтую атэстацыю

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

Значок PDF Падрыхтоўчыя матэрыялы EITC/IS/CCTF – стандартная версія

Значок PDF Падрыхтоўчыя матэрыялы EITC/IS/CCTF – пашыраная версія з пытаннямі для агляду

Навучальны план праграмы сертыфікацыі

Увядзенне 1 Тэма
У вас пакуль няма доступу да гэтага кантэнту
Змест урока
0% завершана Крокі 0/1
Тэарэтычнае ўвядзенне
Канечныя дзяржаўныя машыны 6 Topics
У вас пакуль няма доступу да гэтага кантэнту
Змест урока
0% завершана Крокі 0/6
Увядзенне ў машыны з канчатковым станам
Прыклады машын з канчатковым станам
Аперацыі на звычайных мовах
Увядзенне ў недетерминированные машыны канчатковых станаў
Афіцыйнае вызначэнне недетерминированных машын канечнага стану
Эквівалентнасць дэтэрмінаваных і недетерминированных ФСМ
Рэгулярныя мовы 5 Topics
У вас пакуль няма доступу да гэтага кантэнту
Змест урока
0% завершана Крокі 0/5
Закрыццё рэгулярных аперацый
Рэгулярныя выразы
Эквівалентнасць рэгулярных выразаў і звычайных моў
Накачанне лемы для звычайных моў
Кароткі змест рэгулярных моў
Бясплатныя граматыкі і мовы 4 Topics
У вас пакуль няма доступу да гэтага кантэнту
Змест урока
0% завершана Крокі 0/4
Уводзіны ў бясплатныя граматыкі і мовы
Прыклады граматык без кантэксту
Віды свабодных моў кантэксту
Факты пра кантэкстныя свабодныя мовы
Мовы, якія адчуваюць кантэкст 3 Topics
У вас пакуль няма доступу да гэтага кантэнту
Змест урока
0% завершана Крокі 0/3
Нармальная форма Хомскага
Іерархія Хомскага і кантэкстныя мовы
Лемма аб помпах для КФЛ
Аўтаматы адціскання 3 Topics
У вас пакуль няма доступу да гэтага кантэнту
Змест урока
0% завершана Крокі 0/3
КПК: Аўтаматы націску
Эквівалентнасць CFG і PDA
Высновы з эквівалентнасці CFG і PDA
Машыны Цьюрынга 9 Topics
У вас пакуль няма доступу да гэтага кантэнту
Змест урока
0% завершана Крокі 0/9
Уводзіны ў машыны Цьюрынга
Прыклады машыны Цьюрынга
Вызначэнне ТМ і звязаных з імі моўных заняткаў
Тэзіс Царквы-Цюрынга
Тэхніка праграмавання машыны Цьюрынга
Шматслойныя машыны Цьюрынга
Недэтэрмінізм у машынах Цьюрынга
Машыны Цьюрынга як вырашальнікі задач
Перапісчыкі
Рашучасць 17 Topics
У вас пакуль няма доступу да гэтага кантэнту
Змест урока
0% завершана Крокі 0/17
Вырашальнасць і праблемы, якія вырашаюцца
Больш вырашальныя праблемы для DFA
Праблемы, якія тычацца моў без кантэксту
Універсальная машына Цьюрынга
Бясконцасць - незлічоная і незлічоная
Мовы, якія не пазнаюць Цьюрынга
Невырашальнасць праблемы спынення
Мова, якую Тьюрынг не пазнае
Скарачальнасць - метад доказу невырашальнасці
Праблема прыпынку - доказ скарачэннем
Ці прымае ТМ якія-небудзь радкі?
Вылічаныя функцыі
Эквівалентнасць машын Цьюрынга
Звядзенне адной мовы да іншай
Праблема перапіскі
Невырашальнасць PCP
Лінейныя звязаныя аўтаматы
Рэкурсія 5 Topics
У вас пакуль няма доступу да гэтага кантэнту
Змест урока
0% завершана Крокі 0/5
Праграма, якая друкуецца самастойна
Машына Цьюрынга, якая піша апісанне сябе
Тэарэма рэкурсіі
Вынікі тэарэмы рэкурсіі
Тэарэма фіксаванай кропкі
Логіка 4 Topics
У вас пакуль няма доступу да гэтага кантэнту
Змест урока
0% завершана Крокі 0/4
Логіка прэдыкатаў першага парадку - агляд
Праўда, сэнс і доказ
Праўдзівыя сцверджанні і даказальныя сцвярджэнні
Тэарэма незавершанасці Годэля
складанасць 8 Topics
У вас пакуль няма доступу да гэтага кантэнту
Змест урока
0% завершана Крокі 0/8
Складанасць часу і абазначэнне вялікіх значэнняў
Вылічэнне часу выканання алгарытму
Складанасць часу з рознымі вылічальнымі мадэлямі
Класы складанасці часу P і NP
Вызначэнне NP і мнагачленнай праверанасці
NP-паўната
Доказ таго, што SAT з'яўляецца NP поўным
Класы складанасці касмічнай прасторы
Асновы тэорыі складанасці вылічэнняў EITC/IS/CCTF
У вас пакуль няма доступу да гэтага кантэнту
Галоўная » Мой рахунак

цэнтр сертыфікацыі

Галоўная праграма
Увядзенне
Тэарэтычнае ўвядзенне
Канечныя дзяржаўныя машыны
Увядзенне ў машыны з канчатковым станам
Прыклады машын з канчатковым станам
Аперацыі на звычайных мовах
Увядзенне ў недетерминированные машыны канчатковых станаў
Афіцыйнае вызначэнне недетерминированных машын канечнага стану
Эквівалентнасць дэтэрмінаваных і недетерминированных ФСМ
Рэгулярныя мовы
Закрыццё рэгулярных аперацый
Рэгулярныя выразы
Эквівалентнасць рэгулярных выразаў і звычайных моў
Накачанне лемы для звычайных моў
Кароткі змест рэгулярных моў
Бясплатныя граматыкі і мовы
Уводзіны ў бясплатныя граматыкі і мовы
Прыклады граматык без кантэксту
Віды свабодных моў кантэксту
Факты пра кантэкстныя свабодныя мовы
Мовы, якія адчуваюць кантэкст
Нармальная форма Хомскага
Іерархія Хомскага і кантэкстныя мовы
Лемма аб помпах для КФЛ
Аўтаматы адціскання
КПК: Аўтаматы націску
Эквівалентнасць CFG і PDA
Высновы з эквівалентнасці CFG і PDA
Машыны Цьюрынга
Уводзіны ў машыны Цьюрынга
Прыклады машыны Цьюрынга
Вызначэнне ТМ і звязаных з імі моўных заняткаў
Тэзіс Царквы-Цюрынга
Тэхніка праграмавання машыны Цьюрынга
Шматслойныя машыны Цьюрынга
Недэтэрмінізм у машынах Цьюрынга
Машыны Цьюрынга як вырашальнікі задач
Перапісчыкі
Рашучасць
Вырашальнасць і праблемы, якія вырашаюцца
Больш вырашальныя праблемы для DFA
Праблемы, якія тычацца моў без кантэксту
Універсальная машына Цьюрынга
Бясконцасць - незлічоная і незлічоная
Мовы, якія не пазнаюць Цьюрынга
Невырашальнасць праблемы спынення
Мова, якую Тьюрынг не пазнае
Скарачальнасць - метад доказу невырашальнасці
Праблема прыпынку - доказ скарачэннем
Ці прымае ТМ якія-небудзь радкі?
Вылічаныя функцыі
Эквівалентнасць машын Цьюрынга
Звядзенне адной мовы да іншай
Праблема перапіскі
Невырашальнасць PCP
Лінейныя звязаныя аўтаматы
Рэкурсія
Праграма, якая друкуецца самастойна
Машына Цьюрынга, якая піша апісанне сябе
Тэарэма рэкурсіі
Вынікі тэарэмы рэкурсіі
Тэарэма фіксаванай кропкі
Логіка
Логіка прэдыкатаў першага парадку - агляд
Праўда, сэнс і доказ
Праўдзівыя сцверджанні і даказальныя сцвярджэнні
Тэарэма незавершанасці Годэля
складанасць
Складанасць часу і абазначэнне вялікіх значэнняў
Вылічэнне часу выканання алгарытму
Складанасць часу з рознымі вылічальнымі мадэлямі
Класы складанасці часу P і NP
Вызначэнне NP і мнагачленнай праверанасці
NP-паўната
Доказ таго, што SAT з'яўляецца NP поўным
Класы складанасці касмічнай прасторы
Асновы тэорыі складанасці вылічэнняў EITC/IS/CCTF

MENU USER

  • Мой рахунак

СЕРТЫФІКАТ КАТЭГОРЫЯ

  • Сертыфікацыя EITC (105)
  • Сертыфікацыя EITCA (9)

Што вы шукаеце?

  • Увядзенне
  • Як гэта працуе?
  • Акадэміі EITCA
  • Субсідыя EITCI DSJC
  • Поўны каталог EITC
  • ваш заказ
  • Рэкамендаваны
  •   IT ID
  • Водгукі EITCA (Сярэдняя публікацыя)
  • аб
  • Кантакт

Акадэмія EITCA з'яўляецца часткай Еўрапейскай сістэмы ІТ-сертыфікацыі

Еўрапейская структура ІТ-сертыфікацыі была створана ў 2008 годзе як заснаваны ў Еўропе і незалежны ад пастаўшчыка стандарт шырокадаступнай онлайн-сертыфікацыі лічбавых навыкаў і кампетэнцый у многіх галінах прафесійнай лічбавай спецыялізацыі. Структура EITC рэгулюецца Еўрапейскі інстытут сертыфікацыі ІТ (EITCI), некамерцыйны орган сертыфікацыі, які падтрымлівае рост інфармацыйнага грамадства і ліквідуе разрыў у лічбавых навыках у ЕС.

Права на атрыманне акадэміі EITCA 80% падтрымкі субсідый EITCI DSJC

80% платы за акадэмію EITCA субсідуецца пры залічэнні 10/5/2025

    Офіс сакратара Акадэміі EITCA

    Еўрапейскі інстытут сертыфікацыі ІТ ASBL
    Брусэль, Бэльгія, Эўразьвяз

    Аператар сістэмы сертыфікацыі EITC/EITCA
    Кіруючы Еўрапейскім стандартам ІТ-сертыфікацыі
    доступу Кантактная форма ці тэлефануйце па тэлефоне + 32 25887351

    Сачыце за EITCI на X
    Наведайце EITCA Academy на Facebook
    Узаемадзейнічайце з Акадэміяй EITCA на LinkedIn
    Глядзіце відэа EITCI і EITCA на YouTube

    Фінансуецца Еўрапейскім саюзам

    Фінансуецца за кошт Еўрапейскі фонд рэгіянальнага развіцця (ЕФРР) і Еўрапейскі сацыяльны фонд (ЕСФ) у серыі праектаў з 2007 года, у цяперашні час кіруецца Еўрапейскі інстытут сертыфікацыі ІТ (EITCI) З 2008

    Палітыка інфармацыйнай бяспекі | Палітыка DSRRM і GDPR | Палітыка абароны даных | Запіс дзеянняў па апрацоўцы | Палітыка HSE | Антыкарупцыйная палітыка | Сучасная палітыка рабства

    Аўтаматычны пераклад на вашу мову

    Умовы i Варункi | Палітыка прыватнасьці
    Акадэмія EITCA
    • Акадэмія EITCA ў сацыяльных медыя
    Акадэмія EITCA


    © 2008-2025  Еўрапейскі інстытут сертыфікацыі ІТ
    Брусэль, Бэльгія, Эўразьвяз

    TOP
    Чат са службай падтрымкі
    Чат са службай падтрымкі
    Пытанні, сумненні, праблемы? Мы тут, каб дапамагчы вам!
    Канец чата
    Падключэнне ...
    Ў вас ёсць якія-небудзь пытанні?
    Ў вас ёсць якія-небудзь пытанні?
    :
    :
    :
    паслаць
    Ў вас ёсць якія-небудзь пытанні?
    :
    :
    Пачаць чат
    Сеанс чата скончыўся. Дзякуй!
    Ацаніце падтрымку, якую вы атрымалі.
    добра Дрэнны