Теоретическая информатика - Theoretical computer science

Эта статья посвящена области информатики и математики. Для журнала см. Теоретическая информатика (журнал) .
Художественное представление машины Тьюринга . Машины Тьюринга используются для моделирования вычислительных устройств общего назначения.

Теоретическая информатика ( TCS ) - это часть общей информатики и математики, которая фокусируется на математических аспектах информатики, таких как теория вычислений , лямбда-исчисление и теория типов .

Трудно точно очертить теоретические области. ACM «s Special Interest Group по алгоритмам и теории вычислений (SIGACT) дает следующее описание:

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

История

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

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

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

С развитием квантовой механики в начале 20 века появилась концепция, согласно которой математические операции могут выполняться над всей волновой функцией частицы. Другими словами, можно одновременно вычислять функции для нескольких состояний. Это привело к концепции квантового компьютера во второй половине 20-го века, которая получила распространение в 1990-х годах, когда Питер Шор показал, что такие методы могут использоваться для разложения больших чисел на множители за полиномиальное время , что, в случае их реализации, сделало бы некоторые современные алгоритмы шифрования с открытым ключом , такие как RSA_ (криптосистема), небезопасны.

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

DFAexample.svg Эллиптическая кривая simple.png 6n-graf.svg Ван tile.svg P = NP  ?
Математическая логика Теория автоматов Теория чисел Теория графов Теория вычислимости Теория вычислительной сложности
ГНИТИРВ-ТЕРСЕС Коммутативная диаграмма для morphism.svg SimplexRangeSearching.svg TSP Deutschland 3.png Blochsphere.svg
Криптография Теория типов Теория категорий Вычислительная геометрия Комбинаторная оптимизация Теория квантовых вычислений

Темы

Алгоритмы

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

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

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

Теория автоматов

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

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

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

Теория кодирования

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

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

Вычислительная биология

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

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

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

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

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

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

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

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

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

Вычислительная геометрия - это раздел информатики, посвященный изучению алгоритмов, которые могут быть сформулированы в терминах геометрии . Некоторые чисто геометрические проблемы возникают в результате изучения вычислительных геометрических алгоритмов, и такие проблемы также считаются частью вычислительной геометрии. Хотя современная вычислительная геометрия появилась недавно, это одна из старейших областей вычислений, история которой восходит к глубокой древности. Древним предшественником является санскритский трактат « Шульба-сутры» , или «Правила аккорда», то есть книга алгоритмов, написанная в 800 г. до н. Э. В книге прописаны пошаговые инструкции по созданию геометрических объектов, таких как алтари, с использованием колышка и хорды.

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

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

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

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

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

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

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

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

Криптография

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

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

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

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

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

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

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

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

Распределенные вычисления

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

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

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

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

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

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

Формальные методы

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

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

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

Теория информации

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

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

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

Машинное обучение

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

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

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

Параллельное вычисление

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

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

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

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

Семантика программы

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

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

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

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

Квантовый компьютер является вычисление системы , которая делает прямое использование квантово-механические явления , такие как суперпозиция и запутанность , для выполнения операций по данным . Квантовые компьютеры отличаются от цифровых компьютеров на транзисторах . В то время как цифровые компьютеры требуют, чтобы данные были закодированы в двоичные цифры ( биты ), каждое из которых всегда находится в одном из двух определенных состояний (0 или 1), квантовые вычисления используют кубиты (квантовые биты), которые могут находиться в суперпозициях состояний. Теоретической моделью является квантовая машина Тьюринга , также известная как универсальный квантовый компьютер. Квантовые компьютеры имеют теоретическое сходство с недетерминированными и вероятностными компьютерами ; один из примеров - возможность находиться в более чем одном состоянии одновременно. Сфера квантовых вычислений была впервые представлена Юрием Маниным в 1980 году и Ричардом Фейнманом в 1982 году. Квантовый компьютер со спинами в качестве квантовых битов был также разработан для использования в качестве квантового пространства-времени в 1968 году.

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

Символьное вычисление

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

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

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

Очень крупномасштабная интеграция

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

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

Организации

Журналы и информационные бюллетени

Конференции

Смотрите также

