Теоретическая информатика

Интеллектуальная карта для подобласти теоретической информатики

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

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

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

История теоретической информатики

Теоретическая информатика тесно связана с математикой и логикой. В 20 веке эмансипация и образование проходили как самостоятельная дисциплина.

Пионерами этой дисциплины были Курт Гедель , Алонзо Черч , Алан Тьюринг , Стивен К. Клини , Клод Шеннон , Джон фон Нейман , Ганс Гермес и Ноам Хомский .

Логик Генрих Шольц попросил (и получил) у Тьюринга в 1936 году копию его новаторской работы « О вычислимых числах в приложении к« проблеме принятия решений »» . На основе этой работы Шольц провел (по словам Ахима Клаузинга) «первый в мире семинар по информатике».

Теория автоматов и формальные языки

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

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

Иерархия Хомского

Большинство формальных языков, которые появляются на практике, например, языков программирования, имеют простую структуру и могут быть разделены на один из хорошо известных языковых классов иерархии Хомского в соответствии с их сложностью . Иерархия Хомского, по словам Ноама Хомского , пионера в теории языка, состоит из четырех классов. Это, в порядке возрастания их мощности, обычные языки (тип 3), контекстно-свободные языки (тип 2), контекстно-зависимые языки (тип 1) и языки с рекурсивным перечислением (тип 0).

Языковые классы иерархии Хомского следующие:
Тип 3 ⊂ Тип 2 ⊂ Тип 1 ⊂ Тип 0, представленный здесь включениями
R ⊂ L CF ⊂ L ECS ⊂ L RE .
Регулярные языки могут быть получены из конечных автоматов ,
контекстно-свободные языки (недетерминированных) выдвигающихся автоматов ,
контекстно-зависимые языки из линейно ограниченных машин Тьюринга и
рекурсивно перечислимые языки распознаются общими машинами Тьюринга .

Существует эквивалентность между четырьмя классами грамматики и четырьмя машинными классами иерархии Хомского с точки зрения их сгенерированных и распознаваемых классов языков. Формальные языки, которые генерируются соответствующими классами грамматики иерархии Хомского, могут, как указано выше, распознаваться соответствующими машинными классами и наоборот.

Накачка и леммы Джаффе

Хорошо известными практическими помощниками в описании регулярных и контекстно-свободных языков являются леммы о накачке , которые обеспечивают необходимое, но недостаточное условие того, что язык, генерируемый грамматикой, является регулярным или контекстно-независимым. Из-за структуры формулировок лемм лемма о накачке для регулярных языков также называется теоремой uvw, а лемма о накачке для контекстно-свободных языков также называется теоремой uvwxy. В отличие от лемм о накачке, расширения, подобные лемме Яффе , предоставляют достаточный критерий .

Описание грамматик 2-го типа

Форма Бэкуса-Наур (после того, как Джон У. Бэкуса и Питер Наур ) или BNF является условным обозначением для контекстно-свободных грамматик и , таким образом , для контекстно-свободных языков. BNF используется на практике, например, для определения синтаксиса языков программирования . Соответствующий синтаксис языков программирования Pascal и Modula-2 был определен в расширенной форме Бэкуса-Наура , EBNF. Расширенная форма Бэкуса-Наура отличается от BNF только несколькими расширениями обозначений.

Теория вычислимости

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

Интуитивная и формальная предсказуемость и тезис Черча

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

Теорема о неполноте, проблема остановки и теорема Райса

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

Теория сложности

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

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

Центральный вопрос (если не главный) в теории сложности, который оставался открытым на протяжении десятилетий, заключается в том, совпадают ли классы NP и P - решение NP-полной задачи за детерминированное полиномиальное время будет достаточным в качестве доказательства. Аналогично этому, может быть предпринята попытка эффективно решить NP-полную задачу на компьютере, эквивалентном Тьюрингу ( см. Также тезис Черча ).

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

Формальная семантика

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

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

Различают в зависимости от математического подхода.

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

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

логика

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

Другие важные исследователи

