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

редактировать
Список статей в Википедии

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

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

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

Содержание

  • 1 Вычислимость
    • 1.1 Вычислимость Катленда: введение в рекурсивную функцию Теория (Кембридж)
    • 1.2 Разрешимость теорий и автоматов второго порядка на бесконечных деревьях
    • 1.3 Конечные автоматы и проблемы их решения
    • 1.4 Введение в теорию автоматов, алгоритмы и вычисления
    • 1.5 Некоторые формальные свойствах грамматики
    • 1.6 О вычислимых числах с приложением к Entscheidungsproblem
    • 1.7 Рекурсивные функции
    • 1.8 Представление событий в нервных сетях и конечных автоматах
  • 2 Теория вычислительной сложности
    • 2.1 Вычислительная система Арора и Барака циональная сложность и вычислительная сложность Голдрайха (оба Кембриджа)
    • 2.2 Машинно-вычислительная теория сложности рекурсивных функций
    • 2.3 Алгебраические методы для интерактивных систем доказательства
    • 2.4 Сложность процедур доказательства теорем
    • 2.5 Компьютеры и несговорчивость: руководство по теории NP-полноты
    • 2.6 Степень сложности вычислений функции и частичное упо рядочение рекурсивных множеств
    • 2.7 Насколько хорош симплекс-метод?
    • 2.8 Как построить случайные функции
    • 2.9 IP = PSPACE
    • 2.10 Сводимость среди комбинаторных задач
    • 2.11 Сложность знания интерактивных систем доказательства
    • 2.12 Письмо Гёделя фон Нейману
    • 2.13 О вычислительной сложности алгоритмов
    • 2.14 Пути, деревья и цветы
    • 2.15 Теория и приложенияных функций
    • 2.16 Вычислительная сложность
    • 2.17 Интерактивные доказательства и трудность аппроксимирующих клик
    • 2.18 Вероятностная проверка: новый характер эризации NP
    • 2.19 Проверка доказательства и трудность задач аппроксимации
    • 2.20 Внутренняя вычислительная сложность функций
  • 3 Алгоритмы
    • 3.1 "Машинная программа для доказательства теорем"
    • 3.2 "Машина-ориентированная логика, основанная на принципе разрешения«
    • 3.3 «Задача коммивояжера и минимальные остовные деревья »
    • 3.4« Полиномиальный алгоритм в линейном программировании »
    • 3.5« Вероятностный алгоритм проверки простоты »
    • 3.6« Оптимизация путем имитац ии отжига »
    • 3.7 Искусство программирования
    • 3.8 Алгоритмы + структуры данных = программы
    • 3.9 Дизайн и анализ компьютерных алгоритмов
    • 3.10 Как решить это с помощью компьютера
    • 3.11 Алгоритмы
    • 3.12 Введение в алгоритмы
  • 4 Алгоритмическая теория информации
    • 4.1 «О таблицах случайных чисел»
    • 4.2 «Формальная теория индуктивного вывода»
    • 4.3 «Алгоритмическая теория информации»
  • 5 Теория информации
    • 5.1 »Математическая теория коммуникации «
    • 5.2» Ошибка дет. Коды, исправляющие и исправляющие ошибки "
    • 5.3" Метод построения минимальных избыточных кодов "
    • 5.4" Универсальный алгоритм последовательного сжатия данных "
    • 5.5 Элементы теории информации
  • 6 Формальная проверка
    • 6.1 Присвоение смысла программам
    • 6.2 Аксиоматическая основа компьютерного защищенного программирования
    • 6.3 Доказательство утверждений о параллельных программах
    • 6.4 Доказательство утверждений о параллельных программах
    • 6.5 Техника аксиоматического доказательства для параллельных программ I
    • 6.6 Дисциплина программирования
    • 6.7 Денотационная семантика
    • 6.8 Временная логика программ
    • 6.9 Характеристика корректности параллельных программ с помощью фиксированных точек (1980)
    • 6.10 Обмен данными между последовательными процессами (1978)
    • 6.11 Исчисление соответствующих систем
    • 6.12 Разработка программного обеспечения : строгий подход
    • 6.13 Наука программирования
    • 6.14 Обмен последовательными процессами (1985)
    • 6.15 Линейная логика (1987)
    • 6.16 Исчисление Мобильного Процесса (1989)
    • 6.17 Нотация Z: Справочное руководство
    • 6.18 Связь и параллелизм
    • 6.19 Практическая теория программирования
  • 7 Ссылки

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

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

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

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

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

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

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

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

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

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

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

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

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

Rekursive Funktionen

  • Петер, Рожа (1951). Рекурсивные функции. Академическая пресса. ISBN 9780125526500.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Компьютеры и несговорчивость: Руководство по теории NP-полноты

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

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

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

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

  • Виктор Клее и
  • Клее, Виктор ; (1972). «Насколько хорош симплексный алгоритм?». В кальяне, Овед (ред.). Неравенства III (Труды Третьего симпозиума по неравенству, проходившего в Калифорнийском университете, Лос-Анджелес, Калифорния, 1–9 сентября 1969 г., посвященного памяти Теодора С. Моцкина). Нью-Йорк-Лондон: Academic Press. С. 159–175. MR 0332165. CS1 maint: ref = harv (ссылка )

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

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

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

IP = PSPACE

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

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

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

Описание: Эта статья показала, что 21 различная проблема представляет собой NP-Complete и демонстрируют концепции.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проверка доказательств и твердость задач аппроксимации

Описание: Эти три статьи установили тот удивительный факт, что некоторые проблемы в 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 года «Дисциплина программирования») предлагается вместо формальной проверка после того, как она была написана (т.е. постфактум), программы и их формальные доказательства должны разрабатываться рука об руку (с использованием преобразователей предикатов для уточнения самых слабых предварительных условий), метод, известный как программный (или формальный) уточнение (или вывод), или иногда «правильность построения».

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

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

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

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

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

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

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

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

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

  • Пнуэли, А. (1977). «Временная логика программ». 18-й ежегодный симпозиум по основам информатики (SFCS 1977). IEEE. С. 46–57. doi : 10.1109 / SFCS.1977.32.

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

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

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

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

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

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

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

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

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

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

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

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

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

Связь последовательных процессов (1985)

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

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

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

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

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

Нотация Z: Справочное руководство

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

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

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

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

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

Ссылки

Последняя правка сделана 2021-05-28 09:43:13
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте