Теоретична інформатика — Вікіпедія

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

Теоретична інформатика у Вікісховищі

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

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

Не просто точно описати межі даної теорії. ACM SIGACT^[en] англ. Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, підгрупа ACM, описує місію науки, як підтримку теоретичної інформатики і зазначає:^[1]

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

До цього списку, науковий журнал «ACM Transactions on Computation Theory» (TOCT) також додає теорію кодування, теорію обчислювального навчання^[en] і аспекти теоретичної інформатики в таких областях, як бази даних, інформаційний пошук, економічні моделі та мережі.^[2] Попри таку широку сферу діяльності, теоретики інформатики відрізняють себе від практиків. Деякі характеризують себе як тих, хто робить «більш фундаментальну наукову працю, що лежить в основі області обчислювальної техніки».^[3] Інші ж, «теоретики-практики» наполягають, що неможливо відокремити теорії від практики. Це означає, що теоретики регулярно використовують експериментальну науку, яка виконується у менш теоретичних областях, таких як дослідження систем програмного^[en] забезпечення. Це також означає, що співпраці все ж більше, ніж взаємовиключної конкуренції між теорією і практикою.

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

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

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

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

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

Алгоритм являє собою покрокову процедуру для розрахунків. Алгоритми використовують для розрахунку, обробки даних і автоматизованого мислення.

Алгоритм є ефективним процесом. Він виражається у вигляді обмеженого списку^[4], що складається з чітко визначених^[5] інструкцій для обчислення функції^[6]. Починаючи з первинного стану і початкової «вхідної інформації» (цей пункт може бути порожнім^[7]), інструкції описують обчислення, які при виконанні проходять через кінцеву^[8] кількість чітко визначених послідовних станів і зрештою на останньому етапі результують у «вихідну інформацію»^[9]. Перехід від одного стану до іншого, не обов'язково детермінований; деякі алгоритми, знані як увипадковлені алгоритми, не виключають випадковий порядок.^[10]

Структура даних це специфічний спосіб організації даних в комп'ютері, так що вона може бути використана ефективно.^[11][12]

Різні види структур даних підходять для різних типів додатків, а деякі є вузькоспеціалізованими для виконання конкретних завдань. Наприклад, бази даних використовують індекси Б-дерева для малих відсотків пошуку даних і компіляторів, а бази даних використовують динамічні хеш-таблиці, як пошукові.

Структури даних забезпечують ефективні засоби для управління великими обсягами даних для таких ужитків, як великі бази даних і вебіндексування. Як правило, ефективні структури даних грають ключову роль в розробці ефективних алгоритмів. Деякі формальні методи проєктування та мови програмування підкреслюють структури даних, а не алгоритми, як ключовий організаційний фактор у розробці програмного забезпечення. Зберігання та пошук можуть бути здійснені за даними, що зберігаються як в пам'яті комп'ютера, так і у зовнішній пам'яті.

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

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

Розподілені обчислення досліджують розподілені системи. Розподілена система являє собою програмне забезпечення, в якому компоненти, розташовані на комп'ютерах однієї мережі зв'язку, обмінюються даними та координують свої дії шляхом обміну повідомлень.^[13] Компоненти взаємодіють один з одним для досягнення спільної мети. Три важливих характеристики розподілених систем: паралелізм компонентів, відсутність глобального годинника, і незалежність при виході компонентів з ладу.^[13] Приклади розподілених систем варіюються від систем СОА до масових багатокористувацьких ігор і peer-to-peer додатків.

Комп'ютерна програма, яка працює в розподіленій системі, називається розподіленою програмою, і розподілене програмування — це процес написання таких програм.^[14] Існує багато альтернатив для механізму передачі повідомлень, в тому числі RPC-подібні конектори і черги повідомлень. Важливою метою і завданням розподілених систем є прозорість розташування.

Паралельні обчислення — це форма обчислень, в яких кілька дій проводяться одночасно.^[15] Ґрунтуються на тому, що великі задачі можна розділити на кілька менших, кожну з яких можна розв'язати незалежно від інших.

