Тэарэтычная інфарматыка

Тэарэтычная інфарматыка — раздзел інфарматыкі і матэматыкі, які вывучае абстрактныя і матэматычныя асновы вылічэнняў.

Гісторыя

Хоць лагічная выснова і матэматычны доказ існавалі і раней, у 1931 годзе Курт Гёдэль даказаў сваёй тэарэмай аб непаўнаце, што існуюць фундаментальныя абмежаванні на тое, якія сцвярджэнні могуць быць даказаны або абвергнуты.

Тэорыя інфармацыі была дададзеная ў гэтую вобласць у 1948 годзе з матэматычнай тэорыяй камунікацыі Клода Шэнана. У тым жа дзесяцігоддзі Дональд Хеб прапанаваў матэматычную мадэль навучання ў мозгу. З ростам колькасці біялагічных дадзеных, якія пацвярджаюць гэтую гіпотэзу з некаторымі зменамі, былі створаны вобласці нейронавых сетак і паралельнай размеркаванай апрацоўкі. У 1971 годзе Стывен Кук і Леанід Левін даказалі, працуючы незалежна адзін ад аднаго, што існуюць практычна значныя задачы, якія з’яўляюцца NP-поўнымі, што стала знамянальным вынікам у тэорыі складанасці вылічэнняў.^[1]

Сучасныя тэарэтычныя даследаванні ў галіне інфарматыкі засноўваюцца на гэтых базавых распрацоўках, але таксама ўключаюць у сябе мноства іншых матэматычных і міждысцыплінарных праблем, якія паказаныя ніжэй::

${\displaystyle P\rightarrow Q\,}$					P = NP ?
Матэматычная логіка	Тэорыя аўтаматаў	Тэорыя лікаў	Тэорыя графаў	Тэорыя вылічальнасці	Тэорыя складанасці вылічэнняў
GNITIRW-TERCES	${\displaystyle \Gamma \vdash x:{\text{Int}}}$
Крыптаграфія	Тэорыя тыпаў	Тэорыя катэгорый	Вылічальная геаметрыя	Камбінаторная аптымізацыя	Квантавыя вылічэнні