Я аспирант по математике, и теоретическая информатика - это область, в которой я никогда не понимал, о чем она, потому что не мог найти хорошее прочтение по этой теме. Я хочу знать, о чем этот домен на самом деле, какие темы он затрагивает, какие предпосылки необходимы для его запуска и т. Д. На данный момент я просто хочу знать:
Что такое хорошая вводная книга по теоретической информатике?
Учитывая, что есть такая вещь. Если нет, то с чего начать математику, обладающему базовыми знаниями в области компьютерных наук (то есть основам одного или двух языков программирования), если он хочет понять, что такое теоретическая компьютерная наука? Что вы порекомендуете?
Благодарность!
Ответы:
Во-первых, «теоретическая информатика» означает разные вещи для разных людей. Я думаю, что для большинства пользователей этого сайта историческая карикатура (которая отражает некоторые современные социологические тенденции) заключается в том, что существуют «Теория А» и «Теория В» (без подразумеваемого отношения порядка между ними): Теория А состоит из теории алгоритмы, теория сложности, криптография и тому подобное. Теория B состоит из таких вещей, как теория языков программирования, теория автоматов и т. Д. В зависимости от ваших вкусов в математике, вы можете предпочесть одно другому (или оба одинаково). Я более знаком с «Теорией А», поэтому позвольте мне дать некоторые ссылки там:
Начните с книги Сипсера. Это даст вам хорошее представление об автоматах, машинах Тьюринга, вычислимости, сложности Колмогорова, P vs NP и некоторых других классах сложности. Он очень хорошо написан (на мой взгляд, это одна из самых лучших технических книг за всю историю )
Что касается алгоритмов, я немного предпочитаю Kleinberg-Tardos, но есть много хороших вводных книг. Вы можете быть особенно заинтересованы в вычислительной геометрии, которая имеет свой собственный набор замечательных книг.
Учитывая, что вы аспирант по математике, основным разделом TCS, который отсутствует в этих книгах, является теория алгебраической сложности, которая часто тесно связана с алгеброй (как коммутативной, так и некоммутативной), теорией представлений, теорией групп и алгебраической геометрией. , Здесь есть канонический текст: Бургиссер-Клаузен-Шокроллахи. Это в некоторой степени энциклопедия, поэтому, возможно, это не лучшее введение, но я не уверен, что в этой области есть действительно вводная книга. Вы также можете проверить опросы Чена-Каяла-Вигдерсона и Шиплка-Иегудаева.
После этого я бы посоветовал просмотреть более продвинутые книги по конкретным темам, в зависимости от вашего математического вкуса:
«Арора-Барак» - более современная теория сложности (продолжает, так сказать, там, где заканчивается книга Сипсера), дающая вам представление об используемых техниках (главным образом, сочетание комбинаторики и алгебры)
Книга Юкны о сложности булевых функций делает то же самое, но более детально о сложности булевых схем, в частности (очень комбинаторный по своему вкусу)
Теория геометрической сложности. Смотрите здесь или введение Ландсберга для геометров .
Книга О'Доннелла « Анализ булевых функций» имеет более фурье-аналитическую наклонность.
Криптография. Более сложными математическими аспектами здесь обычно являются теория чисел и алгебраическая геометрия. Хотя эти чисто математические аспекты представляют собой лишь небольшую часть криптографии, они важны и могут вас заинтересовать. Не будучи моей областью, я не уверен, какая хорошая стартовая книга здесь.
Теория кодирования. Здесь математическая теория варьируется от упаковки сфер (см. Книгу Конвея и Слоана) до алгебраической геометрии (например, книга Стихтенота). Опять же, это не моя область, поэтому я не уверен, что это лучшие отправные точки, но пролистывая их, вы быстро почувствуете вкус и решите, хотите ли вы углубиться глубже.
И затем есть много других математических тем, которые появляются только в исследовательской литературе, таких как связи с пенами, теория графов, C * -алгебры (позвольте мне просто указать на гипотезу Кадисона-Сингера ), теория инвариантов, теория представлений, квадратуры, и так далее. Смотрите также эти связанные вопросы
источник
Природа вычислений Кристофера Мура и Стефана Мертенса.
источник