Список важных публикаций по теоретической информатике - List of important publications in theoretical computer science

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

Некоторые причины, по которым конкретная публикация может считаться важной:

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

Вычислимость

Вычислимость Катленда : введение в теорию рекурсивных функций (Кембридж)

  • Катленд, Найджел Дж. (1980). Вычислимость: введение в теорию рекурсивных функций . Издательство Кембриджского университета . ISBN 978-0-521-29465-2.

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

Разрешимость теорий и автоматов второго порядка на бесконечных деревьях

Описание: В статье представлен древовидный автомат , расширение автоматов . Древовидный автомат нашел множество применений для доказательства корректности программ .

Конечные автоматы и проблемы их решения

Описание: математическая обработка автоматов , доказательство основных свойств и определение недетерминированного конечного автомата .

Введение в теорию автоматов, языки и вычисления

Описание: Популярный учебник.

О некоторых формальных свойствах грамматик

Описание: Эта статья представила , что теперь известно как иерархии Хомского , в защитной иерархии классов формальных грамматик , порождающих формальные языки .

О вычислимых числах в приложении к проблеме Entscheidungs.

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

Рекурсивные функции

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

Представление событий в нервных сетях и конечных автоматах

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

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

Arora & Барака вычислительной сложности и Голдрейха вычислительной сложности (как Кембридж)

  • Санджив Арора и Боаз Барак, «Вычислительная сложность: современный подход», Cambridge University Press, 2009 г., 579 страниц, твердый переплет
  • Одед Голдрайх, "Вычислительная сложность: концептуальная перспектива", Cambridge University Press, 2008 г., 606 страниц, твердый переплет

Помимо уважаемой прессы, продвигающей эти последние тексты, они очень положительно рецензируются в ACM SIGACT News Даниэлем Апоном из Университета Арканзаса, который определяет их как «учебники для курса теории сложности, предназначенные для начинающих выпускников ... или ... продвинутые студенты бакалавриата… [с] многочисленными уникальными сильными сторонами и очень немногими слабостями », и заявляет, что оба они:

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

Рецензент отмечает, что в [Ароре и Бараке] делается определенная попытка включить самые свежие материалы, в то время как Голдрайх больше сосредотачивается на разработке контекстной и исторической основы для каждой представленной концепции », и что он« аплодирует [s ] всем… авторам за их выдающийся вклад ».

Машинно-независимая теория сложности рекурсивных функций

Описание: Аксиомы Блюма .

Алгебраические методы для интерактивных систем доказательства

Описание: В этой статье показано, что PH содержится в IP .

Сложность процедур доказательства теорем

Описание: в этой статье вводится понятие NP-полноты и доказывается, что проблема логической выполнимости (SAT) является NP-полной . Отметим, что аналогичные идеи были независимо развиты несколько позже Леонидом Левиным в «Левин, Универсальные проблемы поиска. Проблемы передачи информации, 9 (3): 265–266, 1973».

Компьютеры и неразрешимость: руководство по теории NP-полноты

Описание: Основное значение этой книги связано с ее обширным списком из более чем 300 NP-Complete задач. Этот список стал общей ссылкой и определением. Хотя книга была опубликована всего через несколько лет после определения концепции, такой обширный список был найден.

Степень сложности вычисления функции и частичное упорядочение рекурсивных множеств

Описание: Этот технический отчет был первой публикацией, в которой говорилось о том, что позже было переименовано в вычислительную сложность.

Насколько хорош симплексный метод?

Описание: Построенный в «Кли-Минтите куб» в размерности  D , у которого 2 D углы каждый посещают Данциг «s симплексного алгоритма для линейной оптимизации .

Как построить случайные функции

Описание: эта статья показала, что существование односторонних функций приводит к вычислительной случайности .

IP = PSPACE

Описание: IP - это класс сложности, характеристика которого (на основе интерактивных систем доказательства ) сильно отличается от обычных вычислительных классов, ограниченных во времени / пространстве. В этой статье Шамир расширил технику предыдущей статьи Лунда и др., Чтобы показать, что PSPACE содержится в IP и, следовательно, IP = PSPACE, так что каждая проблема в одном классе сложности разрешима в другом.

Сводимость комбинаторных задач

  • Р.М. Карп
  • В RE Миллер и Дж. Тэтчер, редакторы, Сложность компьютерных вычислений , Plenum Press, Нью-Йорк, Нью-Йорк, 1972, стр. 85–103.

Описание: эта статья показала, что 21 задача являются NP-Complete, и показала важность этой концепции.

Сложность знаний интерактивных систем доказательства

Описание: В этой статье представлена ​​концепция нулевого знания .

