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

Эта статья о отрасли информатики и математики. Информацию о журнале см. в разделе «Теоретическая информатика» (журнал) .

Теоретическая информатика — это раздел информатики и математики , который фокусируется на абстрактных и математических основах вычислений , таких как теория вычислений , теория формального языка , лямбда-исчисление и теория типов . [1]

Трудно точно очертить теоретические области. группа по интересам ACM ( Специальная по алгоритмам и теории вычислений SIGACT) предоставляет следующее описание: [2]

TCS охватывает широкий спектр тем, включая алгоритмы , структуры данных , сложность вычислений , параллельные и распределенные вычисления, вероятностные вычисления , квантовые вычисления , теорию автоматов , теорию информации , криптографию , программ семантику и верификацию , алгоритмическую теорию игр , машинное обучение , вычислительную биологию , вычислительная экономика , вычислительная геометрия , вычислительная теория чисел и алгебра . Работы в этой области часто отличаются упором на математическую технику и строгость .

История [ править ]

Основная статья: История информатики

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

Теория информации была добавлена ​​в эту область с появлением в 1948 году математической теории коммуникации Клода Шеннона . В том же десятилетии Дональд Хебб представил математическую модель обучения мозга. С накоплением биологических данных, подтверждающих эту гипотезу с некоторыми модификациями, были установлены области нейронных сетей и параллельной распределенной обработки . В 1971 году Стивен Кук и работая независимо , Леонид Левин , доказали, что существуют практически важные задачи, которые являются NP-полными , что стало знаковым результатом в теории сложности вычислений . [3]

Современные теоретические исследования в области информатики основаны на этих базовых разработках, но включают в себя множество других математических и междисциплинарных проблем, которые были поставлены, как показано ниже:

П = НП ?
Математическая логика Теория автоматов Теория чисел Теория графов Теория вычислимости Теория сложности вычислений
ГНИТИРВ-ТЕРЦЕС
Криптография Теория типов Теория категорий Вычислительная геометрия Комбинаторная оптимизация Теория квантовых вычислений

Темы [ править ]

Алгоритмы [ править ]

Основная статья: Алгоритм

Алгоритм – это пошаговая процедура вычислений. Алгоритмы используются для вычислений , обработки данных и автоматического рассуждения .

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

Теория автоматов [ править ]

Основная статья: Теория автоматов

Теория автоматов — это изучение абстрактных машин и автоматов , а также вычислительных задач, которые можно решить с их помощью. Это теория теоретической информатики в рамках дискретной математики (раздел математики , а также информатики ). Автоматы происходят от греческого слова αὐτόματα, означающего «самодействующий».

Теория автоматов - это исследование самодействующих виртуальных машин, которое помогает в логическом понимании процессов ввода и вывода без или с промежуточными этапами вычислений ( или любой функции /процесса).

Теория кодирования [ править ]

Основная статья: Теория кодирования

Теория кодирования — это изучение свойств кодов и их пригодности для конкретного применения. Коды используются для сжатия данных , криптографии , исправления ошибок , а в последнее время также для сетевого кодирования . Коды изучаются различными научными дисциплинами, такими как теория информации , электротехника , математика и информатика , с целью разработки эффективных и надежных передачи данных методов . Обычно это предполагает устранение избыточности и исправление (или обнаружение) ошибок в передаваемых данных.


Теория сложности вычислений [ править ]

Основная статья: Теория сложности вычислений

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

Проблема считается по своей сути сложной, если ее решение требует значительных ресурсов, независимо от используемого алгоритма . Теория формализует эту интуицию, вводя математические модели вычислений для изучения этих проблем и количественно определяя количество ресурсов, необходимых для их решения, таких как время и память. Также используются другие меры сложности , такие как объем связи (используется в сложности связи ), количество вентилей в схеме (используется в сложности схемы ) и количество процессоров (используется в параллельных вычислениях ). Одна из задач теории сложности вычислений — определить практические пределы того, что компьютеры могут и чего не могут делать.

Вычислительная геометрия [ править ]

Основная статья: Вычислительная геометрия

Вычислительная геометрия — это раздел информатики, посвященный изучению алгоритмов, которые можно сформулировать в терминах геометрии . Некоторые чисто геометрические проблемы возникают в результате изучения вычислительных геометрических алгоритмов, и такие проблемы также считаются частью вычислительной геометрии.

Основным толчком к развитию вычислительной геометрии как дисциплины стал прогресс в области компьютерной графики и систем автоматизированного проектирования и производства ( CAD / CAM ), однако многие задачи вычислительной геометрии носят классический характер и могут возникнуть в результате математической визуализации .

Другие важные применения вычислительной геометрии включают робототехнику (проблемы планирования движения и видимости), географические информационные системы (ГИС) (геометрическое местоположение и поиск, планирование маршрута), проектирование интегральных схем (проектирование и проверка геометрии ИС), автоматизированное проектирование (CAE). (генерация сетки), компьютерное зрение (3D реконструкция).

обучения вычислительного Теория ​

Основная статья: Теория вычислительного обучения

Теоретические результаты в машинном обучении в основном касаются типа индуктивного обучения, называемого обучением с учителем. При обучении с учителем алгоритму предоставляются образцы, помеченные некоторыми полезный способ. Например, образцы могут представлять собой описания грибов, а на этикетках может быть указано, съедобны ли грибы или нет. Алгоритм берет эти предварительно помеченные образцы и использует их для создания классификатора. Этот классификатор представляет собой функцию, которая присваивает метки образцам, включая образцы, которые алгоритм ранее никогда не видел. Целью алгоритма контролируемого обучения является оптимизация некоторых показателей производительности, например минимизация количества ошибок, допущенных на новых образцах.

чисел Вычислительная ​ теория

Основная статья: Вычислительная теория чисел

Вычислительная теория чисел , также известная как алгоритмическая теория чисел , представляет собой исследование алгоритмов выполнения теоретико-числовых вычислений . Самая известная проблема в этой области — факторизация целых чисел .

Криптография [ править ]

Основная статья: Криптография

Криптография — это практика и изучение методов безопасной связи в присутствии третьих лиц (называемых злоумышленниками ). [11] В более общем плане речь идет о построении и анализе протоколов , которые преодолевают влияние злоумышленников. [12] и которые связаны с различными аспектами информационной безопасности, такими как конфиденциальность данных , целостность данных , аутентификация и неотказуемость . [13] Современная криптография пересекается с дисциплинами математики , информатики и электротехники . Приложения криптографии включают карты банкоматов , компьютерные пароли и электронную коммерцию .

Современная криптография в значительной степени основана на математической теории и практике информатики; Криптографические алгоритмы разрабатываются на основе предположений о вычислительной сложности , что делает такие алгоритмы трудно взломанными на практике любым противником. Сломать такую ​​систему теоретически возможно, но невозможно сделать это любыми известными практическими способами. Поэтому эти схемы называются вычислительно безопасными; теоретические достижения, например, усовершенствования алгоритмов факторизации целых чисел и более быстрые вычислительные технологии, требуют постоянной адаптации этих решений. Существуют теоретически безопасные схемы, которые, очевидно, невозможно взломать даже при неограниченной вычислительной мощности (примером является одноразовый блокнот) , но эти схемы сложнее реализовать, чем лучшие теоретически взламываемые, но вычислительно безопасные механизмы.

Структуры данных [ править ]

Основная статья: Структура данных

Структура данных – это особый способ организации данных в компьютере, позволяющий их эффективно использовать . [14] [15]

Различные типы структур данных подходят для разных типов приложений, а некоторые узкоспециализированы для конкретных задач. Например, базы данных используют индексы B-дерева для небольшого процента поиска данных, а компиляторы и базы данных используют динамические хеш-таблицы в качестве таблиц поиска.

Структуры данных предоставляют средства для эффективного управления большими объемами данных для таких целей, как большие базы данных и службы индексирования в Интернете . Обычно эффективные структуры данных являются ключом к разработке эффективных алгоритмов . Некоторые формальные методы проектирования и языки программирования подчеркивают, что структуры данных, а не алгоритмы, являются ключевым организующим фактором при разработке программного обеспечения. Сохранение и извлечение данных может осуществляться как в основной, так и во вторичной памяти .

Распределенные вычисления [ править ]

Основная статья: Распределенные вычисления

