첫째, “이론적 컴퓨터 과학”은 사람들마다 다른 것을 의미합니다. 나는이 사이트에있는 대부분의 사용자들에게 (현대 사회 학적 경향을 반영하는) 역사적 풍자 만화는 “이론 A”와 “이론 B”가 있다는 것입니다. 알고리즘, 복잡성 이론, 암호화 및 유사 이론 B는 프로그래밍 언어 이론, 오토마타 이론 등으로 구성됩니다. 수학의 취향에 따라, 당신은 수학의 취향에 따라 다른 것을 선호 할 수 있습니다 (또는 둘 다 동일하게). “Theory A”에 대해 더 잘 알고 있습니다.

• Sipser의 책으로 시작하십시오. 이를 통해 오토마타, 튜링 머신, 계산 성, 콜로 모고 로프 복잡성, P vs NP 및 기타 몇 가지 복잡한 클래스에 대한 좋은 소개를 얻을 수 있습니다. 그것은 매우 잘 작성된 것입니다 (내 의견으로는, 그것은 가장 잘 쓰여진 기술 서적 중 하나입니다 지금까지 )

• 알고리즘의 경우 Kleinberg-Tardos를 약간 선호하지만 거기에 좋은 입문서가 많이 있습니다. 고유 한 훌륭한 책 세트가있는 계산 기하학에 특히 관심이있을 수 있습니다.

• 당신이 수학 대학원생이라는 것을 감안할 때,이 책들에서 빠진 TCS의 주요 지점은 대수학 복잡성 이론이며, 종종 대수학 (정류 및 비 정류 학), 표현 이론, 그룹 이론 및 대수 기하학과 밀접한 관련이 있습니다. . 여기에 표준 텍스트 인 Burgisser-Clausen-Shokrollahi가 있습니다. 다소 백과 사전이므로 가장 좋은 소개는 아니지만 이 영역에 실제로 소개 책 이 있는지 확실하지 않습니다 . Chen-Kayal-Wigderson과 Shiplka-Yehudayoff의 설문 조사를 확인하십시오.

그런 다음 수학적 취향에 따라 특정 주제에 대한 고급 책을 탐색하는 것이 좋습니다.

• Arora-Barak은 더 현대적인 복잡성 이론입니다 (Sipser의 책이 끝나는 곳에서 계속됩니다).

• 불리언 함수의 복잡성에 관한 Jukna의 책은 비슷하지만, 특히 불리언 회로의 복잡성 (풍미가 매우 강한 조합)에 대해 더 깊이 있습니다.

• 기하학적 복잡성 이론. 지오 미터에 대한 Landsberg의 소개 또는 여기를 참조 하십시오 .

• O’Donnell의 부울 함수 분석은 푸리에 분석이 더 많이 구부러졌습니다.

• 암호화. 여기서 더 진보 된 수학적 측면은 일반적으로 수 이론과 대수 기하학입니다. 이러한 순수한 수학적 측면은 암호화의 작은 부분만을 나타내지 만 흥미로울 수있는 중요한 부분입니다. 내 지역이 아니고, 좋은 시작 책이 무엇인지 잘 모르겠습니다.

• 코딩 이론. 여기서 수학적 이론은 구체 포장 (Conway and Sloane의 책 참조)에서 대수 기하학 (예 : Stichtenoth의 책)에 이르기까지 다양합니다. 다시 말하지만, 내 지역이 아니기 때문에 이것이 최고의 출발점인지 확실하지 않지만 그 점을 넘기면 빨리 맛을 얻고 더 깊이 파고 들지 결정할 것입니다.

그리고 거품, 그래프 이론, C * 대수와의 연결 ( Kadison-Singer 추측을 가리키게 함 ), 불변의 이론, 표현 이론, 구적법, 그리고 계속해서. 관련 질문도 참조하십시오

• 더 많은 컴퓨터 과학을 배우기를 희망하는 수학자들을위한 자료
• 이론적 인 CS에 순수한 수학에 관한 주제가 있습니까?
• 고전 수학에 TCS를 적용 하시겠습니까?
• TCS에서 범주 이론의 견고한 응용 프로그램?

답변