Письмо Гёделя фон Нейману

Описание: Гёдель обсуждает идею эффективного универсального средства доказательства теорем.

О вычислительной сложности алгоритмов

Описание: В этой статье вычислительная сложность получила свое название и начало.

Дорожки, деревья и цветы

Описание: существует алгоритм с полиномиальным временем для поиска максимального совпадения в недвудольном графе и еще один шаг к идее вычислительной сложности . Для получения дополнительной информации см. [2] .

Теория и приложения секретных функций

Описание: в этой статье создается теоретическая основа для функций лазейки и описаны некоторые из их приложений, например, в криптографии . Обратите внимание, что концепция функций лазейки была представлена ​​в «Новых направлениях криптографии» шестью годами ранее (см. Раздел V «Взаимосвязи проблем и лазейки»).

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

Описание: Введение в теорию сложности вычислений , книга объясняет авторскую характеристику P-SPACE и другие результаты.

Интерактивные доказательства и твердость приближающих клик

Вероятностная проверка доказательств: новая характеристика NP

Проверка доказательства и трудность аппроксимационных задач.

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

Внутренняя вычислительная сложность функций

Описание: Первое определение класса сложности P. Одна из основополагающих работ теории сложности.

Алгоритмы

«Машинная программа для доказательства теорем»

Описание: Алгоритм DPLL . Базовый алгоритм для SAT и других задач NP-Complete .

«Машинно-ориентированная логика, основанная на принципе разрешения»

Описание: Первое описание разрешения и унификации, используемых в автоматическом доказательстве теорем ; используется в Прологе и логическом программировании .

«Задача коммивояжера и минимальные остовные деревья»

Описание: использование алгоритма минимального остовного дерева в качестве алгоритма аппроксимации для NP-полной задачи коммивояжера . Алгоритмы аппроксимации стали обычным методом решения NP-Complete задач.

«Полиномиальный алгоритм в линейном программировании»

Описание: Долгое время не существовало доказуемо полиномиального алгоритма времени для задачи линейного программирования . Хачиян был первым, кто предоставил алгоритм, который был полиномиальным (и не только был достаточно быстрым в большинстве случаев, как предыдущие алгоритмы). Позже Нарендра Кармаркар представил более быстрый алгоритм по адресу: Нарендра Кармаркар, «Новый алгоритм с полиномиальным временем для линейного программирования», Combinatorica , vol 4, no. 4, стр. 373–395, 1984.

«Вероятностный алгоритм проверки простоты»

Описание: В статье представлен тест простоты Миллера-Рабина и изложена программа рандомизированных алгоритмов .

«Оптимизация моделированием отжига»

Описание: в этой статье описывается имитация отжига , которая сейчас является очень распространенной эвристикой для задач NP-Complete .

Искусство программирования

Описание: Эта монография состоит из четырех томов, в которых рассматриваются популярные алгоритмы. Алгоритмы написаны как на английском, так и на ассемблере MIX (или ассемблере MMIX в более поздних выпусках). Это делает алгоритмы понятными и точными. Однако использование низкоуровневого языка программирования расстраивает некоторых программистов, более знакомых с современными структурированными языками программирования .

Алгоритмы + Структуры данных = Программы

Описание: ранняя и влиятельная книга по алгоритмам и структурам данных, реализованная на языке Паскаль.

Разработка и анализ компьютерных алгоритмов

Описание: Один из стандартных текстов по алгоритмам примерно за 1975–1985 гг.

Как решить это на компьютере

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

Алгоритмы

Описание: очень популярный текст по алгоритмам в конце 1980-х годов. Он был более доступным и читабельным (но более элементарным), чем Ахо, Хопкрофт и Ульман. Есть более свежие выпуски.

Введение в алгоритмы

Описание: этот учебник стал настолько популярным, что фактически стал стандартом для обучения базовым алгоритмам. Первое издание (с первыми тремя авторами) было опубликовано в 1990 году, второе издание - в 2001 году, а третье - в 2009 году.

Алгоритмическая теория информации

«О таблицах случайных чисел»

Описание: Предложен вычислительный и комбинаторный подход к вероятности.

«Формальная теория индуктивного вывода»

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

«Алгоритмическая теория информации»

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

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

«Математическая теория коммуникации»

Описание: Эта статья создала область теории информации .

«Коды обнаружения и исправления ошибок»

Описание: В этой статье Хэмминг представил идею кода с исправлением ошибок . Он создал код Хэмминга и расстояние Хэмминга и разработанные методы для кода оптимальности доказательств.

«Метод построения кодов минимальной избыточности»

Описание: Кодировка Хаффмана .

«Универсальный алгоритм последовательного сжатия данных»

