이론적 컴퓨터 과학이 무엇인지 더 배울 수있는 곳은? 주제에 관심이 있는지, 어떤

저는 수학을 전공하는 대학원생이며 이론적 인 컴퓨터 과학은 주제에 대해 잘 읽을 수 없었기 때문에 그것이 무엇인지 이해하지 못하는 영역입니다. 이 도메인이 실제로 어떤 주제인지, 어떤 주제에 관심이 있는지, 어떤 필수 구성 요소가 필요한지 등을 알고 싶습니다. 지금은 알고 싶습니다.

이론적 인 컴퓨터 과학에 대한 좋은 입문서는 무엇입니까?

그런 것이 있다고 가정합니다. 그렇지 않다면, 컴퓨터 과학에 대한 기본 지식을 가진 수학자 (즉, 하나 또는 두 개의 프로그래밍 언어의 기초를 알고있는)는 이론적 인 컴퓨터 과학이 무엇인지 이해하기 시작하면 어디에서 시작해야합니까? 추천 메뉴가 무엇인가요?

감사!



답변

첫째, “이론적 컴퓨터 과학”은 사람들마다 다른 것을 의미합니다. 나는이 사이트에있는 대부분의 사용자들에게 (현대 사회 학적 경향을 반영하는) 역사적 풍자 만화는 “이론 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 추측을 가리키게 함 ), 불변의 이론, 표현 이론, 구적법, 그리고 계속해서. 관련 질문도 참조하십시오


답변

크리스토퍼 무어와 스테판 머튼의 계산의 본질.