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

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

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

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

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

История

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

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

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

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

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

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

Темы

Алгоритмы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основным толчком к развитию вычислительной геометрии как дисциплины стал прогресс в компьютерная графика и автоматизированное проектирование и производство (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

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

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

Параллельные вычисления это форма вычисление в котором одновременно выполняется множество расчетов,[33] действуя по принципу, что большие проблемы часто можно разделить на более мелкие, которые затем решаются "в параллели". Есть несколько различных форм параллельных вычислений: битовый уровень, уровень обучения, данные, и параллелизм задач. Параллелизм применяется уже много лет, в основном в высокопроизводительные вычисления, но в последнее время интерес к нему вырос из-за физических ограничений, мешающих частотное масштабирование.[34] Поскольку в последние годы потребление энергии (и, как следствие, тепловыделение) компьютерами стало проблемой,[35] параллельные вычисления стали доминирующей парадигмой в компьютерная архитектура, в основном в виде многоядерные процессоры.[36]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Организации

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

Конференции

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

Примечания

  1. ^ «СИГАКТ». Получено 2017-01-19.
  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 г. Архивировано с оригинал (PDF) 5 сентября 2012 г.. Получено 18 августа 2012.
  10. ^ "О CCMB". Центр вычислительной молекулярной биологии. Получено 18 августа 2012.
  11. ^ Ривест, Рональд Л. (1990). «Криптология». В J. Van Leeuwen (ред.). Справочник по теоретической информатике. 1. Эльзевир.
  12. ^ Белларе, Михир; Рогавей, Филипп (21 сентября 2005 г.). "Вступление". Введение в современную криптографию. п. 10.
  13. ^ Menezes, A.J .; van Oorschot, P.C .; Ванстон, С. А. (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. ^ Эндрюс (2000). Долев (2000). Гош (2007), п. 10.
  18. ^ Р. В. Батлер (6 августа 2001 г.). "Что такое формальные методы?". Получено 2006-11-16.
  19. ^ К. Майкл Холлоуэй. «Почему инженерам следует рассматривать формальные методы» (PDF). 16-я конференция по системам цифровой авионики (27-30 октября 1997 г.). Архивировано из оригинал (PDF) 16 ноября 2006 г.. Получено 2006-11-16. Цитировать журнал требует | журнал = (помощь)
  20. ^ Монин, стр.3-4
  21. ^ Ф. Рике; Д. Уорленд; Р. Рюйтер ван Стивенинк; В. Биалек (1997). Шипы: изучение нейронного кода. Пресса Массачусетского технологического института. ISBN  978-0262681087.
  22. ^ Huelsenbeck, J. P .; Ронквист, Ф .; Nielsen, R .; Боллбэк, Дж. П. (2001-12-14). «Байесовский вывод филогении и его влияние на эволюционную биологию». Наука. Американская ассоциация развития науки (AAAS). 294 (5550): 2310–2314. Bibcode:2001Наука ... 294.2310H. Дои: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. ^ Джейнс, Э. Т. (1957-05-15). «Теория информации и статистическая механика». Физический обзор. Американское физическое общество (APS). 106 (4): 620–630. Bibcode:1957PhRv..106..620J. Дои:10.1103 / Physrev.106.620. ISSN  0031-899X.
  26. ^ Чарльз Х. Беннет, Мин Ли и Бин Ма (2003) Письма по цепочке и эволюционные истории, Scientific American 288:6, 76-81
  27. ^ Дэвид Р. Андерсон (1 ноября 2003 г.). «Некоторые сведения о том, почему люди, занимающиеся эмпирическими науками, могут захотеть лучше понять теоретико-информационные методы» (PDF). Архивировано из оригинал (PDF) 23 июля 2011 г.. Получено 2010-06-23.
  28. ^ Рон Ковахи; Фостер-провост (1998). "Словарь терминов". Машинное обучение. 30: 271–274. Дои:10.1023 / А: 1007411609915.
  29. ^ а б К. М. Бишоп (2006). Распознавание образов и машинное обучение. Springer. ISBN  978-0-387-31073-2.
  30. ^ Верник, Ян, Бранков, Юрганов и Стротер, Машинное обучение в медицинской визуализации, Журнал IEEE Signal Processing Magazine, т. 27, нет. 4, июль 2010 г., стр. 25–38.
  31. ^ Маннила, Хейкки (1996). Интеллектуальный анализ данных: машинное обучение, статистика и базы данных. Междунар. Конф. Управление научно-статистической базой данных. Компьютерное общество IEEE.
  32. ^ Фридман, Джером Х. (1998). «Интеллектуальный анализ данных и статистика: какая связь?». Вычислительная техника и статистика. 29 (1): 3–9.
  33. ^ Готтлиб, Аллан; Алмаси, Джордж С. (1989). Высокопараллельные вычисления. Редвуд-Сити, Калифорния: Бенджамин / Каммингс. ISBN  978-0-8053-0177-9.
  34. ^ С.В. Adve et al. (Ноябрь 2008 г.). «Исследования в области параллельных вычислений в Иллинойсе: повестка дня UPCRC» В архиве 2008-12-09 на Wayback Machine (PDF). Parallel @ Illinois, Университет Иллинойса в Урбане-Шампейне. «Основные методы достижения этих преимуществ в производительности - повышенная тактовая частота и более интеллектуальные, но все более сложные архитектуры - теперь наталкиваются на так называемую« стену питания ». Компьютерная индустрия признала, что повышение производительности в будущем должно в значительной степени обеспечиваться за счет увеличения количества процессоров (или ядер. ) на кристалле, вместо того, чтобы ускорить работу одного ядра ".
  35. ^ Asanovic et al. Старая [общепринятая мудрость]: питание бесплатное, но транзисторы дороги. Новое [общепринятое мнение] состоит в том, что мощность стоит дорого, а транзисторы «бесплатны».
  36. ^ Асанович, Крсте и др. (18 декабря 2006 г.). "Пейзаж исследований в области параллельных вычислений: взгляд из Беркли" (PDF). Калифорнийский университет в Беркли. Технический отчет № UCB / EECS-2006-183. «Старая [общепринятая мудрость]: повышение тактовой частоты - это основной метод повышения производительности процессора. Новая [общепринятая мудрость]: увеличение параллелизма - это основной метод повышения производительности процессора ... Даже представители Intel, компании, обычно связанной с ' «чем выше тактовая частота, тем лучше», предупредил, что традиционные подходы к максимальному увеличению производительности за счет увеличения тактовой частоты были доведены до предела ».
  37. ^ Хеннесси, Джон Л .; Паттерсон, Дэвид А .; Ларус, Джеймс Р. (1999). Компьютерная организация и дизайн: аппаратно-программный интерфейс (2-е изд., 3-е изд.). Сан-Франциско: Кауфманн. ISBN  978-1-55860-428-5.
  38. ^ "Квантовые вычисления с молекулами "статья в Scientific American к Нил Гершенфельд и Исаак Л. Чуанг
  39. ^ Манин, Ю. И. (1980). Вычислимое и невычислимое [Вычислимые и невычислимые] (на русском). Сов.радио. С. 13–15. Архивировано из оригинал 10 мая 2013 г.. Получено 4 марта 2013.
  40. ^ Фейнман, Р. П. (1982). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики. 21 (6): 467–488. Bibcode:1982IJTP ... 21..467F. CiteSeerX  10.1.1.45.9310. Дои:10.1007 / BF02650179. S2CID  124545445.
  41. ^ Дойч, Дэвид (1992-01-06). «Квантовые вычисления». Мир физики. 5 (6): 57–61. Дои:10.1088/2058-7058/5/6/38.
  42. ^ Финкельштейн, Дэвид (1968). "Пространственно-временная структура при взаимодействии высоких энергий". В Gudehus, T .; Кайзер, Г. (ред.). Фундаментальные взаимодействия при высоких энергиях. Нью-Йорк: Гордон и разрыв.
  43. ^ «Новый контроль над кубитами - хорошее предзнаменование для будущего квантовых вычислений». Получено 26 октября 2014.
  44. ^ Дорожная карта квантовой информатики и технологий чтобы понять, куда движутся исследования.
  45. ^ а б c d е В Рейтинг австралийских конференций по ИКТ за 2007 год В архиве 2009-10-02 на Wayback Machine: уровень A +.
  46. ^ MFCS 2017
  47. ^ КСО 2018
  48. ^ а б c d е ж грамм час я j В 2007 Австралийский рейтинг конференций по ИКТ В архиве 2009-10-02 на Wayback Machine: уровень А.
  49. ^ FCT 2011 (Дата обращения 03.06.2013)

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

внешняя ссылка