Є кілька різних рівнів паралельних обчислень: бітовий, інструкцій, даних та паралелізм задач. Паралельні обчислення застосовуються вже протягом багатьох років, переважно в високопродуктивних обчисленнях, але зацікавлення ним зросло тільки нещодавно, через фізичні обмеження зростання частоти.^[16] Оскільки споживана потужність (і відповідно виділення тепла) комп'ютерами стало проблемою в останні роки,^[17] паралельне програмування стає домінуючою парадигмою в комп'ютерній архітектурі, основному в формі багатоядерних процесорів.^[18]

Програми для паралельних комп'ютерів писати значно складніше, ніж для послідовних,^[19] бо паралелізм додає кілька нових класів потенційних помилок, серед яких найпоширеніною є стан гонитви. Комунікація та синхронізація процесів, зазвичай, одна з найбільших перешкод для досягнення хорошої продуктивності паралельних програм.

Максимальний можливий приріст продуктивності паралельної програми визначається законом Амдала.

(надвелика інтегральна схема)

Надвисокий ступінь інтеграції (VLSI) — це процес створення мікросхеми шляхом об'єднання тисячі транзисторів в одному чипі. НВІС почався в 1970-ті роки, коли розроблялися складні напівпровідникові і комунікаційні технології. Мікропроцесор являє собою пристрій НВІС. До впровадження технології НВІС більшість мікросхем мали обмежений набір функцій, які вони могли б виконувати. Електронна схема може складатися з ЦП, ROM, RAM і «glue logic» (особливий вид цифрових схем, що дозволяє різним типам логічних чипів або схем працювати разом, діючи як сполучна ланка між ними). НВІС дозволяє виробникам мікросхем включити все це в один чип.

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

Машинне навчання можна розглядати як під-область інформатики та статистики. Вона має міцні зв'язки з штучним інтелектом і оптимізацією, які забезпечують методи, теорію і застосування доменів до області. Машинне навчання використовується в різних обчислювальних задачах, де розробка та програмування чітких алгоритмів на основі правил є неприпустимою. Приклади застосування включають фільтрацію спаму, оптичне розпізнавання символів (OCR), пошукові системи і комп'ютерний зір. Машинне навчання іноді з'єднані з добуванням даних, хоча це більше сфокусовано на пошуковому аналізі даних. Машинне навчання та розпізнавання образів можна розглядати як два аспекти одного і того ж поля.

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

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

Обчислювальна геометрія — галузь комп'ютерних наук присвячена вивченню алгоритмів що описуються в термінах геометрії.

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

Іншим важливим застосуванням обчислювальної геометрії є робототехніка (планування руху та задачі розпізнавання образів), геоінформаційні системи (геометричний пошук, планування маршруту), дизайн мікросхем, програмування верстатів з числовим програмним управлінням, CAE, комп'ютерний зір (3D реконструкції).

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

З моменту свого створення вона розширилася і знайшла застосування в таких областях, як статистичне висновування, обробка природної мови, криптографія, нейробіологія, еволюція та функції молекулярних кодів, теплофізика, квантовий комп'ютер, лінгвістика, для виявлення плагіату, розпізнавання образів, виявлення аномалій та інших форм аналізу даних.

