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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Компьютерная программа , которая работает в распределенной системе называется распространяемой программой , и распределенное программирование представляет собой процесс написания таких программ. [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]

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

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

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

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

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

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

  • Европейская ассоциация теоретической информатики
  • SIGACT
  • Институт теории вычислений Саймонса

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

  • « Дискретная математика и теоретическая информатика »
  • Информация и вычисления
  • Теория вычислений (журнал в открытом доступе )
  • Формальные аспекты вычислений
  • Журнал ACM
  • Журнал SIAM по вычислениям (SICOMP)
  • Новости SIGACT
  • Теоретическая информатика
  • Теория вычислительных систем
  • Международный журнал основ информатики
  • Чикагский журнал теоретической информатики (журнал с открытым доступом )
  • Основы и тенденции теоретической информатики
  • Журнал автоматов, языков и комбинаторики
  • Acta Informatica
  • Fundamenta Informaticae
  • Транзакции ACM по теории вычислений
  • Вычислительная сложность
  • Журнал сложности
  • ACM-транзакции на алгоритмах
  • Письма об обработке информации
  • Open Computer Science ( журнал с открытым доступом )

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

  • Ежегодный симпозиум ACM по теории вычислений (STOC) [45]
  • Ежегодный симпозиум IEEE по основам компьютерных наук (FOCS) [45]
  • Инновации в теоретической информатике (ITCS)
  • Математические основы информатики (MFCS) [46]
  • Международный симпозиум по информатике в России (CSR) [47]
  • Симпозиум ACM – SIAM по дискретным алгоритмам (SODA) [45]
  • Симпозиум IEEE по логике в компьютерных науках (LICS) [45]
  • Конференция по вычислительной сложности (CCC) [48]
  • Международный коллоквиум по автоматам, языкам и программированию (ICALP) [48]
  • Ежегодный симпозиум по вычислительной геометрии (SoCG) [48]
  • Симпозиум ACM по принципам распределенных вычислений (PODC) [45]
  • Симпозиум ACM по параллелизму в алгоритмах и архитектурах (SPAA) [48]
  • Ежегодная конференция по теории обучения (COLT) [48]
  • Симпозиум по теоретическим аспектам информатики (STACS) [48]
  • Европейский симпозиум по алгоритмам (ESA) [48]
  • Практикум по аппроксимационным алгоритмам для задач комбинаторной оптимизации (APPROX) [48]
  • Практикум по рандомизации и вычислениям (RANDOM) [48]
  • Международный симпозиум по алгоритмам и вычислениям (ISAAC) [48]
  • Международный симпозиум по основам теории вычислений (FCT) [49]
  • Международный семинар по теоретико-графическим концепциям в компьютерных науках (WG)

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

  • Формальная наука
  • Нерешенные проблемы информатики
  • Список важных публикаций по теоретической информатике

Заметки [ править ]

  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 . Cite journal requires |journal= (help)
  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. ^ Верник, Ян, Бранков, Юрганов и Стротер, Машинное обучение в медицинской визуализации, Журнал обработки сигналов IEEE , т. 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)

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

  • Мартин Дэвис , Рон Сигал, Элейн Дж. Вейкер, Вычислимость, сложность и языки: основы теоретической информатики , 2-е изд., Academic Press, 1994, ISBN 0-12-206382-1 . Охватывает теорию вычислений , а также семантику программ и теорию количественной оценки . Направлено на аспирантов. 

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

  • Каталог дополнительных теоретических ссылок SIGACT
  • Theory Matters Wiki Теоретическая информатика (TCS) Advocacy Wiki
  • Список научных конференций в области теоретической информатики на confsearch
  • Теоретическая информатика - StackExchange , сайт вопросов и ответов для исследователей теоретической информатики
  • Компьютерные науки Анимированные
  • http://theory.csail.mit.edu/ @ Массачусетский технологический институт