Теорија израчунљивости

Из Википедије, слободне енциклопедије

Теорија израчунљивости је грана рачунарства која разматра могу ли се и с којом ефикасношћу решити проблеми користећи рачунар. Поље је подељено у две главне гране: теорију израчунљивости и теорију комплексности, с тим да обе гране изучавају формалне моделе рачунања.

Како би ригорозно проучавали рачунање, рачунарски научници користе математичке апстракције - моделе рачунања. Неколико је формулација у употреби, али најчешће испитивана је Турингова машина. Турингова машина се може схватити као лични рачунар опремљен меморијом бесконачног капацитета, иако може меморији приступати у малим дискретним деловима. Информатичари проучавају Турингову машину јер је она једноставна за формулацију и може бити анализирана и коришћена у доказивању резултата јер представља оно што многи сматрају најмоћнијим могућим „разумним“ моделом рачунања. Иако се захтев за меморијом бесконачног капацитета може схватити као нефизикалан, за сваки стварно решен проблем Туринговом машином коришћена меморија ће увек бити коначна, па сваки проблем који реши Турингова машина може решити и персонални рачунар са довољно уграђене меморије.

Теорија израчунљивости[уреди]

Теорија израчунљивости се примарно бави питањем је ли проблем уопште решив на рачунару. Проблем заустављања је један од најважнијих резултата у теорији израчунљивости, јер представља пример конкретног проблема којег је и лако формулисати и немогуће решити користећи Турингову машину. Већи је део теорије израчунљивости изграђен око резултата проблема заустављања.

Теорија израчунљивости је уско везана са граном математичке логике званом теорија рекурзије, која отклања ограничење проучавања само модела рачунања који су блиски оним физикално остваривима. Многи математичари и рачунски теоретичари који проучавају теорију рекурзије ће је назвати теоријом израчунљивости. Не постоји стварна разлика између двају поља.

Теорија комплексности[уреди]

Теорија комплексности разматра не само може ли се проблем уопште решити на рачунару, већ и колико ефиксно може бити решен. Два главна аспекта су посматрана: временска сложеност и просторна сложеност, који респективно представљају број корака потребан да се рачунање обави, те количину меморије потребну за обављање рачунања.

Како би анализирали колико времена и простора дати алгоритам захтева, истраживачи изражавају време и простор захтеван за решавање проблема као функцију улазног проблема. На пример, проналажење неког појединог броја у дугој листи бројева постаје све теже како та листа расте. Ако кажемо да постоји н бројева у листи, тада, уколико листа није предсортирана или на неки начин индексирана, морамо испитати сваки број како бисмо пронашли број који тражимо. Стога кажемо да, како би решио овај проблем, рачунар мора обавити број корака који расте линеарно у односу на величину проблема.

Како би поједноставили овај проблем, истраживачи су прихватили велику О нотацију, која дозвољава поређење функција на начин који осигурава да појединачни аспекти конструкције машине не морају бити разматрани, већ само асимптотско понашање како проблеми постају све већи. Зато се у претходном примеру може рећи да проблем захтева н корака за решавање.

Можда најважнији од свих отворених проблема у рачунарству јесте питање могу ли одређене широке класе проблема означене као НП бити ефикасно решене.

Друге формалне дефиниције рачунања[уреди]

Осим Турингове машине, користе се и други модели рачунања као што су: ламбда рачун, комбинаторска логика, μ-рекурзивна функција, Марковљев алгоритам, Регистарска машина, П′′,

Као допуна општих рачунских модела, неки једноставнији рачунски модели су корисни за посебне, ограничене примене. Регуларни изрази, на пример, се користе за специфицирање узорака стринга у многим контекстима, од програмске подршке за канцеларијску продуктивност па до програмских језика. Други формализам математички истоветан регуларним изразима, коначни аутомати, се користи у дизајну електронских кругова и при решавању неких проблема. Контекстно независна граматика се користи приликом спецификације синтаксе програмских језика. Недетерминистички потисни аутомати су други формализам истоветан контекстно независним граматикама. Примитивно рекурзивне функције су поткласа рекурзивних функција.

Различити модели рачунања имају способност обављања различитих задатака. Један начин мерења моћи рачунског модела јесте проучавање класе формалних језика које модел може генерисати - ово води ка Чомскијевој хијерархији језика.

Извори[уреди]

  • Hein, James L: Theory of Computation. Sudbury, MA: Jones & Bartlett, 1996. ISBN 978-0867204971
  • Hopcroft, John E., and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. 3rd ed Reading, MA: Addison-Wesley, 2006. ISBN 978-0321455369
  • Taylor, R. Gregory: Models of Computation. New York: Oxford University Press, 1998.
  • Hartley Rogers, Jr, Theory of Recursive Functions and Effective Computability, MIT Press, 1987, ISBN 0-262-68052-1