Википедија

Теоријска рачунарска наука

Теоријска рачунарска наука, или ТЦС, подскуп је опште рачунарске науке и математике који се фокусира на више математематичких и рачунарских тема, укључујући теорију рачунања, ламбда рачун[4] и теорију типова.[5]

Уметнички приказ Тјурингове машине.[1][2][3] Тјурингове машине се користе за моделовање општих рачунарских уређаја.

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

На овој листи АЦМ-ов часопис Трансакције о теорији рачунања укључује теорију кодирања и теорију рачунарског учења, као и теоријске аспекте рачунарске науке у подручјима као што су базе података, проналажење информација, економски модели и мреже. Упркос том широком опсегу, "теоријски људи" у рачунарској науци се идентификују као различити од "примењених људи". Први се карактеришу као да раде "(темељнију)" науку "која лежи у области рачуналства." Другии "примењени људи" сугеришу да је немогуће одвојити теорију и примену. То значи да такозвани "теоријски људи" редовно користе експерименталне науке у мање теоријским областима као што је истраживање софтверских система. То такође значи да постоји више координирања, него међусобно искључиве конкуренције између теорије и примене.

Историја рачунарства уреди

Док су логичко закључивање и математички доказ постојали раније, Курт Годел је 1931. доказао својом теоремом непотпуности да постоје основна ограничења у вези с тим да се изјаве могу доказати или одбацити.

Ови догађаји довели су до савременог проучавања логике и рачунања, а заправо и области теоријске рачунарске науке у целини. Теорија информација је додата математичкој теорији комуникације Цларие Сханнон из 1948. године. У истој деценији, Донналд Хебб представио је математички модел учења у мозгу. Уз монтажу биолошких података који подупиру ову хипотезу са неким изменама, успостављена су поља неуронских мрежа и паралелна дистрибуирана обрада. Године 1971. Степхен Цоок и независно радећи Леонид Левин доказали су да постоје практични релевантни проблеми који су НП-комлетни - значајан резултат рачунарске теорије сложености. С развојемм квантне механике на почетку 20. века дошло је до концепције да се математичка операција може извести на целој таласој функцији честица. Другим речима, могла би се истовремено рачунати функције на више стања. То је довело до концепта квантног рачунара у другој половини 20. века који је започео 1990. када је Петер Схор показао да се такве методе могу користити за фактор великих бројева у полиномијалном времену, који би уколико се имплементира, учинио најсавременији криптографски систем јавног кључа бескорисно несигурним.

Савремена теоријска истраживања рачунарства је заснована на овим основним догађајима, али обухвата и многе друге математичке и интердисциплинарне проблеме који су постављени, као што је приказано у наставку:

П→Q
П = НП

Математичка логика Теорија аутоматизма Теорија бројеве Теорија графова Компатибилност Теорија сложености

ГНИТИРW-ТЕРЦЕС Г ├ x : Инт Криптографија Теорија типа Теотија категорије Рачунарска геометрија Комбинаторна оптимизација Квантна комп. теотија

Алгоритам уреди

Алгоритам је корак-по-корак поступак решавања. Алгоритми се користе за обрачун, обраду података и аутоматско закључивање.

Алгоритам је ефикасна метода која се изражава као коначна листа јасно дефинисаних инструкција за израчунавање функције. Полазећи од почетног стања и почетног уноса (можда празног), инструкције описују рачунање које, када се изврши, пролази кроз коначан број добро дефинисаних сукцесивних стања, а на крају производи "излаз" и завршава у коначном завршном стању. Прелаз из једнеог стања у друго није нужно детерминистичан; неки алгоритми, познати као рандомизирани алгоритми, укључују случајни улаз.

Структура података уреди

Структура података је посебан начин организовања података у рачунару како би се могли ефикасно користити.

Различите врсте структура података одговарају различитим врстама апликација, а неке су врло специјализоване за одређене задатке. На пример, базе података користе индексе Б-стабла за мале проценте прикупљања података и компајлера и користе динамичке табеле са решењима као табеле потражње.

Рачунарска теорија сложености уреди

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

Дистрибутивни рачун уреди

