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

Обновлено: 05.07.2024

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

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

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

оглавление

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

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

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

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

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

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

Большинство формальных языков, которые появляются на практике, например, языков программирования, имеют простую структуру и могут быть разделены на один из хорошо известных языковых классов иерархии Хомского в соответствии с их сложностью . Иерархия Хомского, по словам Ноама Хомского , пионера в теории языка, состоит из четырех классов. Это, в порядке возрастания их мощности, обычные языки (тип 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 - это класс задач, которые могут быть решены недетерминированной машиной Тьюринга за полиномиальное время). П. >> N П. >>

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

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

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

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

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

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

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

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

логика

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

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

литература

веб ссылки

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

  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 .
    Эта страница последний раз была отредактирована 24 августа 2021 в 17:47.

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

Теоретическая информатика имеет множество ответвлений и направлений, изучающих различные сферы ее применения.

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

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

Не нашли что искали?

Просто напиши и мы поможем

Характеристика направлений теоретической информатики

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

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

Сложно разобраться самому?

Попробуй обратиться за помощью к преподавателям

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

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

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

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

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


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

Под этим расплывчатым названием можно сгруппировать многие дисциплины, в том числе:

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

Резюме

История

В этом разделе мы рассказываем историю теоретической информатики, опираясь на разные источники:

1940-е годы


1950-е годы


Программирования на компьютерах время было трудно. Например, необходимо было подключить или отключить сотню кабелей на компьютере ENIAC , чтобы выполнить простую операцию.

Важным вкладом 1950-х годов стало создание таких языков программирования, как FORTRAN , COBOL и LISP , которые предлагают высокоуровневые конструкции для написания:

  • из условных операторов ,
  • из управляющих структур , таких как тест - петли,
  • из процедур .

Теория языков и автоматов является важной темой в 1950 - х годах, поскольку она позволяет понять выразительность компьютерных языков и их реализации. Формально определены конечные автоматы и стековые автоматы. Затем Майкл Озер Рабин и Дана Стюарт Скотт математически изучают выразительную силу и пределы возможностей этих моделей.

1960-е

В 1964 году Ноам Хомский определил иерархию Хомского . Несколько классов языков ( обычные языки , алгебраические языки , языки с контекстами, языки с рекурсивным перечислением ) соответствуют различным типам теоретических машин ( конечные автоматы , клеточные автоматы , машина Тьюринга с линейной памятью, машина Тьюринга). Изучаются различные варианты этих классов языков и машин.

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

1970-е

В 1970-е годы развивалась теория сложности . Определены классы сложности P и NP ; НП-Полнота определяется независимо друг от друга Стивен Кук и Леонид Левин . Ричард Карп продемонстрировал важность NP-полных языков. Задаётся вопрос P = NP, и исследователи предположили, что его можно решить через соответствие между машинами Тьюринга и схемами.

Также разработайте формальные методы проверки программ. Мы определяем формальную семантику для языков программирования.

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

В эти годы процветала и алгоритмика . Дональд Кнут оказал большое влияние на разработку алгоритмов, как и Ахо, Хопкрофт и Ульман.

1980-е и 1990-е годы

1980-е и 1990-е годы способствовали развитию параллельных вычислений и распределенных систем .

Сфера действия домена

Исследователи французской теоретической информатики сгруппированы в GdR Informatique Mathematics и являются членами Французской ассоциации фундаментальной информатики , членом Société informatique de France на французском уровне и членом EATCS на европейском уровне.

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

Алгоритмический

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

Формальные методы

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

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

Клод Шеннон и Уоррен Уивер усиливают эту парадигму. Инженеры по телекоммуникациям, их технические проблемы привели к тому, что они захотели измерить информацию, чтобы вывести основы коммуникации (а не теорию информации). В математической теории связи в 1948 году , они моделируют информацию для изучения соответствующих законов: шум, энтропии и хаоса, от общей аналогии с законами энергетики и термодинамики.

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

Информатика и информация, проблема терминологии

Теория графов

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

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

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

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

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

Теория языка

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

Логика для ИТ

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

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

Wikimedia Foundation . 2010 .

Смотреть что такое "Теоретическая информатика" в других словарях:

Информатика — (ср. нем. Informatik, англ. Information technology, фр. Informatique, англ. computer science компьютерная наука в США, англ. computing science вычислительная наука в Великобритании) наука о способах… … Википедия

Институт автоматики и вычислительной техники МЭИ — Институт автоматики и вычислительной техники Московского энергетического института (технического университета) … Википедия

Читайте также: