Теоретическая информатика ( TCS ) представляет собой подмножество общей информатики и математики , которое фокусируется на математических аспектах информатики , таких как теория вычислений , лямбда-исчисление и теория типов .
Трудно точно определить теоретические области. Группа специальных интересов ACM по алгоритмам и теории вычислений (SIGACT) дает следующее описание: [1]
TCS охватывает широкий спектр тем, включая алгоритмы , структуры данных , вычислительную сложность , параллельные и распределенные вычисления, вероятностные вычисления , квантовые вычисления , теорию автоматов , теорию информации , криптографию , семантику и проверку программ , машинное обучение , вычислительную биологию , вычислительную экономику , вычислительную технику. геометрия , вычислительная теория чисел иалгебра . Работы в этой области часто отличаются упором на математическую технику и строгость .
В то время как логический вывод и математическое доказательство существовали ранее, в 1931 году Курт Гёдель доказал своей теоремой о неполноте , что существуют фундаментальные ограничения на то, какие утверждения могут быть доказаны или опровергнуты.
Эти разработки привели к современному изучению логики и вычислимости , а также к области теоретической информатики в целом . Информационная теория была добавлена к этой области с математической теорией коммуникации 1948 года Клодом Шенноном . В том же десятилетии Дональд Хебб представил математическую модель обучения мозга. С ростом биологических данных, подтверждающих эту гипотезу с некоторыми изменениями, были установлены поля нейронных сетей и параллельной распределенной обработки . В 1971 году Стивен Кук и, работая независимо, Леонид Левин , доказал, что существуют практически важные задачи, которые являются NP-полными — знаковый результат в теории сложности вычислений .
С развитием квантовой механики в начале 20 века появилась концепция, согласно которой математические операции можно выполнять над волновой функцией всей частицы. Другими словами, можно одновременно вычислять функции для нескольких состояний. Это привело к концепции квантового компьютера во второй половине 20-го века, которая получила широкое распространение в 1990-х годах, когда Питер Шор показал , что такие методы можно использовать для разложения больших чисел на множители за полиномиальное время . алгоритмы шифрования с открытым ключом , такие как RSA_(cryptosystem) , небезопасны. [ нужна ссылка ]