Описание: Алгоритм сжатия LZ77 .

Элементы теории информации

Описание: популярное введение в теорию информации.

Формальная проверка

Присвоение смысла программам

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

Аксиоматическая основа компьютерного программирования

Описание: статья Тони Хоара «Аксиоматическая основа компьютерного программирования» описывает набор правил вывода (т.е. формального доказательства) для фрагментов языка программирования, подобного Алголу, описанных в терминах (которые сейчас называются) троек Хора.

Защищенные команды, неопределенность и формальная производная программ

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

Доказательство утверждений о параллельных программах

Описание: статья, в которой представлены доказательства инвариантности параллельных программ.

Техника аксиоматического доказательства для параллельных программ I

Описание: В этой статье, наряду с работой тех же авторов «Проверка свойств параллельных программ: аксиоматический подход. Commun. ACM 19 (5): 279–285 (1976)», был представлен аксиоматический подход к верификации параллельных программ.

Дисциплина программирования

Описание: Классический учебник Эдсгера Дейкстры для аспирантов «Дисциплина программирования» расширяет его более раннюю статью «Защищенные команды, недетерминированность и формальное создание программ» и твердо устанавливает принцип формального получения программ (и их доказательств) на основе их спецификации.

Денотационная семантика

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

Временная логика программ

Описание: использование темпоральной логики было предложено как метод формальной проверки.

Определение свойств корректности параллельных программ с помощью фиксированных точек (1980 г.)

Описание: Проверка модели была представлена ​​как процедура для проверки корректности параллельных программ.

Сообщая последовательные процессы (1978)

Описание: (оригинальный) документ Тони Хоара о взаимодействующих последовательных процессах (CSP) вводит идею параллельных процессов (то есть программ), которые не разделяют переменные, а вместо этого взаимодействуют исключительно путем обмена синхронными сообщениями.

Расчет коммуникационных систем

Описание: В статье Робина Милнера A Calculus of Communicating Systems (CCS) описывается алгебра процессов, позволяющая формально рассуждать о системах параллельных процессов, что было невозможно для более ранних моделей параллелизма (семафоры, критические секции, исходный CSP).

Разработка программного обеспечения: строгий подход

Описание: Учебник Клиффа Джонса «Разработка программного обеспечения: строгий подход» - это первое полномасштабное изложение Венского метода разработки (VDM), разработанного (в основном) в исследовательской лаборатории IBM в Вене за предыдущее десятилетие и сочетающего в себе идею программы. уточнение по Дейкстру с уточнением (или реификацией) данных, посредством чего алгебраически определенные абстрактные типы данных формально преобразуются во все более «конкретные» представления.

Наука программирования

Описание: Учебник Дэвида Грайса «Наука программирования» описывает самый слабый метод предусловия Дейкстры для формального вывода программ, за исключением гораздо более доступной формы, чем более ранняя «Дисциплина программирования» Дейкстры .

Он показывает, как создавать программы, которые работают правильно (без ошибок, кроме ошибок ввода). Это делается путем демонстрации того, как использовать выражения предикатов предусловия и постусловия и методы доказательства программ для управления способом создания программ.

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

Общение последовательных процессов (1985)

Описание: Учебник Тони Хоара по взаимодействующим последовательным процессам (CSP) (в настоящее время третий наиболее цитируемый справочник по информатике за все время) представляет обновленную модель CSP, в которой взаимодействующие процессы даже не имеют программных переменных и которая, как CCS, позволяет системам процессов рассуждать формально.

Линейная логика (1987)

Описание: Линейная логика Жирара стала прорывом в разработке систем типизации для последовательных и параллельных вычислений, особенно для систем типизации, ориентированных на ресурсы.

Расчет мобильных процессов (1989)

Описание: эта статья знакомит с Pi-Calculus , обобщением CCS, обеспечивающим мобильность процессов. Исчисление чрезвычайно простое и стало доминирующей парадигмой в теоретическом изучении языков программирования, систем набора текста и логики программ.

Обозначение Z: Справочное руководство

Описание: Классический учебник Майка Спайви «Нотация Z: Справочное руководство» обобщает формальную нотацию языка спецификаций Z , которая, хотя и была создана Жаном-Раймоном Абриалем, развивалась (в основном) в Оксфордском университете за предыдущее десятилетие.

Коммуникация и параллелизм

Описание: Учебник Робина Милнера «Коммуникация и параллелизм» представляет собой более доступное, хотя и технически продвинутое, изложение его более ранних работ по CCS.

Практическая теория программирования

Описание: актуальная версия предикативного программирования . Основа для UTP К. Хоара . Самые простые и всесторонние формальные методы.

Рекомендации