Застосування основних тематичних розділів теорії інформації включають стиснення даних без втрат (наприклад, ZIP-файли), стиснення даних з втратами (наприклад, MP3 і JPEG-файли) і канального кодування (наприклад, для цифрових абонентських ліній (DSL). Наука знаходиться на перетині математики, статистики, інформатики, фізики, нейробіології і електротехніки. ЇЇ вплив має вирішальне значення для успіху місії Вояджер в глибокому космосі, винахід компакт-диска, можливість створення мобільних телефонів, розвиток Інтернету, вивчення лінгвістики і людського сприйняття, розуміння чорних дір, і багато іншого. Важливі субполя теорії інформації: стиснення даних, пряма корекція помилок, алгоритмічна теорія складності, алгоритмічна теорія інформації, теоретико-інформаційна безпека, а також вимірювання інформації.

Криптогра́фія — наука про математичні методи забезпечення конфіденційності, цілісності і автентичності інформації. Розвинулась з практичної потреби передавати важливі відомості найнадійнішим чином. Для математичного аналізу криптографія використовує інструментарій абстрактної алгебри та теорії ймовірностей.

Криптографічні алгоритми розроблені навколо припущень обчислювальної складності, що робить такі алгоритми важкими для зламування на практиці. Теоретично зламати таку систему можна, але це неможливо зробити будь-яким з відомих практичних засобів.

Квантовий комп'ютер — фізичний обчислювальний пристрій, функціонування якого ґрунтується на принципах квантової механіки, зокрема, принципі суперпозиції та явищі квантової заплутаності. Такий пристрій відрізняється від звичайного транзисторного комп'ютера зокрема тим, що класичний комп'ютер оперує даними, закодованими у двійкових розрядах (бітах), кожен з яких завжди знаходяться в одному з двох станів (0 або 1), коли квантовий комп'ютер використовує квантові біти (кубіти), які можуть знаходитися у суперпозиції станів. Інформатико-теоретичною моделлю такого обчислювального пристрою є квантова машина Тюрінга, або універсальний квантовий комп'ютер. Квантовий комп'ютер має низку спільних ознак із недетермінованим та ймовірнісним комп'ютерами, але тим не менш ці пристрої не є тотожними. Вважається, що вперше ідею використання принципів квантової механіки для виконання обчислень висловили Юрій Манін та Річард Фейнман в 1981 році.

Станом на 2014 рік, квантові обчислення все ще перебувають в початковому стані, але були проведені експерименти, в яких квантові обчислювальні операції були виконані на дуже невеликій кількості кубітів. І практичні, і теоретичні дослідження тривають, і багато національних урядів і військових фінансувальних установи підтримують дослідження квантових обчислень для розробки квантових комп'ютерів як для цивільних, так і в цілях національної безпеки, таких як криптоаналіз.

Семантика в теорії програмування — розділ що вивчає математичне значення мови програмування та моделі обчислень. Формальна семантика мови задається математичною моделлю яка описує можливі в мові обчислення.

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

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

Формальні методи найкраще описати як застосування досить широкого розмаїття теоретичних основ інформатики, зокрема логіки обчислень, формальних мов, теорії автоматів і семантики мов програмування, окрім того, системи типізації і алгебричні типи даних для специфікації і перевірки проблем в програмному і апаратному забезпеченні.

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

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

Комп'ютерна алгебра, яку також називають символьними обчисленнями або алгебричними обчисленнями, є науковою областю, яка належить до вивчення і розробки алгоритмів і програмного забезпечення для роботи з алгебричними виразами та іншими математичними об'єктами. Хоча комп'ютерна алгебра повинна бути під-областю наукових обчислень, вона, як правило, розглядається як окрема наука. Зокрема, така, як наукові обчислення, що, як правило, основані на чисельних методах з приблизними числами з рухомою комою, в той час як символьні обчислення підкреслюють точне обчислення виразів, що містять змінні, які не мають ніякого заданого значення, і, таким чином, розглядаються як символи (від того і назва — символьні обчислення).

Програмні додатки, які виконують символічні обчислення називаються системами комп'ютерної алгебри, де термін система вказує на складність основних додатків, які включають в себе, як мінімум:

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

Алгоритмічна теорія чисел — це наука про алгоритми для виконання цифрових теоретичних обчислень. Найвідомішою проблемою в цій галузі є факторизація цілих чисел.

Інформаційна складність (IBC^[en]) вивчає оптимальні алгоритми і обчислювальну складність для безперервних завдань. ІС вивчає такі безперервні проблеми, як інтеграція шляху, диференціальні рівняння з частинними похідними, системи звичайних диференціальних рівнянь, нелінійні рівняння, інтегральні рівняння, нерухомі точки і інтегрування високочастотних функцій.

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

• Асоціація Обчислювальної Техніки (European Association for Theoretical Computer Science^[en])
• Група Особливого Інтересу з Алгоритмів та Теорії Обчислень (SIGACT^[en])