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

Алгоритми

Докладніше: Алгоритм

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

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

Структури даних

Докладніше: Структура даних

Структура даних це специфічний спосіб організації даних в комп'ютері, так що вона може бути використана ефективно.[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]) вивчає оптимальні алгоритми і обчислювальну складність для безперервних завдань. ІС вивчає такі безперервні проблеми, як інтеграція шляху, диференціальні рівняння з частинними похідними, системи звичайних диференціальних рівнянь, нелінійні рівняння, інтегральні рівняння, нерухомі точки і інтегрування високочастотних функцій.

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

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