Теоретична інформатика — це наукова галузь, предметом вивчення якої є інформація та інформаційні процеси, в якій здійснюється винахід і створення нових засобів роботи з інформацією. Це підрозділ загальної інформатики та математики, який зосереджується на більш абстрактних або математичних аспектах обчислювальної техніки і яка охоплює теорію алгоритмів.
Як будь-яка фундаментальна наука, теоретична інформатика (в тісній взаємодії з філософією і кібернетикою) займається створенням системи понять, виявленням загальних закономірностей, що дозволяють описувати інформацію та інформаційні процеси, що протікають в різних сферах (у природі, суспільстві, людському організмі, технічних системах).
Окремі розділи теоретичної інформатики Не просто точно описати межі даної теорії. , підгрупа ACM, описує місію науки, як підтримку теоретичної інформатики і зазначає:
До цього списку, науковий журнал «ACM Transactions on Computation Theory» (TOCT) також додає теорію кодування, теорію обчислювального навчання і аспекти теоретичної інформатики в таких областях, як бази даних, інформаційний пошук, економічні моделі та мережі. Попри таку широку сферу діяльності, теоретики інформатики відрізняють себе від практиків. Деякі характеризують себе як тих, хто робить «більш фундаментальну наукову працю, що лежить в основі області обчислювальної техніки». Інші ж, «теоретики-практики» наполягають, що неможливо відокремити теорії від практики. Це означає, що теоретики регулярно використовують експериментальну науку, яка виконується у менш теоретичних областях, таких як дослідження забезпечення. Це також означає, що співпраці все ж більше, ніж взаємовиключної конкуренції між теорією і практикою.
Історія
Хоча логічний висновок і математичне доведення існували і раніше, у 1931 році Курт Гедель своєю теоремою про неповноту довів, що існують принципові обмеження на те, які формули можуть бути доведені або спростовані.
Цей розвиток призвів до сучасного вивчення логіки і обчислюваності, а також, безперечно, області теоретичної інформатики в цілому. Теорія інформації була додана до галузі разом з математичною теорією зв'язку Клода Шеннона (1948). У тому ж десятилітті, Дональд Гебб представив математичну модель навчання в головному мозку. З біологічними даними (кількість яких тільки зростала), що, з деякими виправленнями, підтверджували цю гіпотезу, була створена галузь нейронних мереж і паралельної розподіленої технології обробки. 1971 року Стівен Кук і Леонід Левін, працюючи незалежно один від одного, довели, що існують практично-відповідні проблеми, які є NP-повними — помітний результат в теорії складності обчислень.
З розвитком квантової механіки на початку 20-го століття з'явилася концепція, що математичні операції можуть бути виконані на всій хвильовій функції частинок. Іншими словами, можна обчислити функції на декількох станах одночасно. Це призвело до поняття квантового комп'ютера в другій половині 20-го століття, розвиток якого злетів у 1990-ті роки, коли Пітер Шор показав, що такі методи можуть бути використані для факторіально великого числа за поліноміальний час, які, в разі їх здійснення, робили б найсучасніші асиметричні криптосистеми нікчемно небезпечними.
Сучасні теоретичні дослідження інформатики засновані на цих основних подіях, але включають в себе безліч інших математичних і міждисциплінарних проблем.
P = NP ? Математична логіка Теорія автоматів Теорія чисел Теорія графів Теорія обчислюваності Теорія складності обчислень GNITIRW-TERCES Криптографія Теорія типів Теорія категорій Обчислювальна геометрія Комбінаторна оптимізація Квантова теорія обчислюваності
Предмети вивчення
Алгоритми
Алгоритм являє собою покрокову процедуру для розрахунків. Алгоритми використовують для розрахунку, обробки даних і автоматизованого мислення.
Алгоритм є ефективним процесом. Він виражається у вигляді обмеженого списку«Будь-який класичний математичний алгоритм, наприклад, може бути описаний кінцевим числом англійських слів». (Hartley Rogers, Theory of Recursive Function and Effective Computability, 1987), що складається з чітко визначенихЧітко визначених по відношенню до того, хто виконує дію за алгоритмом: «Існує обчислювальний засіб, як правило, людина, яка може реагувати на інструкції і виконувати обчислення». (Hartley Rogers, Theory of Recursive Function and Effective Computability, 1987) інструкцій для обчислення функції«Алгоритм являє собою процедуру обчислення функції (по відношенню до деяких обраних позначень для чисел) … це обмеження (для числових функцій) не призводить до обмеження спільності». (Hartley Rogers, Theory of Recursive Function and Effective Computability, 1987). Починаючи з первинного стану і початкової «вхідної інформації» (цей пункт може бути порожнім«Алгоритм має нуль або більше входів, тобто кількість, яка дається йому перед початком алгоритму». (Дональд Кнут, The Art of Computer Programming, 1973)), інструкції описують обчислення, які при виконанні проходять через кінцеву«Процедуру, яка має всі характеристики алгоритму за винятком того, що їй, можливо, бракує скінченності, можна назвати 'обчислювальний метод'». (Дональд Кнут, The Art of Computer Programming, 1973) кількість чітко визначених послідовних станів і зрештою на останньому етапі результують у «вихідну інформацію»«Алгоритм має одну або кілька вихідних інформацій, тобто величин, які мають певне відношення до вхідних інформацій». (Дональд Кнут, The Art of Computer Programming, 1973). Перехід від одного стану до іншого, не обов'язково детермінований; деякі алгоритми, знані як увипадковлені алгоритми, не виключають випадковий порядок."Чи є процес з випадковими внутрішніми процесами (не включаючи вхідну інформацію) алгоритмом — питання дискусійне. Роджерс вважає, що: «обчислення виконується в переривчастій поступовості, без використання безперервних методів або аналогових пристроїв… переноситися детерміновано, не вдаючись до випадкових способів або пристроїв, наприклад, до гральних костей». (Hartley Rogers, Theory of Recursive Function and Effective Computability, 1987)
Структури даних
Структура даних це специфічний спосіб організації даних в комп'ютері, так що вона може бути використана ефективно.Пол Е. Блек, запис про структури даних в Словнику алгоритмів і структур даних Національного інституту стандартів і технологій США. 15 грудня 2004, онлайн-версія від 21 вересня 2009.Запис про структури даних в Британській енциклопедії (2009) онлайн-версія від 21 травня 2009 року.
Різні види структур даних підходять для різних типів додатків, а деякі є вузькоспеціалізованими для виконання конкретних завдань. Наприклад, бази даних використовують індекси Б-дерева для малих відсотків пошуку даних і компіляторів, а бази даних використовують динамічні хеш-таблиці, як пошукові.
Структури даних забезпечують ефективні засоби для управління великими обсягами даних для таких ужитків, як великі бази даних і вебіндексування. Як правило, ефективні структури даних грають ключову роль в розробці ефективних алгоритмів. Деякі формальні методи проєктування та мови програмування підкреслюють структури даних, а не алгоритми, як ключовий організаційний фактор у розробці програмного забезпечення. Зберігання та пошук можуть бути здійснені за даними, що зберігаються як в пам'яті комп'ютера, так і у зовнішній пам'яті.
Теорія складності обчислень
Теорія складності обчислень є гілкою теорії алгоритмів, яка фокусується на класифікації обчислювальних проблем відповідно до властивих труднощів, а також установлює зв'язок цих складностей одні з одними. Обчислювальні проблеми — це завдання, які в принципі піддаються вирішенню за допомогою комп'ютера, що еквівалентно тому, що проблема може бути вирішена шляхом механічного застосування математичних кроків, таких як алгоритм.
Проблема вважається важкою за своєю суттю, якщо її рішення вимагає значних ресурсів, незалежно від використовуваного алгоритму. Теорія формалізує це, вводячи математичні моделі обчислень для вивчення цих проблем і визначаючи кількість ресурсів, необхідних для їх вирішення (такі як час і сховище). Використовуються й інші міри складності, такі як кількість комунікацій (використовується у комунікаційній складності), кількість вентилів в ланцюзі (використовують в складних схемах), а також кількість процесорів (використовують в паралельних обчисленнях). Одне із завдань теорії складності обчислень полягає у визначенні практичних обмежень на те, що комп'ютери можуть і не можуть зробити.
Розподілені обчислення
Розподілені обчислення досліджують розподілені системи. Розподілена система являє собою програмне забезпечення, в якому компоненти, розташовані на комп'ютерах однієї мережі зв'язку, обмінюються даними та координують свої дії шляхом обміну повідомлень.Джордж Колоуріс; Жан Доллімор; Тім Кіндберг; Гордон Блер (2011). Розподілені системи: концепції та дизайн (5-е видання). Бостон: Addison-Wesley. ISBN 0-132-14301-1 Компоненти взаємодіють один з одним для досягнення спільної мети. Три важливих характеристики розподілених систем: паралелізм компонентів, відсутність глобального годинника, і незалежність при виході компонентів з ладу. Приклади розподілених систем варіюються від систем СОА до масових багатокористувацьких ігор і peer-to-peer додатків.
Комп'ютерна програма, яка працює в розподіленій системі, називається розподіленою програмою, і розподілене програмування — це процес написання таких програм.Ендрюс, Грегорі Р. (2000), Основи, багатопоточного, паралельного і розподіленого програмування, Addison-Wesley, ISBN 0-201-35752-6.
Долев, Шломі (2000), Автостабілізація, MIT Press, ISBN 0-262-04178-2.
Гош, Сукумар (2007), Розподілені системи — Алгоритмічний підхід, Chapman & Hall / CRC, ISBN 978-1-58488-564-1. Існує багато альтернатив для механізму передачі повідомлень, в тому числі RPC-подібні конектори і черги повідомлень. Важливою метою і завданням розподілених систем є прозорість розташування.
Паралельні обчислення
Паралельні обчислення — це форма обчислень, в яких кілька дій проводяться одночасно.Готліб, Алан; Алмасі, Джордж С. (1989). Високопаралельні обчислення. Редвуд-Сіті, штат Каліфорнія.: Benjamin / Cummings. ISBN 0-8053-0177-1 Ґрунтуються на тому, що великі задачі можна розділити на кілька менших, кожну з яких можна розв'язати незалежно від інших.