Примечания

  1. ^ "СИГАКТ" . Проверено 19 января 2017 .
  2. ^ «Любой классический математический алгоритм, например, может быть описан конечным числом английских слов» (Rogers 1987: 2).
  3. ^ Хорошо определено относительно агента, который выполняет алгоритм: «Существует вычислительный агент, обычно человек, который может реагировать на инструкции и выполнять вычисления» (Rogers 1987: 2).
  4. ^ «алгоритм - это процедура для вычисления функции (относительно некоторых выбранных обозначений для целых чисел) ... это ограничение (числовыми функциями) не приводит к потере общности» (Rogers 1987: 1).
  5. ^ «Алгоритм имеет ноль или более входов, т. Е. Количества, которые задаются ему изначально перед запуском алгоритма» (Knuth 1973: 5).
  6. ^ «Процедура, которая имеет все характеристики алгоритма, за исключением того, что ей, возможно, не хватает конечности, может быть названа« вычислительным методом »» (Knuth 1973: 5).
  7. ^ «Алгоритм имеет один или несколько выходов, то есть количества, которые имеют определенное отношение к входам» (Knuth 1973: 5).
  8. ^ Вопрос о том, является ли процесс со случайными внутренними процессами (не включая входные) алгоритмом, является спорным. Роджерс полагает, что: «вычисление выполняется дискретным пошаговым способом, без использования непрерывных методов или аналоговых устройств ... выполняется детерминированно, без использования случайных методов или устройств, например, игральных костей» Rogers 1987: 2.
  9. ^ "Рабочее определение биоинформатики и вычислительной биологии NIH" (PDF) . Инициатива в области биомедицинской информатики и технологий. 17 июля 2000 г. Архивировано 5 сентября 2012 г. из оригинального (PDF) . Проверено 18 августа 2012 года .
  10. ^ "О CCMB" . Центр вычислительной молекулярной биологии . Проверено 18 августа 2012 года .
  11. ^ Ривест, Рональд Л. (1990). «Криптология». В J. Van Leeuwen (ред.). Справочник по теоретической информатике . 1 . Эльзевир.
  12. ^ Белларе, Михир; Рогавей, Филипп (21 сентября 2005 г.). "Вступление". Введение в современную криптографию . п. 10.
  13. ^ Menezes, AJ; ван Оршот, ПК; Ванстон, С.А. (1997). Справочник по прикладной криптографии . ISBN 978-0-8493-8523-0.
  14. ^ Пол Э. Блэк (редактор), запись о структуре данных в Словаре алгоритмов и структур данных . США Национальный институт стандартов и технологий . 15 декабря 2004 г. Онлайн-версия доступна 21 мая 2009 г.
  15. ↑ Входная структура данных в Encyclopædia Britannica (2009) Онлайн-запись, доступная 21 мая 2009 года.
  16. ^ a b Кулурис, Джордж; Жан Доллимор ; Тим Киндберг; Гордон Блэр (2011). Распределенные системы: концепции и дизайн (5-е изд.). Бостон: Эддисон-Уэсли. ISBN 978-0-132-14301-1.
  17. ^ Эндрюс (2000) . Долев (2000) . Гош (2007) , стр. 10.
  18. ^ RW Батлер (2001-08-06). "Что такое формальные методы?" . Проверено 16 ноября 2006 .
  19. ^ С. Майкл Холлоуэй. «Почему инженерам следует рассматривать формальные методы» (PDF) . 16-я конференция по системам цифровой авионики (27–30 октября 1997 г.). Архивировано из оригинального (PDF) 16 ноября 2006 года . Проверено 16 ноября 2006 . Цитировать журнал требует |journal=( помощь )
  20. ^ Монин, pp.3-4
  21. ^ Ф. Рике; Д. Варланд; Р. Рюйтер ван Стивенинк; В. Биалек (1997). Шипы: изучение нейронного кода . Пресса Массачусетского технологического института. ISBN 978-0262681087.
  22. ^ Huelsenbeck, JP; Ронквист, Ф .; Nielsen, R .; Боллбэк, JP (2001-12-14). «Байесовский вывод филогении и его влияние на эволюционную биологию». Наука . Американская ассоциация развития науки (AAAS). 294 (5550): 2310–2314. Bibcode : 2001Sci ... 294.2310H . DOI : 10.1126 / science.1065889 . ISSN  0036-8075 . PMID  11743192 . S2CID  2138288 .
  23. ^ Рандо Алликметс, Уайет В. Вассерман, Эми Хатчинсон, Филип Смоллвуд, Джереми Натанс, Питер К. Роган, Томас Д. Шнайдер , Майкл Дин (1998) Организация гена ABCR: анализ последовательностей промотора и сплайсинга, ген 215 : 1, 111-122
  24. ^ Бернхэм, КП и Андерсон Д.Р. (2002) Выбор модели и многомодельный вывод: практический теоретико-информационный подход, второе издание (Springer Science, Нью-Йорк) ISBN  978-0-387-95364-9 .
  25. ^ Джейнс, ET (1957-05-15). «Теория информации и статистическая механика». Физический обзор . Американское физическое общество (APS). 106 (4): 620–630. Bibcode : 1957PhRv..106..620J . DOI : 10.1103 / Physrev.106.620 . ISSN  0031-899X .
  26. ^ Чарльз Х. Беннетт, Мин Ли и Бин Ма (2003) Цепные буквы и эволюционная история , Scientific American 288 : 6, 76-81
  27. ↑ Дэвид Р. Андерсон (1 ноября 2003 г.). «Некоторые сведения о том, почему люди, занимающиеся эмпирическими науками, могут захотеть лучше понять теоретико-информационные методы» (PDF) . Архивировано из оригинального (PDF) 23 июля 2011 года . Проверено 23 июня 2010 .
  28. ^ Рон Kovahi; Фостер-провост (1998). «Словарь терминов» . Машинное обучение . 30 : 271–274. DOI : 10,1023 / A: 1007411609915 .
  29. ^ а б К. М. Бишоп (2006). Распознавание образов и машинное обучение . Springer. ISBN 978-0-387-31073-2.
  30. ^ Верник, Ян, Бранков, Yourganov и Strother, машинное обучение в медицинской визуализации, IEEE Signal Processing Magazine , т. 27, нет. 4, июль 2010 г., стр. 25–38.
  31. ^ Mannila, Хейкки (1996). Интеллектуальный анализ данных: машинное обучение, статистика и базы данных . Междунар. Конф. Управление научно-статистической базой данных. Компьютерное общество IEEE.
  32. ^ Фридман, Джером Х. (1998). «Интеллектуальный анализ данных и статистика: какая связь?». Вычислительная техника и статистика . 29 (1): 3–9.
  33. ^ Готтлиб, Аллан; Алмаси, Джордж С. (1989). Высокопараллельные вычисления . Редвуд-Сити, Калифорния: Бенджамин / Каммингс. ISBN 978-0-8053-0177-9.
  34. ^ SV Adve et al. (Ноябрь 2008 г.). «Исследование параллельных вычислений в Иллинойсе: повестка дня UPCRC». Архивировано 9 декабря 2008 г. в Wayback Machine (PDF). Parallel @ Illinois, Университет штата Иллинойс в Урбана-Шампейн. «Основные методы достижения этих преимуществ в производительности - повышенная тактовая частота и более умные, но все более сложные архитектуры - сейчас наталкиваются на так называемую« стену питания ». Компьютерная индустрия признала, что повышение производительности в будущем должно в значительной степени обеспечиваться за счет увеличения числа процессоров (или ядер). ) на кристалле, вместо того, чтобы ускорить работу одного ядра ".
  35. ^ Асанович и др. Старая [общепринятая мудрость]: питание бесплатное, но транзисторы дороги. Новое [общепринятое мнение] состоит в том, что мощность стоит дорого, а транзисторы «бесплатны».
  36. ^ Асанович, Крсте и др. (18 декабря 2006 г.). «Пейзаж исследований в области параллельных вычислений: взгляд из Беркли» (PDF). Калифорнийский университет в Беркли. Технический отчет № UCB / EECS-2006-183. «Старая [общепринятая мудрость]: повышение тактовой частоты - это основной метод повышения производительности процессора. Новая [общепринятая мудрость]: увеличение параллелизма - это основной метод повышения производительности процессора ... Даже представители Intel, компании, обычно связанной с ' «чем выше тактовая частота, тем лучше», предупредил, что традиционные подходы к максимальному увеличению производительности за счет максимизации тактовой частоты были доведены до предела ».
  37. ^ Хеннесси, Джон Л .; Паттерсон, Дэвид А .; Ларус, Джеймс Р. (1999). Компьютерная организация и дизайн: программно-аппаратный интерфейс (2-е изд., 3-е изд.). Сан-Франциско: Кауфманн. ISBN 978-1-55860-428-5.
  38. ^ « Квантовые вычисления с молекулами » статья в журнале Scientific American от Neil Гершенфельд и Isaac L. Chuang
  39. ^ Манин, Ю. И. (1980). Vychislimoe я nevychislimoe [ Computable и невычислимые ] (на русском языке ). Сов.радио. С. 13–15. Архивировано из оригинального 10 мая 2013 года . Проверено 4 марта 2013 года .
  40. Перейти ↑ Feynman, RP (1982). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики . 21 (6): 467–488. Bibcode : 1982IJTP ... 21..467F . CiteSeerX  10.1.1.45.9310 . DOI : 10.1007 / BF02650179 . S2CID  124545445 .
  41. ^ Дойч, Дэвид (1992-01-06). «Квантовые вычисления». Мир физики . 5 (6): 57–61. DOI : 10.1088 / 2058-7058 / 5/6/38 .
  42. ^ Финкельштейн, Дэвид (1968). "Пространственно-временная структура при взаимодействии высоких энергий". В Гудехусе, Т .; Кайзер, Г. (ред.). Фундаментальные взаимодействия при высоких энергиях . Нью-Йорк: Гордон и разрыв.
  43. ^ «Новый контроль над кубитом - хороший предзнаменование для будущего квантовых вычислений» . Проверено 26 октября 2014 года .
  44. ^ Дорожная карта квантовой информатики и технологий, чтобы понять, куда движутся исследования.
  45. ^ Б с d е 2007 австралийской Рейтинг конференций ИКТ Архивной 2009-10-02 в Wayback Machine : уровень А +.
  46. ^ MFCS 2017
  47. ^ CSR 2018
  48. ^ Б с д е е г ч я J 2007 австралийская Рейтинг конференций ИКТ Архивные 2009-10-02 в Wayback Machine : уровень A.
  49. ^ FCT 2011 (получено 03.06.2013)

дальнейшее чтение

внешние ссылки