Теоретична інформатика

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Теоретична інформатика — це наукова галузь, предметом вивчення якої є інформація та інформаційні процеси, в ​​якій здійснюється винахід і створення нових засобів роботи з інформацією. Це підрозділ загальної інформатики та математики, який зосереджується на більш абстрактних або математичних аспектах обчислювальної техніки і яка включає в себе теорію алгоритмів.

Як будь-яка фундаментальна наука, теоретична інформатика (в тісній взаємодії з філософією і кібернетикою) займається створенням системи понять, виявленням загальних закономірностей, що дозволяють описувати інформацію та інформаційні процеси, що протікають в різних сферах (у природі, суспільстві, людському організмі, технічних системах).

Окремі розділи теоретичної інформатики[ред.ред. код]

Не просто точно обмежити області даної теорії. Група Особливого Інтересу з Алгоритмів та Теорії Обчислень Асоціації Обчислювальної Техніки (ГОІАТО АОТ) описує місію науки, як підтримку теоретичної інформатики і зазначає:

Область теоретичної інформатики тлумачиться широко і включає в себе алгоритми, структури даних, теорію складності обчислень, розподілені обчислення, паралельні обчислення, НВІС (надвелика інтегральна схема), машинне навчання, обчислювальну біологію, обчислювальну геометрію, теорії інформації, криптографія, квантовий комп'ютер, теорія чисел і алгебра теорії обчислень (символьні обчислення[рос.]), семантика і верифікація мов програмування, теорію автоматів, а також теорію випадкових процесів. Робота в цій області часто відрізняється акцентом на математичній техніці і строгості.

До цього списку, науковий журнал АОТ “Транзакції з теорії обчислень” також додає теорію кодування, теорію обчислювального навчання і аспекти теоретичної інформатики в таких областях, як бази даних, інформаційний пошук, економічні моделі та мережі. Незважаючи на таку широку сферу діяльності, теоретики інформатики відрізняють себе від практиків. Деякі характеризують себе як тих, хто робить "більш фундаментальну наукову працю, що лежить в основі області обчислювальної техніки".  Інші ж, «теоретики-практики» наполягають, що неможливо відокремити теорії від практики. Це означає, що теоретики регулярно використовують експериментальну науку, яка виконується у менш теоретичних областях, таких як дослідження системи програмного забезпечення. Це також означає, що ніж співпраці все ж більше, ніж взаємовиключної конкуренції між теорією і практикою.

Історія[ред.ред. код]

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

Цей розвиток призвів до сучасного вивчення логіки і обчислюваності, а також, безперечно, області теоретичної інформатики в цілому. Теорія інформації була додана до галузі разом з  математичною теорією зв'язку[рос.] Клода Шеннона (1948). У тому ж десятилітті, Дональд Хебб[рос.] представив математичну модель навчання в головному мозку. З біологічними даними (кількість яких  тільки зростала), що, з деякими виправленнями, підтверджували цю гіпотезу, була створена галузь нейронних мереж і паралельної розподіленої технології обробки. У 1971 році Стівен Кук і Леонід Левін[рос.], працюючи незалежно один від одного, довели, що існують практично-відповідні проблеми, які є NP-повними – помітний результат в теорії складності обчислень.

З розвитком квантової механіки на початку 20-го століття з’явилася концепція, що математичні операції можуть бути виконані на всій хвильовій функції частинок. Іншими словами, можна обчислити функції на декількох станах одночасно. Це призвело до поняття квантового комп'ютера в другій половині 20-го століття, розвиток якого злетів у 1990-ті роки, коли Пітер Шор[рос.] показав, що такі методи можуть бути використані для факторіально великого числа за поліноміальний час, які, в разі їх здійснення, робили б найсучасніші асиметричні криптосистеми нікчемно небезпечними.

Сучасні теоретичні дослідження інформатики засновані на цих основних подіях, але включають в себе безліч інших математичних і міждисциплінарних проблем.

Галузі[ред.ред. код]

Алгоритми[ред.ред. код]

Основна стаття: Алгоритм

Структури даних[ред.ред. код]

Основна стаття: Структура даних

Теорія складності обчислень[ред.ред. код]

Основна стаття: Теорія складності обчислень

Розподілені обчислення[ред.ред. код]

Основна стаття: Розподілені обчислення

Паралельні обчислення[ред.ред. код]

Основна стаття: Паралельні обчислення

Надвисокий ступінь інтеграції[ред.ред. код]

Основна стаття: НВСІ (надвелика інтегральна схема)

Машинне навчання[ред.ред. код]

Основна стаття: Машинне навчання

Обчислювальна біологія[ред.ред. код]

Основна стаття: Обчислювальна біологія

Обчислювальна геометрія[ред.ред. код]

Основна стаття: Обчислювальна геометрія

Теорія інформації[ред.ред. код]

Основна стаття: Теорія інформації

Криптографія[ред.ред. код]

Основна стаття: Криптографія

Квантовий комп'ютер[ред.ред. код]

Основна стаття: Квантовий комп'ютер

Семантика мов програмування[ред.ред. код]

Основна стаття: Семантика мов програмування

Формальні методи[ред.ред. код]

Основна стаття: Формальні методи

Теорія автоматів[ред.ред. код]

Основна стаття: Теорія автоматів

Теорія кодування[ред.ред. код]

Основна стаття: Теорія кодування

Теорія чисел[ред.ред. код]

Основна стаття: Теорія чисел

Символьні обчислення[ред.ред. код]

Основна стаття: Символьні обчислення[рос.]

Інформаційна складність[ред.ред. код]

Обчислювальна теорія навчання[ред.ред. код]

Організації[ред.ред. код]