Теоретическая информатика — это подраздел информатики и математики , который фокусируется на абстрактных и математических основах вычислений .
Трудно точно очертить теоретические области. Специальная группа по интересам ACM по алгоритмам и теории вычислений (SIGACT) дает следующее описание: [1]
TCS охватывает широкий спектр тем, включая алгоритмы , структуры данных , вычислительную сложность , параллельные и распределенные вычисления, вероятностные вычисления , квантовые вычисления , теорию автоматов , теорию информации , криптографию , семантику и верификацию программ , алгоритмическую теорию игр , машинное обучение , вычислительную биологию , вычислительную экономику , вычислительную геометрию и вычислительную теорию чисел и алгебру . Работа в этой области часто отличается акцентом на математическую технику и строгость .
Хотя логический вывод и математическое доказательство существовали и ранее, в 1931 году Курт Гёдель доказал своей теоремой о неполноте , что существуют фундаментальные ограничения на то, какие утверждения могут быть доказаны или опровергнуты.
Теория информации была добавлена в эту область с математической теорией коммуникации 1948 года Клода Шеннона . В том же десятилетии Дональд Хебб представил математическую модель обучения в мозге. С ростом биологических данных, подтверждающих эту гипотезу с некоторыми изменениями, были созданы области нейронных сетей и параллельной распределенной обработки . В 1971 году Стивен Кук и, работая независимо , Леонид Левин доказали, что существуют практически значимые задачи, которые являются NP-полными — знаменательный результат в теории вычислительной сложности . [2]
Современные теоретические исследования в области информатики основаны на этих базовых разработках, но включают в себя множество других поставленных математических и междисциплинарных проблем, как показано ниже:
Алгоритм — это пошаговая процедура вычислений. Алгоритмы используются для вычислений , обработки данных и автоматизированных рассуждений .
Алгоритм — это эффективный метод , выраженный в виде конечного списка [3] четко определенных инструкций [4] для вычисления функции . [5] Начиная с начального состояния и начальных входных данных (возможно, пустых ), [6] инструкции описывают вычисление , которое при выполнении проходит через конечное [7] число четко определенных последовательных состояний, в конечном итоге производя «выходные данные» [8] и завершаясь в конечном конечном состоянии. Переход из одного состояния в другое не обязательно является детерминированным ; некоторые алгоритмы, известные как рандомизированные алгоритмы , включают случайные входные данные. [9]
Теория автоматов — это изучение абстрактных машин и автоматов , а также вычислительных задач, которые могут быть решены с их помощью. Это теория в теоретической информатике, в рамках дискретной математики (раздел математики , а также информатике ). Автоматы происходят от греческого слова αὐτόματα, означающего «самодействующий».
Теория автоматов — это изучение самодействующих виртуальных машин, помогающих в логическом понимании процесса ввода и вывода, без или с промежуточными этапами вычислений ( или любой функцией /процессом).
Теория кодирования — это изучение свойств кодов и их пригодности для конкретного приложения. Коды используются для сжатия данных , криптографии , исправления ошибок и в последнее время также для сетевого кодирования . Коды изучаются различными научными дисциплинами — такими как теория информации , электротехника , математика и информатика — с целью разработки эффективных и надежных методов передачи данных . Обычно это включает в себя удаление избыточности и исправление (или обнаружение) ошибок в передаваемых данных.
Теория вычислительной сложности — это раздел теории вычислений , который фокусируется на классификации вычислительных задач в соответствии с их присущей сложностью и связывании этих классов друг с другом. Под вычислительной задачей понимается задача, которая в принципе может быть решена компьютером, что эквивалентно утверждению, что задача может быть решена путем механического применения математических шагов, таких как алгоритм .
Проблема считается изначально сложной, если ее решение требует значительных ресурсов, независимо от используемого алгоритма . Теория формализует эту интуицию, вводя математические модели вычислений для изучения этих проблем и количественно определяя объем ресурсов, необходимых для их решения, таких как время и память. Также используются другие меры сложности , такие как объем коммуникации (используется в сложности коммуникации ), количество вентилей в схеме (используется в сложности схемы ) и количество процессоров (используется в параллельных вычислениях ). Одна из ролей теории вычислительной сложности заключается в определении практических ограничений того, что могут и не могут делать компьютеры .
Вычислительная геометрия — это раздел компьютерной науки, посвященный изучению алгоритмов, которые могут быть сформулированы в терминах геометрии . Некоторые чисто геометрические проблемы возникают из изучения вычислительных геометрических алгоритмов, и такие проблемы также считаются частью вычислительной геометрии.
Основным толчком к развитию вычислительной геометрии как дисциплины послужил прогресс в области компьютерной графики и систем автоматизированного проектирования и производства ( CAD / CAM ), однако многие проблемы вычислительной геометрии носят классический характер и могут возникать в результате математической визуализации .
Другие важные приложения вычислительной геометрии включают робототехнику (планирование движения и проблемы видимости), географические информационные системы (ГИС) (геометрическое местоположение и поиск, планирование маршрутов), проектирование интегральных схем (проектирование и проверка геометрии ИС), компьютерное проектирование (CAE) (создание сеток), компьютерное зрение (3D-реконструкция).
Теоретические результаты в машинном обучении в основном касаются типа индуктивного обучения, называемого контролируемым обучением. В контролируемом обучении алгоритму предоставляются образцы, которые помечены некоторым полезным способом. Например, образцы могут быть описаниями грибов, а метки могут указывать на то, съедобны грибы или нет. Алгоритм берет эти ранее помеченные образцы и использует их для индукции классификатора. Этот классификатор представляет собой функцию, которая присваивает метки образцам, включая образцы, которые алгоритм никогда ранее не видел. Целью алгоритма контролируемого обучения является оптимизация некоторой меры производительности, такой как минимизация количества ошибок, допущенных в новых образцах.
Вычислительная теория чисел , также известная как алгоритмическая теория чисел , является изучением алгоритмов для выполнения вычислений теории чисел . Наиболее известная проблема в этой области — факторизация целых чисел .
Криптография — это практика и изучение методов безопасной связи в присутствии третьих лиц (называемых противниками ). [10] В более общем смысле, это создание и анализ протоколов , которые преодолевают влияние противников [11] и которые связаны с различными аспектами информационной безопасности, такими как конфиденциальность данных , целостность данных , аутентификация и невозможность отказа от авторства . [12] Современная криптография пересекается с дисциплинами математики , информатики и электротехники . Приложения криптографии включают карты банкоматов , компьютерные пароли и электронную коммерцию .
Современная криптография в значительной степени основана на математической теории и практике компьютерной науки; криптографические алгоритмы разрабатываются на основе предположений о вычислительной сложности , что делает такие алгоритмы трудно поддающимися взлому на практике любым противником. Теоретически возможно взломать такую систему, но это невозможно сделать любыми известными практическими способами. Поэтому эти схемы называются вычислительно безопасными; теоретические достижения, например, усовершенствования алгоритмов факторизации целых чисел , и более быстрые вычислительные технологии требуют постоянной адаптации этих решений. Существуют информационно-теоретически безопасные схемы, которые, как доказано, не могут быть взломаны даже при неограниченной вычислительной мощности — примером является одноразовый блокнот — но эти схемы сложнее реализовать, чем лучшие теоретически взламываемые, но вычислительно безопасные механизмы.
Структура данных — это особый способ организации данных в компьютере, позволяющий эффективно их использовать . [13] [14]
Различные типы структур данных подходят для различных типов приложений, а некоторые из них узкоспециализированы для определенных задач. Например, базы данных используют индексы B-дерева для небольших процентов поиска данных, а компиляторы и базы данных используют динамические хэш-таблицы в качестве таблиц поиска.
Структуры данных предоставляют средства для эффективного управления большими объемами данных для таких применений, как большие базы данных и службы индексации в Интернете . Обычно эффективные структуры данных являются ключом к разработке эффективных алгоритмов . Некоторые формальные методы проектирования и языки программирования подчеркивают структуры данных, а не алгоритмы, как ключевой организующий фактор в разработке программного обеспечения. Хранение и извлечение могут выполняться для данных, хранящихся как в основной памяти , так и во вторичной памяти .
Распределенные вычисления изучают распределенные системы. Распределенная система — это программная система, в которой компоненты, расположенные на сетевых компьютерах, взаимодействуют и координируют свои действия путем передачи сообщений . [15] Компоненты взаимодействуют друг с другом для достижения общей цели. Три важные характеристики распределенных систем: параллелизм компонентов, отсутствие глобальных часов и независимый отказ компонентов. [15] Примеры распределенных систем варьируются от систем на основе SOA до многопользовательских онлайн-игр, одноранговых приложений и сетей блокчейнов, таких как Bitcoin .
Компьютерная программа , которая работает в распределенной системе, называется распределенной программой , а распределенное программирование — это процесс написания таких программ. [16] Существует множество альтернатив для механизма передачи сообщений, включая RPC-подобные соединители и очереди сообщений . Важной целью и проблемой распределенных систем является прозрачность местоположения .
Информационная сложность (IBC) изучает оптимальные алгоритмы и вычислительную сложность для непрерывных задач. IBC изучает непрерывные задачи, такие как интегрирование по траектории, уравнения в частных производных, системы обыкновенных дифференциальных уравнений, нелинейные уравнения, интегральные уравнения, неподвижные точки и очень высокоразмерное интегрирование.
Формальные методы — это особый вид математических методов для спецификации , разработки и проверки программных и аппаратных систем. [17] Использование формальных методов для проектирования программного и аппаратного обеспечения мотивировано ожиданием того, что, как и в других инженерных дисциплинах, выполнение соответствующего математического анализа может способствовать надежности и устойчивости проекта. [18]
Формальные методы лучше всего описываются как применение довольно широкого спектра теоретических основ компьютерной науки, в частности, логических исчислений, формальных языков , теории автоматов и семантики программ , а также систем типов и алгебраических типов данных к проблемам спецификации и проверки программного и аппаратного обеспечения. [19]
Теория информации — это раздел прикладной математики , электротехники и компьютерных наук, занимающийся квантификацией информации . Теория информации была разработана Клодом Э. Шенноном для поиска фундаментальных ограничений на операции обработки сигналов , такие как сжатие данных , а также на надежное хранение и передачу данных . С момента своего создания она расширилась, чтобы найти применение во многих других областях, включая статистический вывод , обработку естественного языка , криптографию , нейробиологию , [20] эволюцию [21] и функцию [22] молекулярных кодов, выбор модели в статистике, [23] теплофизику, [24] квантовые вычисления , лингвистику , обнаружение плагиата, [25] распознавание образов , обнаружение аномалий и другие формы анализа данных . [26]
Приложения фундаментальных тем теории информации включают сжатие данных без потерь (например, файлы ZIP ), сжатие данных с потерями (например, MP3 и JPEG ) и канальное кодирование (например, для цифровой абонентской линии (DSL) ). Область находится на стыке математики , статистики , информатики , физики , нейробиологии и электротехники . Ее влияние имело решающее значение для успеха миссий Voyager в дальний космос, изобретения компакт-диска, осуществимости мобильных телефонов, развития Интернета , изучения лингвистики и человеческого восприятия, понимания черных дыр и многих других областей. Важными подобластями теории информации являются исходное кодирование , канальное кодирование , теория алгоритмической сложности , алгоритмическая теория информации , информационно-теоретическая безопасность и меры информации.
Машинное обучение — это научная дисциплина , которая занимается разработкой и изучением алгоритмов , которые могут обучаться на основе данных. [27] Такие алгоритмы работают, создавая модель на основе входных данных [28] : 2 и используя ее для составления прогнозов или принятия решений, а не следуя только явно запрограммированным инструкциям.
Машинное обучение можно считать подразделом компьютерной науки и статистики . Оно тесно связано с искусственным интеллектом и оптимизацией , которые предоставляют методы, теорию и прикладные области для этой области. Машинное обучение используется в ряде вычислительных задач, где разработка и программирование явных алгоритмов на основе правил невозможны. Примерами приложений являются фильтрация спама , оптическое распознавание символов (OCR), [29] поисковые системы и компьютерное зрение . Машинное обучение иногда путают с интеллектуальным анализом данных , [30] хотя он больше фокусируется на исследовательском анализе данных. [31] Машинное обучение и распознавание образов «можно рассматривать как две грани одной и той же области». [28] : vii
Естественные вычисления [ 32] [33] , также называемые естественными вычислениями, — это терминология, введенная для охвата трех классов методов: 1) те, которые черпают вдохновение из природы для разработки новых методов решения проблем; 2) те, которые основаны на использовании компьютеров для синтеза природных явлений; и 3) те, которые используют природные материалы (например, молекулы) для вычислений. Основными областями исследований, которые составляют эти три ветви, являются искусственные нейронные сети , эволюционные алгоритмы , роевой интеллект , искусственные иммунные системы , фрактальная геометрия, искусственная жизнь , ДНК-вычисления и квантовые вычисления , среди прочих.
Вычислительные парадигмы, изучаемые естественными вычислениями, абстрагируются от таких разнообразных природных явлений, как саморепликация , функционирование мозга , дарвиновская эволюция , групповое поведение , иммунная система , определяющие свойства форм жизни, клеточные мембраны и морфогенез . Помимо традиционного электронного оборудования , эти вычислительные парадигмы могут быть реализованы на альтернативных физических носителях, таких как биомолекулы (ДНК, РНК) или квантовые вычислительные устройства с захваченными ионами.
Двойственно, можно рассматривать процессы, происходящие в природе, как обработку информации. Такие процессы включают самосборку , процессы развития , сети регуляции генов , сети взаимодействия белок-белок , сети биологического транспорта ( активный транспорт , пассивный транспорт ) и сборку генов в одноклеточных организмах . Попытки понять биологические системы также включают разработку полусинтетических организмов и понимание самой вселенной с точки зрения обработки информации. Действительно, была даже выдвинута идея, что информация более фундаментальна, чем материя или энергия. Тезис Цузе-Фредкина, относящийся к 1960-м годам, утверждает, что вся вселенная представляет собой огромный клеточный автомат , который непрерывно обновляет свои правила. [34] [35] Недавно было высказано предположение, что вся вселенная представляет собой квантовый компьютер , который вычисляет свое собственное поведение. [36]
Вселенная/природа как вычислительный механизм рассматривается посредством [37] исследования природы с помощью идей вычислимости и [38] изучения естественных процессов как вычислений (обработки информации).[39]
Параллельные вычисления — это форма вычислений , в которой многие вычисления выполняются одновременно, [40] работающая по принципу, что большие проблемы часто можно разделить на более мелкие, которые затем решаются «параллельно» . Существует несколько различных форм параллельных вычислений: параллелизм на уровне битов , на уровне инструкций , данных и задач . Параллелизм использовался в течение многих лет, в основном в высокопроизводительных вычислениях , но интерес к нему в последнее время возрос из-за физических ограничений, препятствующих масштабированию частоты . [41] Поскольку потребление энергии (и, следовательно, выделение тепла) компьютерами стало проблемой в последние годы, [42] параллельные вычисления стали доминирующей парадигмой в компьютерной архитектуре , в основном в форме многоядерных процессоров . [43]
Параллельные компьютерные программы писать сложнее, чем последовательные, [44], поскольку параллелизм вводит несколько новых классов потенциальных ошибок программного обеспечения , из которых наиболее распространены состояния гонки . Связь и синхронизация между различными подзадачами обычно являются одними из самых больших препятствий для получения хорошей производительности параллельной программы.
Максимально возможное ускорение одной программы в результате распараллеливания известно как закон Амдаля .
Теория языков программирования — это раздел компьютерной науки, который занимается разработкой, реализацией, анализом, характеристикой и классификацией языков программирования и их индивидуальных особенностей . Он входит в дисциплину теоретической компьютерной науки, как зависящую от математики , программной инженерии и лингвистики , так и влияющую на них . Это активная область исследований с многочисленными специализированными академическими журналами.
В теории языков программирования семантика — это область, занимающаяся строгим математическим изучением смысла языков программирования . Она делает это путем оценки смысла синтаксически допустимых строк , определенных конкретным языком программирования, показывая задействованные вычисления. В таком случае, если оценка будет касаться синтаксически недопустимых строк, результатом будет отсутствие вычислений. Семантика описывает процессы, которым следует компьютер при выполнении программы на этом конкретном языке. Это можно показать, описав связь между входом и выходом программы или объяснив, как программа будет выполняться на определенной платформе , тем самым создавая модель вычислений .
Квантовый компьютер — это вычислительная система, которая напрямую использует квантово-механические явления , такие как суперпозиция и запутанность , для выполнения операций с данными . [45] Квантовые компьютеры отличаются от цифровых компьютеров на основе транзисторов . В то время как цифровые компьютеры требуют, чтобы данные были закодированы в двоичные цифры ( биты ), каждый из которых всегда находится в одном из двух определенных состояний (0 или 1), квантовые вычисления используют кубиты (квантовые биты), которые могут находиться в суперпозициях состояний. Теоретической моделью является квантовая машина Тьюринга , также известная как универсальный квантовый компьютер. Квантовые компьютеры имеют теоретические сходства с недетерминированными и вероятностными компьютерами ; одним из примеров является способность находиться в более чем одном состоянии одновременно. Область квантовых вычислений была впервые представлена Юрием Маниным в 1980 году [46] и Ричардом Фейнманом в 1982 году. [47] [48] Квантовый компьютер со спинами в качестве квантовых битов был также сформулирован для использования в качестве квантового пространства-времени в 1968 году. [49]
Были проведены эксперименты, в которых квантовые вычислительные операции выполнялись на очень небольшом количестве кубитов. [50] Как практические, так и теоретические исследования продолжаются, и многие национальные правительства и военные финансирующие агентства поддерживают исследования квантовых вычислений для разработки квантовых компьютеров как для гражданских целей, так и для целей национальной безопасности, таких как криптоанализ . [51]
Компьютерная алгебра , также называемая символьным вычислением или алгебраическим вычислением, является научной областью, которая относится к изучению и разработке алгоритмов и программного обеспечения для манипулирования математическими выражениями и другими математическими объектами . Хотя, строго говоря, компьютерная алгебра должна быть подобластью научных вычислений , они, как правило, рассматриваются как отдельные области, поскольку научные вычисления обычно основаны на численных вычислениях с приблизительными числами с плавающей точкой , в то время как символьные вычисления подчеркивают точные вычисления с выражениями, содержащими переменные , которые не имеют никакого заданного значения и, таким образом, манипулируются как символы (отсюда и название символьных вычислений ).
Программные приложения, которые выполняют символьные вычисления, называются системами компьютерной алгебры , при этом термин «система» намекает на сложность основных приложений, которые включают, по крайней мере, метод представления математических данных на компьютере, пользовательский язык программирования (обычно отличающийся от языка, используемого для реализации), специализированный менеджер памяти, пользовательский интерфейс для ввода/вывода математических выражений, большой набор процедур для выполнения обычных операций, таких как упрощение выражений, дифференцирование с использованием цепного правила , разложение полинома на множители , неопределенное интегрирование и т. д.
Сверхбольшая интеграция ( СБИС ) — это процесс создания интегральной схемы (ИС) путем объединения тысяч транзисторов в одну микросхему. СБИС началась в 1970-х годах, когда разрабатывались сложные полупроводниковые и коммуникационные технологии. Микропроцессор — это устройство СБИС. До появления технологии СБИС большинство ИС имели ограниченный набор функций, которые они могли выполнять. Электронная схема могла состоять из ЦП , ПЗУ , ОЗУ и другой связующей логики . СБИС позволяет производителям ИС добавлять все эти схемы в одну микросхему.