Войти
Художественное представление машины Тьюринга. Машины Тьюринга используются для моделирования общих вычислительных устройств. Теоретическая информатика (TCS ) - это подмножество общего информатики и математики, которые фокусируется на более математических темах вычислений и включает теорию вычислений.
Трудно точно описать теоретические области. ACM Специальная группа вопросов по алгоритмов и теории вычислений (SIGACT) использует следующее описание:
TCS охватывает широкий спектр тем, включая алгоритмы, структуры данных, вычислительная сложность, параллельное и распределенное вычисление, вероятностное вычисление, квантовое вычисление, теория автоматов, теория информации, криптография, семантика программ и проверка, машинное обучение, вычислительная биология, вычислительная экономика, вычислительная геометрия и теория вычислительных чисел и алгебра. Работы в этой области часто отличаются упором на математическую технику и строгостью.
В то время как логический вывод и математическое доказательство существовали ранее, в 1931 году Курт Гёдель доказал, что его теорема о неполноте о том, что существуют фундаментальные ограничения на то, какие утверждения могут быть доказаны или опровергнуты.
Эти разработки ведут к современному изучению логики и вычислимости, а также к области теоретической информатики в целом. Теория информации была дополнена математической теорией коммуникации 1948 года, разработанной Клодом Шенноном. В том же десятилетии Дональд Хебб представил математическую модель обучения в мозге. По мере накопления биологических данных, подтверждающих эту гипотезу с некоторыми изменениями, были установлены области нейронных сетей и параллельной распределенной обработки. В 1971 году Стивен Кук и, независимо, Леонид Левин, доказали, что существуют практически актуальные проблемы, которые являются НП-полными - знаменательный результат в <565.>Теория вычислительной сложности.
С развертыванием квантовой механики в начале 20-го века появилась, согласно концепции математических операций над всей волновой функцией частиц. Другими словами, можно одновременно вычислять функции для нескольких состояний. Это привело к концепции квантового компьютера во второй половине 20-го века, которая получила распространение в 1990-х годах, когда Питер Шор показал, что такие методы передачи для разложения больших чисел на множители. полиномиальное время, которое, если оно будет реализовано, сделало бы некоторые современные алгоритмы криптографии с открытым ключом, такие как RSA_ (криптосистема) незащищенными.
Современные теоретические компьютерные исследования, основанные на этих разработках, включают множество других математических и междисциплинарных задач, которые были поставлены, как показано ниже:
алгоритм - это пошаговая процедура вычислений. Алгоритмы используются для вычислений, обработки данных и автоматического обоснования.
Алгоритм - это эффективный метод, выраженный как конечный список четко определенные инструкций для вычислений функции. Начало с начального состояния и начального ввода (возможно, пустой ), инструкции выполняют вычисление, которое, когда выполняется, выполняется через конечное число четко определенные последовательные состояния, в конечном итоге производящие «выход» и заканчивающиеся конечным конечным состоянием. Переход от одного состояния к другому не обязательно является детерминированным ; некоторые алгоритмы, известные как рандомизированные алгоритмы, включая случайный ввод.
Теория автоматов - это исследование абстрактных машин и автоматы, а также вычислительные задачи, которые могут быть решены с их помощью. Это теория теоретической информатики в разделе дискретная математика (раздел математики, а также информатики ). Автоматы проходят от греческого слова αὐτόματα, означающий «самодействующий».
Теория автоматов - это исследование самоуправляющихся виртуальных машин с целью помочь в логическом понимании ввода и вывода, без или с промежуточным этапом (этапами) вычислений (или любых функция / процесс).
Теория кодирования - это изучение свойств кодов и их пригодности для конкретного приложения. Коды используются для сжатия данных, криптографии, исправления ошибок, а в последнее время также для сетевого кодирования. Коды изучаются различными научными дисциплинами, такими как теория информации, электротехника, математика и информатика - с целью разработки эффективных и надежных методы передачи данных. Обычно это включает в себя удаление избыточности и исправление (или обнаружение) ошибок в передаваемых данных.
Вычислительная биология включает в себя применение и применение аналитических и теоретических методов данных, математического моделирования и методов компьютерного моделирования для изучения биологических, поведенческих и социальных систем. Область имеет широкое определение и включает основы информатики, прикладной математики, анимации, статистики, биохимии, химии, биофизика, молекулярная биология, генетика, геномика, экология, эволюция, анатомия, нейробиология и визуализация.
Вычислительная биология отличается от биологических вычислений, которые относятся к области компьютерных наук и компьютерная инженерия с использованием бинженерии и биологии для создания компьютеров, но аналогична биоинформатике, которая является междисциплинарной наукой, использующей компьютеры для хранения и обработки биологических данных.
Теория вычислительной сложности - это ветвь теории вычислений, которая фокусируется на классификации вычислительных проблем в соответствии с присущей им сложностью, и связывают эти классы друг с другом. Под вычислительной проблемой понимается задача, которая в принципе может быть решена компьютером, что эквивалентно заявлению о том, что проблема может быть решена механическим применением математических шагов, таких как алгоритм .
Проблема считается сложной по своей сути, если для ее решения требуются значительные ресурсы независимо от используемого алгоритма . Теория формализует эту интуицию, вводя математические модели вычислений для изучения этих проблем и количественно оценивая количество ресурсов, необходимых для их решений, таких как и память. Также используются другие меры сложности, такие как объем связи (используется в сложности цепи ), количество вентилей в (используется в сложность схемы ) и количество процессоров (используется в параллельных вычислений ). Одна из задач теории сложности вычислений - определить практические ограничения того, что компьютеры могут и что не могут делать.
Вычислительная геометрия - это раздел информатики, посвященный изучению алгоритмов, которые могут быть сформулированы в терминах геометрии. Некоторые геометрические проблемы возникают при изучении вычислительных геометрических алгоритмов. Хотя современная вычислительная геометрия появилась недавно, это одна из старейших вычислений, история которой восходит к глубокой древности. Древним предшественником является санскрит трактат Шульба-сутры, или «Правила аккорда», то есть книга алгоритмов, написанная в 800 г. до н.э. В книге прописаны пошаговые инструкции по созданию геометрических объектов, таких как алтари, с использованием колышка и хорды.
Основным стимулом для развития вычислительной геометрии как дисциплины был прогресс в компьютерной графике и автоматизированном проектировании и производстве (CAD / CAM ), но многие Проблемы вычислительной геометрии носят классический характер и могут исходить из математической визуализации.
Другие приложения вычислительной геометрии включают робототехнику (задачи планирования движения и видимости), географические информационные системы (GIS) (геометрическое положение и поиск, планирование маршрута), проектирование интегральных схем (проектирование и проверка геометрии ИС), автоматизированное проектирование (CAE) (создание сетки), компьютерное зрение (трехмерная реконструкция).
Теоретические результаты в машинном обучении в основном связаны с типом индуктивного обучения, называемым обучением с учителем. При обучении с учителем алгоритму получения образцов, которые помечены-либо полезным способом. Например, образцы могут быть описанием грибов, может быть указано, съедобны ли грибы. Алгоритм берет эти ранее помеченные образцы и их использует для создания классификатора. Этот классификатор представляет собой функцию, которая обозначает метки выборкам, включая образцы, которые ранее не просматривали алгоритмом. Цель алгоритма контролируемого обучения - оптимизировать некоторые показатели производительности, например свести к минимуму количества ошибок, сдел на новых выборках.
Вычислительная теория чисел, также известная как алгоритмическая теория чисел, представляет собой исследование алгоритмов для выполнения теории чисел. вычисления. Самая известная проблема в этой области - целочисленная факторизация.
Криптография - это практика и изучение методов безопасной связи в конкретных третьих лиц (называемых противники ). В более общем плане речь идет о построении данных протоколов, которые преодолевают влияние злоумышленников и связаны с особенностями в информационной безопасности, такими как данные конфиденциальность, целостность данных, аутентификация и предотвращение отказа. Современная криптография пересекает такие дисциплины, как математика, информатика и электротехника. К приложениям криптографии группы банкоматы, компьютерные пароли и электронная коммерция.
. Современная криптография в основе на основе математической теории и практики компьютерных наук; криптографические алгоритмы разработаны на основе предположений о вычислительной надежности, что затрудняет взлом таких алгоритмов на практике любым противником. Теоретически взломать такую систему, но невозможно сделать это какими-либо известными практическими средствами. Поэтому эти схемы являются безопасными в вычислительном отношении; Теоретические достижения, например усовершенствования алгоритмов целочисленной факторизации и более быстрые вычислительные технологии, требуют постоянной адаптации этих решений. Существуют теоретически безопасные схемы, которые доказаны не могут быть взломаны даже с неограниченной вычислительной мощностью -, одноразовый блокнот - но эти схемы труднее реализовать, чем лучшие теоретически разрушаемые, но вычислительно безопасные механизмы.
A структура данных - это особый способ организации данных на компьютере, чтобы их можно было использовать эффективно.
Различные типы структур данных подходят для различных типов приложений, а некоторые из них очень специализированы для решения конкретных задач. Например, базы данных используют индексы B-tree для небольшого процента извлечения данных и компиляторы, а базы данных используют динамические хэш-таблицы в качестве таблиц поиска.
Структуры пользовательских программных средств для эффективного управления большими объемами данных для таких целей, как большие базы данных и службы индексирования в Интернете. Обычно эффективные структуры являются ключом к разработке эффективных алгоритмов . Некоторые формальные методы проектирования и языки программирования делают упор на структурух данных, а не на алгоритмах, как на ключевой организующий фактор в разработке программного обеспечения. Сохранение и извлечение как для производства данных, хранящихся в основной памяти, так и во вторичной памяти.
Распределенные вычисления изучают распределенные системы. Распределенная система - это программная система, в которой компоненты расположены на сетевых компьютерах, обмениваются данные и координируют свои действия посредством передачи сообщений. Компоненты взаимодействуют друг с другом для достижения общей цели. Три важных характеристики распределенных систем: параллельность компонентов, отсутствие глобальных часов и независимый отказ компонентов. Примеры распределенных системных систем от систем на основе SOA до многопользовательских онлайн-игр до одноранговых приложений и сетей блокчейнов, таких как Биткойн.
A компьютерная программа, которое выполняется в распределенной системе, называется процесс распределенной программой, а распределенное программирование - это написания таких программ. Существует множество альтернативных механизмов передачи сообщений, включая RPC-подобные соединители и очереди сообщений. Важной целью и проблемой распределенных систем является прозрачность местоположения.
информационная сложность (IBC) изучает оптимальные алгоритмы и вычислительную сложность для непрерывных задач. IBC изучает непрерывные задачи, такие как интегрирование по траекториям, уравнения в частных производных, системы обыкновенных дифференциальных уравнений, нелинейные уравнения, интегральные уравнения, неподвижные точки и интегрирование очень высокой размерности.
Формальные методы - это особый вид математических методов, основанных на спецификации, разработке и проверке программные и аппаратные системы. Использование формальных методов проектирования программного обеспечения и аппаратного обеспечения ожидания того, что, как и других инженерных дисциплин, соответствующих математических методов обеспечения надежности и устойчивости проекта.
Формальные методы лучше всего описывать как применение довольно широкого разнообразия основ теоретической информатики, в частности логики исчислений, формальных языков, теории автоматов и семантики программ, но также систем типов и алгебраических типов данных к проблемам в спецификации и проверке программного обеспечения и аппаратного обеспечения.
Теория информации - это раздел прикладной математики, электротехники и информатики, включающий количественную оценку информации. Теория информации была заложена Клодом Э. Шенноном, чтобы найти фундаментальные методы ограничения операции , такие как сжатие данных и на надежное хранение и передача данных. С момента своего создания он расширился, чтобы найти приложения во многих других областях, включая статистический вывод, обработку естественного языка, криптографию, нейробиологию, эволюция и функции молекулярных кодов, выбор модели в статистике, теплофизике, квантовые вычисления, лингвистика, обнаружение плагиата, распознавание образов, обнаружение аномалий и другие формы анализа данных.
Приложения фундаментальных тем теории информации включают сжатие данных без потерь (например, файлы ZIP ), сжатие данных с потерями (например, MP3 и JPEG ) и канальное кодирование (например, для Digital Subscriber Line (DSL) ). Эта область находится на пересечении математики, статистики, информатики, физики, нейробиологии и электротехника. Его влияние было решающим для успеха миссий Voyager в дальний космос, изобретения компакт-диска, возможностей мобильных телефонов, развития Интернета, изучения лингвистика и человеческое восприятие, понимание черных дыр и многие другие области. Важными подполями теории информации являются кодирование источника, кодирование канала, теория алгоритмической сложности, теория алгоритмической информации, информация. -теоретическая безопасность и меры информации.
Машинное обучение - это научная дисциплина, которая занимается построением и изучением алгоритмов, которые могут учиться из данных. Такие алгоритмы работают, создавая модель на основе входных данных и используя ее для прогнозирования или принятия решений, а не следуя только явно запрограммированным инструкциям.
Машинное обучение можно рассматривать как подполе информатики и статистики. Он тесно связан с искусственным интеллектом и оптимизацией, которые предоставляют методы, теорию и прикладные области для работы в полевых условиях. Машинное обучение используется для решения ряда вычислительных задач, где разработка и программирование явных, основанных на правилах алгоритмов невозможно. Примеры приложений включают фильтрацию спама, оптическое распознавание символов (OCR), поисковые системы и компьютерное зрение. Машинное обучение иногда объединяют с интеллектуальным анализом данных, хотя это больше ориентировано на исследовательский анализ данных. Машинное обучение и распознавание образов "можно рассматривать как два аспекта одного и того же поля."
Параллельные вычисления - это форма вычислений, в котором многие вычисления выполняются одновременно, исходя из принципа, что большие проблемы часто можно разделить на более мелкие, которые затем решаются «параллельно». Существует несколько различных форм параллельных вычислений: битовый уровень, уровень инструкций, данные и параллелизм задач. Параллелизм использовался много лет, в основном в высокопроизводительных вычислениях, но интерес к нему в последнее время вырос из-за физических ограничений, препятствующих масштабированию частоты. Поскольку энергопотребление (и, как следствие, тепловыделение) компьютерами стало проблемой в последние годы, параллельные вычисления стали доминирующей парадигмой в компьютерной архитектуре, в основном в виде многоядерных процессоров.
Параллельные компьютерные программы сложнее писать, чем последовательные, потому что параллелизм вводит несколько новых классов потенциальных программных ошибок, из которых состояния гонки являются наиболее распространенными. Связь и синхронизация между различными подзадачами обычно являются одними из самых больших препятствий на пути к хорошей производительности параллельной программы.
Максимально возможное ускорение отдельной программы в результате распараллеливания известно как закон Амдала.
В теория языков программирования, семантика - это область, связанная со строгим математическим изучением значения языков программирования. Это делается путем оценки значения синтаксически допустимых строк, определенных конкретным языком программирования, показывая задействованные вычисления. В таком случае, если оценка будет синтаксически недопустимой строкой, результатом будет невычисление. Семантика описывает процессы, которым следует компьютер при выполнении программы на этом конкретном языке. Это можно показать, описав взаимосвязь между вводом и выводом программы или объяснив, как программа будет выполняться на определенной платформе, тем самым создав модель вычислений.
A квантовый компьютер - это система вычислений, которая напрямую использует квантово-механические явления, такие как суперпозиция и запутанность для выполнения операций с данными. Квантовые компьютеры отличаются от цифровых компьютеров на основе транзисторов. В то время как цифровые компьютеры требуют кодирования данных в двоичные цифры (биты ), каждое из которых всегда находится в одном из двух определенных состояний (0 или 1), в квантовых вычислениях используются кубиты (квантовые биты), которые могут находиться в суперпозиции состояний. Теоретической моделью является квантовая машина Тьюринга, также известная как универсальный квантовый компьютер. Квантовые компьютеры имеют теоретическое сходство с недетерминированными и вероятностными компьютерами ; один из примеров - возможность находиться в более чем одном состоянии одновременно. Сфера квантовых вычислений была впервые представлена Юрием Маниным в 1980 году и Ричардом Фейнманом в 1982 году. Квантовый компьютер со спинами в качестве квантовых битов был также разработан для использования в качестве квантовых пространство-время в 1968 году.
По состоянию на 2014 год квантовые вычисления все еще находятся в зачаточном состоянии, но были проведены эксперименты, в которых квантовые вычислительные операции выполнялись на очень небольшом количестве кубитов. Продолжаются как практические, так и теоретические исследования, и многие национальные правительства и военные финансовые агентства поддерживают исследования квантовых вычислений для разработки квантовых компьютеров как для гражданских, так и для целей национальной безопасности, таких как криптоанализ.
Компьютерная алгебра, также называемая символьным вычислением или алгебраическим вычислением, - это научная область, которая относится к изучению и разработке алгоритмов и программного обеспечения для управления математическими выражениями и другие математические объекты. Хотя, собственно говоря, компьютерная алгебра должна быть подполем научных вычислений, они обычно рассматриваются как отдельные области, поскольку научные вычисления обычно основаны на числовых вычислениях с приблизительной плавающей запятой. числа, тогда как символьное вычисление подчеркивает точное вычисление с выражениями, содержащими переменные, которые не имеют какого-либо заданного значения и, таким образом, обрабатываются как символы (отсюда и название символьного вычисления).
Программное обеспечение приложения, выполняющие символьные вычисления, называются системами компьютерной алгебры, при этом термин «система» указывает на сложность основных приложений, которые включают, по крайней мере, метод представления математических данных в компьютер, язык пользовательского программирования (обычно отличный от языка, используемого для реализации), выделенный менеджер памяти, пользовательский интерфейс для ввода / вывода математических выражений, большой набор подпрограмм для выполнения обычных операций, таких как упрощение выражений, дифференцирование с использованием правила цепочки, факторизация полинома, неопределенное интегрирование и т. Д.
Очень крупномасштабная интеграция (VLSI ) - это процесс создания интегральной схемы (IC) с помощью объединение тысяч транзисторов в одном кристалле. СБИС началась в 1970-х годах, когда разрабатывались сложные полупроводниковые и коммуникационные технологии. Микропроцессор - это устройство СБИС. До появления технологии СБИС большинство ИС имели ограниченный набор функций, которые они могли выполнять. Электронная схема может состоять из CPU, ROM, RAM и другой связующей логики. СБИС позволяет производителям интегральных схем объединить все эти схемы в одну микросхему.
| journal =()