литература

  • Александр Астерот , Кристель Байер: теоретическая информатика. Введение в предсказуемость, сложность и формальные языки. Пирсон, Мюнхен, 2003 г., ISBN 3-8273-7033-7
  • Катрин Эрк, Лутц Приезе: теоретическая информатика. Всестороннее введение. 3-е издание, Springer, Берлин, 2008 г., ISBN 3-540-76319-8
  • Бернхард Хайнеманн, Клаус Вайраух: Логика для компьютерных ученых. Введение. Teubner, Штутгарт 2000, ISBN 3-519-12248-0
  • Джон Э. Хопкрофт , Раджив Мотвани , Джеффри Уллман : Введение в теорию автоматов, формальные языки и теорию сложности . 2., перераб. Версия. Pearson Studium, Мюнхен, 2002 г., ISBN 3-8273-7020-5 (Оригинальное название: Введение в теорию автоматов, языки и вычисления . Перевод Сигрид Рихтер, Ингрид Токар).
  • Джон Келли: Логика в простом тексте. Пирсон, Мюнхен, 2003 г., ISBN 3-8273-7070-1
  • Уве Шёнинг : Теоретическая информатика - в двух словах. Spectrum Academic Publishing House, Гейдельберг 2003, ISBN 3-8274-1099-1
  • Кристиан Вагенкнехт: Формальные языки, абстрактные автоматы и компиляторы: учебник и рабочая тетрадь для базовых исследований и повышения квалификации . Vieweg + Teubner, 2009 г., ISBN 3-8348-0624-2
  • Инго Вегенер : Теоретическая информатика. Алгоритмическое введение. Teubner, Штутгарт 1999, ISBN 3-519-12123-9
  • Клаус В. Вагнер: Введение в теоретическую информатику. Основы и модели. Springer, Берлин 1997, ISBN 3-540-58139-1
  • Клаус Вейрах : Вычислимость. Springer, Берлин 1987, ISBN 3-540-13721-1
  • Ренате Винтер: Теоретическая информатика. Основы с упражнениями и решениями. Ольденбург, Мюнхен, 2002 г., ISBN 3-486-25808-7
  • Рольф Сохер : Теоретические основы информатики. Hanser Verlag, Мюнхен 2005, ISBN 3-446-22987-6
  • Джордж М. Рид, А. В. Роско, Р. Ф. Вахтер: топология и теория категорий в компьютерных науках. Oxford University Press 1991, ISBN 0-19-853760-3
  • Клаус Кеймель: Сферы и процессы. Springer 2001, ISBN 0-7923-7143-7
  • Дирк В. Хоффманн : Теоретическая информатика . 1-е издание. Справочник Hanser, Мюнхен 2007, ISBN 978-3-446-41511-9 .

веб ссылки

Индивидуальные доказательства

  1. ↑ Копия была найдена Ахим Клаузинг в Институте компьютерных наук в Университете Вестфальская Вильгельма в Мюнстере ( Westfälische Nachrichten 28 января 2013 года :. По следам первопроходца: Оригинал гравюр компьютер ученого Алана Тьюринга в Мюнстере библиотеке университета ; онлайн ).
  2. ↑ Уве Шёнинг: Теоретическая информатика - в двух словах / Уве Шёнинг . Спектр, Акад. Верл., Гейдельберг 2001, ISBN 3-8274-1099-1 , стр. 39,57 .
  3. ↑ Уве Шёнинг: Теоретическая информатика - в двух словах / Уве Шёнинг . Спектр, Акад. Верл., Гейдельберг 2001, ISBN 3-8274-1099-1 , стр. 149 ff .
  4. ↑ Уве Шёнинг: Теоретическая информатика - в двух словах / Уве Шёнинг . Спектр, Акад. Верл., Гейдельберг 2001, ISBN 3-8274-1099-1 , стр. 127 ff .
  5. ↑ Уве Шёнинг: Теоретическая информатика - в двух словах / Уве Шёнинг . Спектр, Акад. Верл., Гейдельберг 2001, ISBN 3-8274-1099-1 , стр. 130 ff .