Это список важных публикаций в теоретической информатика, организованная по отраслям.
Некоторые причины по конкретной публикации может считаться:
Обзор этого раннего текста, сделанный Карлом Смитом из Университета Пердью (в Обществе обзоров промышленной и прикладной математики), сообщает, что это текст с « смесью интуиции и строгости... в изложении доказательств », который представляет« фундаментальные результаты классической теории рекурсии [RT]... в стиле... доступном для студентов с минимальным математическим образованием ». Хотя он заявляет, что он «станет отличным вводным текстом для вводного курса в [RT] для студентов-математиков», он предлагает, чтобы «преподаватель был подготовлен к серьезному расширению материала…», когда он используется со студентами, изучающими информатику (учитывая недостаток) материалов по приложениям RT в этой области).
Описание: В статье был представлен древовидный автомат, расширение автоматов. Древовидный автомат множественного применения для доказательства правильных программ.
Описание: Математическая обработка автоматов, доказательство основных свойств и определение недетерминированного конечного автомата.
Описание: популярный учебник.
Описание: В этой статье представлена так называемая иерархия Хомского, сдерживание иерархия классов формальных грамматик, порождающих формальных языков.
Описание : Это статья устанавливает пределы информатики. Он определил машину Тьюринга, модель для всех вычислений. С другой стороны, он доказал неразрешимость проблемы остановки и Entscheidungsproblem и тем самым обнаружил пределы вычислений.
Первый учебник по теории рекурсивных функций. Книга выдержала множество изданий и принесла Петеру премию Кошута от венгерского правительства. Рецензии Рафаэля М. Робинсона и Стивена Клини дали высокую оценку за эффективное элементарное введение для студентов.
Описание: в этой статье были представлены конечные автоматы, регулярные выражения и регулярные языки, а также их подключение.
Помимо уважаемой прессы, выдвигающей эти недавние тексты, они очень положительно рецензируются в ACM. Даниэля Апона из Университета Арканзаса, определяет их как «учебники для курса теории сложности, предназначенные для начинающих аспирантов… или… продвинутых студентов бакалавриата… [с многочисленными] уникальными сильными сторонами и очень немногими слабыми сторонами», и заявляет, что оба имеют:
«отличными текстами, которые полностью охватывают как широту, так и глубину теории вычислительной сложности... [авторами]... [кто] является ги гантом в теории вычислений [где каждый будет].. бывший Необязательный справочный текст для экспертов в этой области... [и что]... теоретики, исследователи и преподаватели любой научной школы сочтут любую книгу полезной ».
Рецензент отмечает, что есть «определенная попытка в [Arora and Барака], чтобы включить в него очень современные материалы, в то время как Голдрайх больше фокусируется на разработке контекстной и исторической основы для каждой представленной концепции», и что он «аплодирует» всем… авторам за их выдающийся вклад ».
Описание: аксиомы Блюма.
Описание: Эта статья показала, что PH содержит в IP.
Описание: В этой статье представлена концепция NP-полноты и доказано, что проблема логической выполнимости (SAT) является NP-Complete. Отметим, что аналогичные идеи были независимо развиты несколько позже Леонидом Левиным в «Левин, Универсальные проблемы поиска. Проблемы передачи информации 9 (3): 265–266, 1973 ».
Описание: Основное значение этой книги связано с ее обширным списком из более чем 300 NP-Complete задач.. Этот список стал общей ссылкой и определением. Хотя книга вышла всего через несколько лет после концепции, такой обширный список был найден.
Описание: Этот технический отчет был первой публикацией, которая позже была переименовано в вычислительная сложность
Описание: построил «куб Кли-Минти» в измерении D, 2 угла которого посещает Данциг симплекс-алгоритм для линейной оптимизации.
Описание: Эта статья показала, что существование односторонних функций приводит к.
Описание: IP - это класс сложности, характеристика которого (на основе интерактивных систем доказательства ) сильно отличается от обычных классов, ограниченных во времени / простейшей статье. Как этот PSPACE с этой статьи. одержится в IP и, следовательно, IP = PSPACE, так что каждая проблема в одном классе сложности разрешима в другом.
Описание: Эта статья показала, что 21 различная проблема представляет собой NP-Complete и демонстрируют концепции.
Описание: В этой статье представлена <концепция8>нулевого разглашения.
Описание: Гёдель обсуждает идею универсального средства доказательства теорем.
Описание: В этой статье вычислительная сложность была названа и начата.
Описание: алгоритм с полиномиальным временем для определения совпадения в недвудольном графе и еще один шаг к идее вычислительная сложность. Для получения дополнительной информации см. [2].
Описание: в этой статье создаются теоретические основы для функций лазейки и некоторых из их приложений, например, в криптографии. Обратите внимание, что концепция секретных функций представлена в «Новых направлениях криптографии» шестью годами ранее (см. Раздел V «Взаимосвязи проблем и лазейки»).
Описание: Введение в теорию сложности вычислений, книга объясняет авторскую характеристику P-SPACE и другие результаты.
Описание: Эти три статьи установили тот удивительный факт, что некоторые проблемы в NP остаются сложными даже тогда, когда требуется только приближенное решение. См. теорема PCP.
Описание: Первое определение класса сложности P. Одна из основополагающих статей теории сложности.
Описание: алгоритм DPLL. Базовый алгоритм для SAT и других задач NP-Complete.
Описание: Первое описание разрешение и унификации, используемые в автоматическом доказательстве теорем ; используется в Прологе и логическом программировании.
Описание: использование алгоритма минимального связующего дерева в качестве алгоритма аппроксимации для НП- Выполнена задача коммивояжера. Аппроксимационные алгоритмы стали обычным методом решения NP-Complete задач.
Описание: Долгое время не существовало доказуемо полиномиального алгоритма времени для задачи линейного программирования. Хачиян был первым, кто предоставил алгоритм, который был полиномиальным (и не только был достаточно быстрым в большинстве случаев, как предыдущие алгоритмы). Позже Нарендра Кармаркар представил более быстрый алгоритм на: Нарендра Кармаркар, «Новый алгоритм с полиномиальным временем для линейного программирования», Combinatorica, том 4, нет. 4, стр. 373–395, 1984.
Описание: В статье представлен критерий простоты Миллера-Рабина и изложена программа рандомизированные алгоритмы.
Описание: В этой статье описывается имитация отжига, которая сейчас является очень распространенной эвристикой для задач NP-Complete.
Описание: Эта монография состоит из четырех томов, охватывающих популярные алгоритмы. Алгоритмы написаны как на английском языке, так и на языке ассемблера MIX (или на языке ассемблера MMIX в более поздних выпусках). Это делает алгоритмы понятными и точными. Однако использование низкоуровневого языка программирования расстраивает некоторых программистов, более знакомых современными структурным программированием языками.
Описание: ранняя и влиятельная книга по алгоритам и структурам данных, реализованная на Паскале.
Описание: Один из стандартных текстов по алгоритам на период примерно 1975–1985 гг.
Описание: объясняет, почему алгоритмы и структуры данных. Объясняет творческий процесс, ход рассуждений, факторы дизайна, лежащие в основе инновационных решений.
Описание: очень популярный текст по алгоритмам в конце 1980-х. Он был более доступным и читабельным (но более элементарным), чем Ахо, Хопкрофт и Ульман. Есть более свежие выпуски.
Описание: Этот учебник стал настолько популярным, что стал практически стандартом де-факто. для обучения алгоритмам. Первое издание (с первыми тремя авторами) вышло в 1990 году, второе - в 2001 году, третье - в 2009 году.
Описание: Предложен вычислительный и комбинаторный подход к вероятности.
Описание: Это было начало алгоритмической теории информации и колмогоровская сложность. Обратите внимание, что хотя сложность Колмогорова названа в честь Андрея Колмогорова, он сказал, что семена этой идеи принадлежат Рэю Соломонову. Андрей Колмогоров внес большой вклад в эту область, но в более поздних статьях.
Описание: Введение в теорию алгоритмической информации одним из важных людей в этой области.
Описание: Эта статья создала область теории информации.
Описание: В этой статье Хэмминг представил идею кода исправления ошибок. Он создал код Хэмминга и расстояние Хэмминга и разработал методы для доказательства оптимальности кода.
Описание: кодирование Хаффмана.
Описание: алгоритм сжатия LZ77.
Описание: популярное введение в теорию информации.
Описание: Знаменательная статья Роберта Флойда «Присваивая значения программам» вводит метод индуктивных утверждений и приведенных, как программа, аннотированная утверждениями первого порядка, может быть проведена как удовлетворяющая предварительным и спецификация постусловия - в статье также вводятся понятия инварианта цикла и условия проверки.
Описание: В статье Тони Хоара «Аксиоматическая основа компьютерного программирования» описывается набор правил вывода (то есть формального доказательства) для фрагментов Алгола. -подобный язык программирования, описанный в терминах (так называемых) троек Хоара.
Описание: В статье Эдсгера Дейкстры «Защищенные команды, неопределенность и формальная производная программа» (расширенная его учебная программа для аспирантов 1976 года «Дисциплина программирования») предлагается вместо формальной проверка после того, как она была написана (т.е. постфактум), программы и их формальные доказательства должны разрабатываться рука об руку (с использованием преобразователей предикатов для уточнения самых слабых предварительных условий), метод, известный как программный (или формальный) уточнение (или вывод), или иногда «правильность построения».
Описание: статья, в которой представлены доказательства инвариантности параллельных программ.
Описание: В статье, а также в статье тех же авторов «Проверка свойств параллельных программ: аксиоматический подход. Commun. ACM 19 (5): 279–285 (1976) », представлен аксиоматический подход к верификации параллельных программ.
Описание: Классический учебник Эдсгера Дейкстры для аспирантов «Дисциплина программирования» расширяет его предыдущую статью «Защищенные команды, недетерминированность и формальная производственная программа» и твердо принцип формального обеспечения программ (и их доказательств) из их спецификации.
Описание: Денотационная семантика Джо Стоя - первое (для аспирантуры) целое изложение математического (или функционального) подход к формальной семантике языков программирования (в отличие от операционного и алгебраического подходов).
Описание: Использование временной логики было предложено в качестве метода формальной проверки.
Описание: Проверка моделей была введена как процедура для проверки корректности параллельных программ.
Описание: статья Тони Хора (оригинал) о вводе последовательных последовательных процессов (CSP), вводящих идею параллельных процессов (то есть программ), которые не разделяют переменные, а вместо этого используют исключительно путем обмен синхронными Сообщения.
Описание: Статья Робина Милнера «Исчисление коммуникационных систем» (CCS) представленных алгебру процессов, позволяющих формально рассуждать о системах параллельных процессов., что было невозможно для более ранних моделей параллелизма (семафоры, критические секции, исходный CSP).
Описание: Учебник Клиффа Джонса «Разработка программного обеспечения: строгий подход» - это первое полнометражное изложение Венского метода разработки (VDM).), которая развивалась (в основном) в исследовательской лаборатории IBM в Вене за предыдущее десятилетие и сочетает в себе идею усовершенствования программы в соответствии с Дейкстрой с идеей уточнения (или повторения) данных, посредством чего алгебраически определенные абстрактные типы данных формально трансформируются в все более «конкретные» представления.
Описание: Учебник Дэвида Гриса «Наука программирования» описывает самый слабый метод предусловия Дейкстры для формального вывода программ, за исключением гораздо более доступной формы чем более ранняя «Дисциплина программирования» Дейкстры.
Он показывает, как создавать программы, которые работают правильно (без ошибок, кроме ошибок ввода). Это достигается путем демонстрации того, как использовать выражения предикатов предусловия и постусловия, а также методы проверки программ для управления способом создания программ.
Все примеры в книге мелкие и явно академические (в отличие от реальных). Они подчеркивают базовые алгоритмы, такие как сортировка и слияние, а также манипуляции со строками. Подпрограммы (функции) включены, но не рассматриваются среды объектно-ориентированного и функционального программирования.
Описание: Учебник Тони Хора по взаимодействующим последовательным процессам (CSP) (в настоящее время третий по популярности справочник по информатике за все время) представляет обновленную модель CSP, в которой взаимодействующие процессы даже не имеют программных переменных и которая, подобно CCS, позволяет формально рассуждать о системах процессов.
Описание: линейная логика Жирара стала прорывом в разработке систем набора текста для последовательных и параллельных вычислений, особенно для ресурсов сознательные системы набора текста.
Описание: Эта статья вводит Pi-Calculus, обобщение CCS, обеспечивающее мобильность процессов. Исчисление чрезвычайно простое и стало доминирующей парадигмой в теоретическом изучении языков программирования, систем набора текста и логики программ.
Описание: Классический учебник Майка Спайви Нотация Z: Справочное руководство обобщает формальный язык спецификаций Нотация Z, который, хотя и был создан Жаном-Раймондом Абриалом, эволюционировал (в основном) в Оксфордском университете за предыдущее десятилетие.
Описание: Учебник Робина Милнера «Коммуникация и параллелизм» представляет собой более доступное, хотя все еще технически продвинутое, изложение его более ранних работ по CCS.
Описание: современная версия Предикативного программирования. Основание для C.A.R. UTP Хоара. Самые простые и всесторонние формальные методы.