Распределенные вычисления изучают распределенные системы. Распределенная система — это программная система, в которой компоненты, расположенные на сетевых компьютерах, взаимодействуют и координируют свои действия посредством передачи сообщений . [16] Компоненты взаимодействуют друг с другом для достижения общей цели. Тремя важными характеристиками распределенных систем являются: конкурентность компонентов, отсутствие глобальных часов и независимый отказ компонентов. [16] Примеры распределенных систем варьируются от систем на основе SOA до многопользовательских онлайн-игр, одноранговых приложений и сетей блокчейна, таких как Биткойн .

, Компьютерная программа работающая в распределенной системе, называется распределенной программой , а распределенное программирование — это процесс написания таких программ. [17] Существует множество альтернатив механизму передачи сообщений, включая RPC-подобные соединители и очереди сообщений . Важной целью и задачей распределенных систем является прозрачность местоположения .

Информационная сложность ​ ​

Основная статья: Информационная сложность

Информационная сложность (IBC) изучает оптимальные алгоритмы и вычислительную сложность для непрерывных задач. IBC изучал непрерывные задачи, такие как интегрирование по траекториям, уравнения в частных производных, системы обыкновенных дифференциальных уравнений, нелинейные уравнения, интегральные уравнения, неподвижные точки и интегрирование очень высокой размерности.

Формальные методы [ править ]

Основная статья: Формальные методы

Формальные методы это особый вид математических методов для спецификации , разработки и проверки программных — и аппаратных систем. [18] Использование формальных методов проектирования программного и аппаратного обеспечения мотивировано ожиданием того, что, как и в других инженерных дисциплинах, выполнение соответствующего математического анализа может способствовать надежности и устойчивости проекта. [19]

Формальные методы лучше всего описать как применение довольно широкого спектра теоретических основ информатики, в частности, логических исчислений, формальных языков , теории автоматов и семантики программ , а также систем типов и алгебраических типов данных для решения проблем, связанных со спецификацией программного и аппаратного обеспечения и проверка. [20]

Теория информации [ править ]

Основная статья: Теория информации

Теория информации — раздел прикладной математики , электротехники и информатики, занимающийся оценкой информации количественной . Теория информации была разработана Клодом Э. Шенноном, чтобы найти фундаментальные ограничения на операции обработки сигналов , такие как сжатие данных , а также на надежное хранение и передачу данных. С момента своего создания он расширился и нашел применение во многих других областях, включая статистический вывод , обработку естественного языка , криптографию , нейробиологию и т. д . [21] эволюция [22] и функция [23] молекулярных кодов, выбор моделей в статистике, [24] теплофизика, [25] квантовые вычисления , лингвистика , обнаружение плагиата, [26] Распознавание образов , обнаружение аномалий и другие формы анализа данных . [27]

Приложения фундаментальных тем теории информации включают сжатие данных без потерь (например, ZIP-файлов ), сжатие данных с потерями (например, MP3 и JPEG ) и кодирование каналов (например, для цифровой абонентской линии (DSL) ). Эта область находится на стыке математики , статистики , информатики , физики , нейробиологии и электротехники . Его влияние имело решающее значение для успеха миссий «Вояджера» в глубокий космос, изобретения компакт-диска, возможности мобильных телефонов, развития Интернета , изучения лингвистики и человеческого восприятия, понимания черных дыр . и многие другие области. Важными подобластями теории информации являются исходное кодирование , канальное кодирование , теория алгоритмической сложности , алгоритмическая теория информации , теоретико-информационная безопасность и меры информации.

Машинное обучение [ править ]

Основная статья: Машинное обучение

Машинное обучение — это научная дисциплина , которая занимается созданием и изучением алгоритмов , способных обучаться на основе данных. [28] Такие алгоритмы работают путем построения модели на основе входных данных. [29] : 2  и использовать это для прогнозирования или принятия решений, а не следовать только явно запрограммированным инструкциям.

Машинное обучение можно считать подобластью информатики и статистики . Он имеет прочные связи с искусственным интеллектом и оптимизацией , которые предоставляют методы, теорию и области применения в этой области. Машинное обучение используется в ряде вычислительных задач, где разработка и программирование явных алгоритмов , основанных на правилах , невозможно. Примеры приложений включают фильтрацию спама , оптическое распознавание символов (OCR), [30] поисковые системы и компьютерное зрение . Машинное обучение иногда путают с интеллектуальным анализом данных . [31] хотя здесь больше внимания уделяется исследовательскому анализу данных. [32] Машинное обучение и распознавание образов «можно рассматривать как два аспекта то же поле». [29] : vii

