Теоретическая информатика: Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию

Книга Юрая Громковича «Теоретическая информатика» представляет собой фундаментальный учебник, посвящённый теоретическим основам информатики. Автор охватывает широкий спектр классических и современных тем: теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию. Учебник является существенной переработкой предыдущего издания на немецком языке «Algorithmische Konzepte der Informatik» и основан на курсе лекций, читавшихся автором в Университете Аахена.

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

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

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

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