Дистрибутивна рачунарска проучавања дистрибуирају системе. Дистрибутивни систем је софтверски систем у којем компоненте које се налазе на умреженим рачунарима комуницирају и координирају своје поступке преношењем порука. Компоненте међусобно комуницирају како би постигле заједнички циљ. Три значајне карактеристике дистрибутивних система су: конкурентност компоненти, недостатак глобалног сата и независни отказ компонената. Примери дистрибуираних система варирају од СОА-базираних система преко масивних мултииграчких онлајн апликација.

Паралелно рачунање уреди

Паралелно рачунање је облик рачунања у којем се истовремено изводи више операција. Функционише на принципу да се велики проблеми често могу поделити на мање, а затим се паралелно решавати. Постоји неколико различитих облика паралелног рачунања: битни ниво, ниво инструкција, подаци и паралелизам задатака. Како је потрошња енергије (и тиме и загревање) рачунара постало забрињавајуће последњих година, паралелно рачунање постало је доминантна парадигма у рачунарској архитектури, углавном у облику вишејезгрених процесора. Паралелни рачунарски програми су тежи за писње од секвенцијалних, јер уводе неколико нових класа потенцијалних софтверских грешака. Комуникација и синхронизација између различитих потпрограма обично су неке од највећих препрека за добијање добрих перформанси паралелног програма.

Највеће могуће убрзање једног програма као резултат паралелизације познат је као Амдахлов закон.

Веома велика интеграција уреди

Веома велика интеграција (ВЛСИ) је процес стварања интегралног кола (ИЦ) комбинујући хиладе транзистора у један чип. ВЛСИ је започео седамдесетих година када су се развиле сложене полупроводничке и комуникацијске технологије. Микропроцесор је ВЛСИ уређај. Електронско коло се може састојати од процесора, РАМ меморије, РОМ меморије и др. ВЛСИ технологија омогићава да се све ове технологије спакују у један чип.

Машинско учење уреди

Машинско учење је научна дисциплина која се бави израдом и проучавањем алгоритама који могу учити из података. Машинско учење може се сматрати делом информатичке науке и статистике. Оно има снажне везе с вештачком интелигенцијом и оптимизацијом, које дају методе, теорију и примену на терену. Примери апликација укључују филтрирање нежељених порука, оптичко препознавање знакова (ОЦР), претраживаче и рачунарски вид. Машинско учење понекад се повезује са рударењем података, иако се то више фокусира на истраживачку анализу података.

Рачунарска биологија уреди

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

Рачунарска геометрија уреди

Рачунарска геометрија је грана рачунарских наука посвећена проучавању алгоритама који се могу изразити у виду геометрије. Неки чисто геометријски проблеми произлазе из проучавања рачунарских геометријских алгоритама, а такви се проблеми такође сматрају делом рачунарске геометрије. Док је модерна рачунарска геометрија недавно развијена, класицна геометрија је једна од најстаријих области рачунарства, са историјом која се протеже до антике. Древна претеча је санскртска расправа Схулба Сутра, или "Правила акорда", књига алгоритама написаних у 800. пне.

Друге важне примене рачунарске геометрије укључују роботику (проблеме при планирању ивидљивости), географски информациони системи (геометријско лоцирање и претраживање, планирање руте), дизајн интегралних кола (дизајн и верификација ИЦ геометрије), рачунарско инжењерство (ЦАЕ) (мрежна генерација), рачунарска визија (3Д реконструкција).

Теорија информација уреди

Теорија информација је грана примењене математике, електротехнике и рачунарске науке која укључује квантовање информација. Теорију информација развио је Цлауде Е. Сханнон како би пронашао основне границе на операцијама обраде сигнала, као што су компресија података, поуздано чување и комуницирање података. Примена основних тема теорије информација уклучује компресију података без губитака (нпр.ЗИП датотеке), компресију губитка података (нпр.МП3 и ЈПЕГ) и кодирање канала (нпр. За Дигитал Субсцрибер Лине (ДСЛ). Њен је утицај био пресудан за успех Воyагерових мисија у свемир, изум компакт диска, мобилних телефона, развој Интернета, проучавање лингвистике и људске перцепције, разумевање црних рупа, и бројна друга подручја. Важне области теорије информација су изворно кодирање, кодирање канала, алгоритамска теорија сложености, алгоритамска теорија информација, информацијско-теоријска сигурност и мере информација.

Криптографија уреди

Криптографија је пракса и проучавање техника сигурне комуникације у присуству трећих страна (названих противницима). Грубо говорећи, ради се о конструирсању и анализирању протокола који превладавају утицај противника и који се односе на различите аспекте информацијске сигурности као што су поверљивост података, интегритет података, рачунарске лозинке, тачност и неизвршење. Савремена криптографија се преплиће са математиком, рачунарством и електротехником. Примена криптографије укључује АТМ картице, и електронску трговину.

Квантно рачунање уреди

Квантни рачунар је рачунарски систем који за обраду података директно користи квантно-механичке појаве, као што су суперпозиција и заплет. Док дигитални рачунари захтевају да се подаци кодирају у бинарне цифре (битове), од којих је свака увек у једној од два одређена стања (0 или 1), квантно рачунање користи qубитс (квантне битове), који могу бити у суперпозицијама стања. Теоријски модел је квантна Турингова масина, познат као универзални квантни рачунар. Подручје квантног рачунања први пут су увели Јуриј Манин 1980. и Рицхард Феyнман 1982Од 2014. године, квантно рачунање је још увек у повоју, али изведени су експерименти у којима су квантне рачунарске операције извршене на врло малом броју qубита. Многе националне владе и агенције за финансирање подржавају квантно рачунарско истраживање као што је криптоанализа за развој квантних рачунара, како за цивилну тако и за националну безбедбост.

Информациона сложеност уреди

Информациона комплексност (ИБЦ) проучава оптималне алгоритме и рачунарску сложеност за континуиране проблеме. ИБЦ проучава интеграцију путање, парцијалне диференцијалне једначине, системе обичних диференцијалних једналина, нелинеарне једначине, интегралне једначине и врло високу димензионалну интеграцију.

Рачунарска теорија бројева уреди

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

Рачунарска алгебра уреди

Симболички прорачун Уређивање Рачунарска алгебра, која се назива и симболичко рачунање или алгебарско рачунање, је научна област која се односи на проучавање и развој алгоритама и софтвера за рад са математичким изразима и другим математичким објектима).

Семантика програма уреди

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

Формалне методе уреди

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

Теорија аутомата уреди

Теорија аутомата је проучавање апстрактних машина и аутоматизма, као и рачунарских проблема који се могу решити користечи их.

Теорија кодирања уреди

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

Теорија машинског учења уреди

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

Референце уреди

  1. ^ Минскy 1967:107 "Ин хис 1936 папер, А. M. Туринг дефинед тхе цласс оф абстрацт мацхинес тхат ноw беар хис наме. А Туринг мацхине ис а фините-стате мацхине ассоциатед wитх а специал кинд оф енвиронмент -- итс тапе -- ин wхицх ит цан сторе (анд латер рецовер) сеqуенцес оф сyмболс," алсо Стоне 1972:8 wхере тхе wорд "мацхине" ис ин qуотатион маркс.
  2. ^ Стоне 1972:8 статес "Тхис "мацхине" ис ан абстрацт матхематицал модел", алсо цф. Сипсер 2006:137фф тхат десцрибес тхе "Туринг мацхине модел". Рогерс 1987 (1967):13 реферс то "Туринг'с цхарацтеризатион", Боолос Бургесс анд Јеффреy 2002:25 реферс то а "специфиц кинд оф идеализед мацхине".
  3. ^ Сипсер 2006:137 "А Туринг мацхине цан до еверyтхинг тхат а реал цомпутер цан до".
  4. ^ Туринг, Алан M. (децембар 1937). „Цомпутабилитy анд λ-Дефинабилитy”. Тхе Јоурнал оф Сyмболиц Логиц. 2 (4): 153—163. ЈСТОР 2268280. С2ЦИД 2317046. дои:10.2307/2268280. 
  5. ^ Цхурцх, Алонзо (1940). „А формулатион оф тхе симпле тхеорy оф тyпес”. Тхе Јоурнал оф Сyмболиц Логиц. 5 (2): 56—68. ЈСТОР 2266170. С2ЦИД 15889861. дои:10.2307/2266170. 

Фуртхер реадинг уреди

Спољашње везе уреди

 
Теоријска рачунарска наука на Викимедијиној остави.
Преузето из „https://sr.wikipedia.org/w/index.php?title=Teorijska_računarska_nauka&oldid=27674536”