Естественные вычисления [ править ]

Этот раздел представляет собой отрывок из книги Natural Computing . [ редактировать ]

Естественные вычисления , [33] [34] Также называемые естественными вычислениями, это терминология, введенная для обозначения трех классов методов: 1) тех, которые черпают вдохновение из природы для разработки новых методов решения проблем; 2) основанные на использовании компьютеров для синтеза явлений природы; и 3) те, которые используют для вычислений природные материалы (например, молекулы). Основными областями исследований, которые составляют эти три направления, являются искусственные нейронные сети , эволюционные алгоритмы , роевой интеллект , искусственные иммунные системы , фрактальная геометрия, искусственная жизнь , вычисления ДНК и квантовые вычисления , среди других.

Вычислительные парадигмы, изучаемые естественными вычислениями, абстрагируются от таких разнообразных природных явлений, как самовоспроизведение , функционирование мозга , дарвиновская эволюция , групповое поведение , иммунная система , определяющие свойства форм жизни, клеточные мембраны и морфогенез . Помимо традиционного электронного оборудования , эти вычислительные парадигмы могут быть реализованы на альтернативных физических носителях, таких как биомолекулы (ДНК, РНК) или квантовые вычислительные устройства с захваченными ионами.

Двояко можно рассматривать процессы, происходящие в природе, как обработку информации. К таким процессам относятся самосборка , процессы развития , сети регуляции генов , сети белок-белкового взаимодействия , сети биологического транспорта ( активный транспорт , пассивный транспорт ) и сборка генов в одноклеточных организмах . Усилия попонимание биологических систем также включает создание полусинтетических организмов и понимание самой Вселенной с точки зрения обработки информации. Действительно, была даже выдвинута идея, что информация более фундаментальна, чем материя или энергия. Тезис Цузе-Фредкина, датируемый 1960-ми годами, утверждает, что вся Вселенная представляет собой огромный клеточный автомат , который постоянно обновляет свои правила. [35] [36] Недавно было высказано предположение, что вся Вселенная представляет собой квантовый компьютер , который рассчитывает свое собственное поведение. [37]

Вселенная/природа как вычислительный механизм рассматриваются: [38] исследование природы с помощью идей вычислимости и [39] изучение природных процессов как вычислений (обработки информации).

[40]

Параллельное вычисление [ править ]

Основная статья: Параллельные вычисления

Параллельные вычисления — это форма вычислений, при которой множество вычислений выполняются одновременно. [41] действуя по принципу, что большие проблемы часто можно разделить на более мелкие, которые затем решаются «параллельно» . Существует несколько различных форм параллельных вычислений: битовый уровень , уровень команд , данных и параллелизм задач . Параллелизм использовался в течение многих лет, в основном в высокопроизводительных вычислениях , но в последнее время интерес к нему вырос из-за физических ограничений, препятствующих масштабированию частоты . [42] Поскольку энергопотребление (и, следовательно, выделение тепла) компьютерами в последние годы стало проблемой, [43] параллельные вычисления стали доминирующей парадигмой в компьютерной архитектуре , главным образом в виде многоядерных процессоров . [44]

Параллельные компьютерные программы писать труднее, чем последовательные. [45] потому что параллелизм вводит несколько новых классов потенциальных ошибок программного обеспечения , из которых состояния гонки наиболее распространены . Связь и синхронизация между различными подзадачами обычно являются одними из самых серьезных препятствий на пути к достижению хорошей производительности параллельных программ.

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

Теория языка программирования и семантика программ [ править ]

Основные статьи: Теория языков программирования и семантика программ.

Теория языков программирования — это раздел информатики, который занимается проектированием, реализацией, анализом, характеристикой и классификацией языков программирования и их индивидуальных особенностей . Она относится к дисциплине теоретической информатики и зависит как от математики , разработки программного обеспечения, так и от лингвистики . Это активная исследовательская область, в которой издается множество специализированных академических журналов.

В теории языков программирования семантика — это область, занимающаяся строгим математическим исследованием смысла языков программирования . Для этого он оценивает значение синтаксически допустимых строк, определенных конкретным языком программирования, и показывает необходимые вычисления. В таком случае, если вычисление будет состоять из синтаксически недопустимых строк, результатом будет отсутствие вычислений. Семантика описывает процессы, которым следует компьютер при выполнении программы на этом конкретном языке. Это можно продемонстрировать, описав взаимосвязь между входными и выходными данными программы или объяснив, как программа будет выполняться на определенной платформе , и, следовательно, создав модель вычислений .

Квантовые вычисления [ править ]

Основная статья: Квантовые вычисления

Квантовый компьютер — это вычислительная система, которая напрямую использует квантово-механические явления , такие как суперпозиция и запутанность , для выполнения операций с данными . [46] Квантовые компьютеры отличаются от цифровых компьютеров на транзисторах . В то время как цифровые компьютеры требуют, чтобы данные были закодированы в двоичные цифры ( биты ), каждая из которых всегда находится в одном из двух определенных состояний (0 или 1), квантовые вычисления используют кубиты (квантовые биты), которые могут находиться в суперпозициях состояний. Теоретической моделью является квантовая машина Тьюринга , также известная как универсальный квантовый компьютер. Квантовые компьютеры имеют теоретическое сходство с недетерминированными и вероятностными компьютерами ; Одним из примеров является способность находиться в более чем одном состоянии одновременно. Область квантовых вычислений была впервые представлена ​​Юрием Маниным в 1980 году. [47] и Ричард Фейнман в 1982 году. [48] [49] Квантовый компьютер со спинами в виде квантовых битов также был разработан для использования в качестве квантового пространства-времени в 1968 году. [50]

Были проведены эксперименты, в которых квантовые вычислительные операции выполнялись на очень небольшом количестве кубитов. [51] Как практические, так и теоретические исследования продолжаются, и многие национальные правительства и военные финансирующие агентства поддерживают исследования в области квантовых вычислений для разработки квантовых компьютеров как для гражданских целей, так и для целей национальной безопасности, таких как криптоанализ . [52]

Символьное вычисление [ править ]

Основная статья: Символьное вычисление

Компьютерная алгебра , также называемая символическими вычислениями или алгебраическими вычислениями, — это научная область, которая относится к изучению и разработке алгоритмов и программного обеспечения для управления математическими выражениями и другими математическими объектами . Хотя, собственно говоря, компьютерная алгебра должна быть подобластью научных вычислений , их обычно рассматривают как отдельные области, поскольку научные вычисления обычно основаны на числовых вычислениях с приблизительными числами с плавающей запятой , в то время как символьные вычисления делают упор на точные вычисления с выражениями, содержащими переменные , которые не имеют любое заданное значение и, таким образом, ими манипулируют как с символами (отсюда и название символьных вычислений ).

Программные приложения, выполняющие символьные вычисления, называются системами компьютерной алгебры , причем термин «система» указывает на сложность основных приложений, которые включают, по крайней мере, метод представления математических данных на компьютере, язык пользовательского программирования (обычно отличающийся от языка используемый для реализации), выделенный менеджер памяти, пользовательский интерфейс для ввода/вывода математических выражений, большой набор подпрограмм для выполнения обычных операций, таких как упрощение выражений, дифференцирование с использованием цепного правила , полиномиальная факторизация , неопределенное интегрирование и т.д. .

масштабная интеграция Очень ​

Основная статья: СБИС

Очень большая интеграция ( СБИС ) — это процесс создания интегральной схемы (ИС) путем объединения тысяч транзисторов в один чип. СБИС зародилась в 1970-х годах, когда сложные полупроводниковые и коммуникационные разрабатывались технологии. Микропроцессор представляет собой устройство СБИС. До внедрения технологии СБИС большинство микросхем имели ограниченный набор функций, которые они могли выполнять. Электронная схема может состоять из ЦП , ПЗУ , ОЗУ и другой связующей логики . СБИС позволяет производителям микросхем объединять все эти схемы в один чип.

Организации [ править ]

Журналы и информационные бюллетени [ править ]

Конференции [ править ]

См. также [ править ]

Примечания [ править ]

  1. ^ «Теоретическая информатика» . НаукаДирект .
  2. ^ «СИГАКТ» . Проверено 19 января 2017 г.
  3. ^ Кук, Стивен А. (3 мая 1971 г.). «Сложность процедур доказательства теорем» . Материалы третьего ежегодного симпозиума ACM по теории вычислений - STOC '71 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 151–158. дои : 10.1145/800157.805047 . ISBN  978-1-4503-7464-4 .
  4. ^ «Например, любой классический математический алгоритм можно описать конечным числом английских слов». Роджерс, Хартли младший (1967). Теория рекурсивных функций и эффективная вычислимость . МакГроу-Хилл. Страница 2.
  5. ^ Четко определено в отношении агента, выполняющего алгоритм: «Существует вычислительный агент, обычно человек, который может реагировать на инструкции и выполнять вычисления» ( Rogers 1967 , стр. 2).
  6. ^ «Алгоритм - это процедура вычисления функции (относительно некоторых выбранных обозначений целых чисел) ... это ограничение (числовых функций) не приводит к потере общности» ( Rogers 1967 , стр. 1).
  7. ^ «Алгоритм имеет ноль или более входных данных, то есть величин , которые ему задаются изначально до начала работы алгоритма» (Кнут 1973:5).
  8. ^ «Процедура, которая обладает всеми характеристиками алгоритма, за исключением того, что ей, возможно, не хватает конечности, может быть названа« вычислительным методом »» (Кнут 1973:5).
  9. ^ «Алгоритм имеет один или несколько выходных данных, то есть величины, которые имеют определенное отношение к входным данным» (Кнут 1973:5).
  10. ^ Является ли процесс со случайными внутренними процессами (не включая входные) алгоритмом, является дискуссионным. Роджерс полагает, что: «вычисление осуществляется дискретно, поэтапно, без использования непрерывных методов или аналоговых устройств… осуществляется детерминированно, без обращения к случайным методам или устройствам, например, играм в кости» ( Rogers 1967 , с. 2).
  11. ^ Ривест, Рональд Л. (1990). «Криптология». В Дж. Ван Леувене (ред.). Справочник по теоретической информатике . Том. 1. Эльзевир.
  12. ^ Белларе, Михир; Рогауэй, Филипп (21 сентября 2005 г.). "Введение". Введение в современную криптографию . п. 10.
  13. ^ Менезес, AJ; ван Ооршот, ПК; Ванстон, ЮАР (1997). Справочник по прикладной криптографии . Тейлор и Фрэнсис. ISBN  978-0-8493-8523-0 .
  14. ^ Пол Э. Блэк (ред.), запись о структуре данных в Словаре алгоритмов и структур данных . США Национальный институт стандартов и технологий . 15 декабря 2004 г. Интернет-версия , по состоянию на 21 мая 2009 г.
  15. ^ входных Структура данных в Британской энциклопедии (2009) . Интернет-запись доступна 21 мая 2009 года.
  16. ^ Перейти обратно: а б Кулурис, Джордж; Джин Доллимор ; Тим Киндберг; Гордон Блэр (2011). Распределенные системы: концепции и проектирование (5-е изд.). Бостон: Аддисон-Уэсли. ISBN  978-0-132-14301-1 .
  17. ^ Гош, Сукумар (2007). Распределенные системы – алгоритмический подход . Чепмен и Холл/CRC. п. 10. ISBN  978-1-58488-564-1 .
  18. ^ Р. У. Батлер (6 августа 2001 г.). «Что такое формальные методы?» . Проверено 16 ноября 2006 г.
  19. ^ К. Майкл Холлоуэй. «Почему инженерам следует использовать формальные методы» (PDF) . 16-я конференция по системам цифровой авионики (27–30 октября 1997 г.). Архивировано из оригинала (PDF) 16 ноября 2006 года . Проверено 16 ноября 2006 г.
  20. ^ Монин, стр.3–4.
  21. ^ Ф. Рике; Д. Варланд; Р. Рюйтер ван Стивенинк; В Бялек (1997). Спайкс: исследование нейронного кода . Пресса МТИ. ISBN  978-0262681087 .
  22. ^ Хюльзенбек, JP; Ронквист, Ф.; Нильсен, Р.; Болбак, JP (14 декабря 2001 г.). «Байесовский вывод филогении и его влияние на эволюционную биологию». Наука . 294 (5550). Американская ассоциация содействия развитию науки (AAAS): 2310–2314. Бибкод : 2001Sci...294.2310H . дои : 10.1126/science.1065889 . ISSN   0036-8075 . ПМИД   11743192 . S2CID   2138288 .
  23. ^ Рандо Алликметс, Уайет В. Вассерман, Эми Хатчинсон, Филип Смоллвуд, Джереми Натанс, Питер К. Роган, Томас Д. Шнайдер , Майкл Дин (1998) Организация гена ABCR: анализ последовательностей промотора и сплайсингового соединения, Ген 215 : 1, 111–122
  24. ^ Бернхэм, К.П. и Андерсон Д.Р. (2002) Выбор модели и многомодельный вывод: практический информационный подход, второе издание (Springer Science, Нью-Йорк) ISBN   978-0-387-95364-9 .
  25. ^ Джейнс, ET (15 мая 1957 г.). «Теория информации и статистическая механика». Физический обзор . 106 (4). Американское физическое общество (APS): 620–630. Бибкод : 1957PhRv..106..620J . дои : 10.1103/physrev.106.620 . ISSN   0031-899X . S2CID   17870175 .
  26. ^ Чарльз Х. Беннетт, Мин Ли и Бин Ма (2003) Письма счастья и эволюционные истории. Архивировано 7 октября 2007 г. в Wayback Machine , Scientific American 288 : 6, 76–81.
  27. ^ Дэвид Р. Андерсон (1 ноября 2003 г.). «Некоторые сведения о том, почему люди, занимающиеся эмпирическими науками, могут захотеть лучше понять методы теории информации» (PDF) . Архивировано из оригинала (PDF) 23 июля 2011 года . Проверено 23 июня 2010 г.
  28. ^ Рон Ковахи; Фостер Провост (1998). «Словарь терминов» . Машинное обучение . 30 : 271–274. дои : 10.1023/A:1007411609915 .
  29. ^ Перейти обратно: а б КМ Бишоп (2006). Распознавание образов и машинное обучение . Спрингер. ISBN  978-0-387-31073-2 .
  30. ^ Верник, Янг, Бранков, Юрганов и Стротер, Машинное обучение в медицинской визуализации, Журнал обработки сигналов IEEE , том. 27, нет. 4, июль 2010 г., стр. 25–38.
  31. ^ Маннила, Хейкки (1996). Интеллектуальный анализ данных: машинное обучение, статистика и базы данных . Международная конференция. Управление научными и статистическими базами данных. Компьютерное общество IEEE.
  32. ^ Фридман, Джером Х. (1998). «Интеллектуальный анализ данных и статистика: какая связь?». Информатика и статистика . 29 (1): 3–9.
  33. ^ Г.Розенберг, Т.Бак, Дж.Кок, редакторы, Справочник по естественным вычислениям, Springer Verlag, 2012 г.
  34. ^ А.Брабазон, МО'Нил, С.МакГарраги. Естественные вычислительные алгоритмы , Springer Verlag, 2015 г.
  35. ^ Фредкин, Ф. Цифровая механика: информационный процесс, основанный на обратимом универсальном CA. Физика Д 45 (1990) 254-270.
  36. ^ Цузе, К. Вычислительное пространство. Электронная обработка данных 8 (1967) 336-344.
  37. ^ Ллойд, С. Программирование Вселенной: ученый, занимающийся квантовыми компьютерами, изучает космос . Кнопф, 2006 г.
  38. ^ Зенил, Х. Вычислимая Вселенная: понимание и исследование природы как вычисления . Всемирное научное издательство, 2012 г.
  39. ^ Додиг-Црнкович, Г. и Джованьоли, Р. ВЫЧИСЛИТЕЛЬНАЯ ПРИРОДА . Спрингер, 2013 г.
  40. ^ Розенберг, Гжегож (февраль 2001 г.). «Естественные вычисления». Современные тенденции в теоретической информатике : 543–690. дои : 10.1142/9789812810403_0005 . ISBN  978-981-02-4473-6 .
  41. ^ Готлиб, Аллан; Алмаси, Джордж С. (1989). Высокопараллельные вычисления . Редвуд-Сити, Калифорния: Бенджамин/Каммингс. ISBN  978-0-8053-0177-9 .
  42. ^ С.В. Адве и др. (ноябрь 2008 г.). «Исследования в области параллельных вычислений в Иллинойсе: программа UPCRC». Архивировано 9 декабря 2008 г. в Wayback Machine (PDF). Parallel@Illinois, Университет Иллинойса в Урбана-Шампейн. «Основные методы достижения этих преимуществ в производительности – повышение тактовой частоты и более умные, но все более сложные архитектуры – сейчас наталкиваются на так называемую стену мощности. Компьютерная индустрия признала, что будущий рост производительности должен в основном происходить за счет увеличения количества процессоров (или ядер). ) на кристалле, а не заставлять одно ядро ​​работать быстрее».
  43. ^ Асанович и др. Старое [традиционное мнение]: Электроэнергия бесплатна, но транзисторы дороги. Новое [традиционное мнение] заключается в том, что энергия стоит дорого, но транзисторы «бесплатны».
  44. ^ Асанович, Крсте и др. (18 декабря 2006 г.). «Пейзаж исследований в области параллельных вычислений: взгляд из Беркли» (PDF) . Калифорнийский университет, Беркли. Технический отчет № UCB/EECS-2006-183. «Старое [традиционное мнение]: увеличение тактовой частоты является основным методом улучшения производительности процессора. Новое [традиционное мнение]: увеличение параллелизма является основным методом улучшения производительности процессора… Даже представители Intel, компании, обычно ассоциирующейся с чем выше тактовая частота, тем лучше», предупредил, что традиционные подходы к максимизации производительности за счет максимизации тактовой частоты доведены до предела».
  45. ^ Хеннесси, Джон Л.; Паттерсон, Дэвид А.; Ларус, Джеймс Р. (1999). Компьютерная организация и проектирование: аппаратно-программный интерфейс (2-е изд., 3-е печат. изд.). Сан-Франциско: Кауфманн. ISBN  978-1-55860-428-5 .
  46. ^ « Квантовые вычисления с молекулами ». Статья в журнале Scientific American Исаака Нила Гершенфельда и Л. Чуанга
  47. ^ Манин, Ю. И. (1980). и Вычислимое невычислимое . Сов.Радио. стр. 13–15. Архивировано из оригинала 10 мая 2013 года . Проверено 4 марта 2013 г.
  48. ^ Фейнман, Р.П. (1982). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики . 21 (6): 467–488. Бибкод : 1982IJTP...21..467F . CiteSeerX   10.1.1.45.9310 . дои : 10.1007/BF02650179 . S2CID   124545445 .
  49. ^ Дойч, Дэвид (6 января 1992 г.). «Квантовые вычисления». Мир физики . 5 (6): 57–61. дои : 10.1088/2058-7058/5/6/38 .
  50. ^ Финкельштейн, Дэвид (1968). «Пространственно-временная структура в высокоэнергетических взаимодействиях». Ин Гудехус, Т.; Кайзер, Г. (ред.). Фундаментальные взаимодействия при высоких энергиях . Нью-Йорк: Гордон и Брич.
  51. ^ «Новый контроль кубитов служит хорошим предзнаменованием для будущего квантовых вычислений» . Проверено 26 октября 2014 г.
  52. ^ Дорожная карта квантовой информатики и технологий, чтобы понять, в каком направлении движутся исследования.
  53. ^ Перейти обратно: а б с д и Австралийский рейтинг конференций по ИКТ за 2007 год. Архивировано 2 октября 2009 года в Wayback Machine : уровень A+.
  54. ^ «МФКС 2017» . Архивировано из оригинала 10 января 2018 г. Проверено 9 января 2018 г.
  55. ^ КСО 2018
  56. ^ Перейти обратно: а б с д и ж г час я дж Австралийский рейтинг конференций по ИКТ за 2007 год. Архивировано 2 октября 2009 года в Wayback Machine : уровень A.
  57. ^ FCT 2011 (получено 3 июня 2013 г.)

Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Theoretical_computer_science&oldid=1224893969"