Да, до третьего курса включительно я занимался алгоритмами, и даже написал статью.
CS — огромная область, я изучал более-менее исключительно
теорию (Theoretical Computer Science),
и то далеко не всю.
Я знаю немного алгоритмов и имею самые начальные познания в теории сложности, а вот про области
вроде формальных моделей, семантик, и всего, что связано
с логикой, я почти ничего не знаю.

Так что если под CS понимать алгоритмы,
то здесь я могу сказать, что есть несколько десятков
фундаментальных алгоритмов и несколько десятков
фундаментальных техник, плюс вариации на тему.
В этом отношении структура этой области очень
сильно отличается от структуры, скажем,
алгебраической геометрии.
Это делает её в каком-то смысле проще, а в каком-то
— сложнее для изучения. Просто войти в область,
а вот если надо узнать, какие есть алгоритмы для
данной задачи, то это уже сложнее.
Конкретный список алгоритмов и техник
у меня даже где-то был записан,
но в нём нет нужды — как я теперь вижу,
содержание семи томов Кнута его неплохо описывает,
впрочем, надо отметить, что некоторые темы у Кнута
принципиально отсутствуют, например, геометрия,
и план по ним надо искать в другом месте.

(Reply to this) (Parent) (Thread)

предыдущий пост был мой. задам, если не возражаете несколько вопросов :)
1) я хотел бы как раз заниматься theoretical computer science и расцениваю насколько это вообще реально. major у меня в автоматических системах управления, специальность хоть и инженерная, но насколько я могу судить имеет много пересечений с CS - численные методы, автоматы, теория игр, различные оптимизационные алгоритмы, динамическое программирование и т.д. сейчас хочу пойти в магистратуру, а затем на PhD именно в теоретические компьютерные науки. насколько это вообще реально для человека, который имеет образование в другой области?
2) какую математику мне стоило бы выучить?
3) что вообще из книжек стоит почитать за вычетом кнута и кормена?

(Reply to this) (Parent) (Thread)

1) Более чем реально.
И вообще, специальность не очень важна в последующих
занятиях.
У меня специальность — прикладная математика и информатика, а сейчас я занимаюсь
алгебраической топологией и некоммутативной геометрией.

2) Если заниматься алгоритмами, то там математика
не очень сложная — для большинства задач
хватает того, что описано в книге «Конкретная математика»
(Кнут, Грехем, Паташник).

3) Ещё надо читать специализированную литературу
— алгоритмы и техники из разных областей.
Например, для алгоритмов на строках можно
почитать (из того, что есть на русском) книгу Гасфилда.
Но, конечно, на английском выбор больше.
Я давно не слежу за литературой,
но могу порекомендовать сделать следующее:
идёте на сайт кафедры CS приличного американского
университета (Berkeley, MIT etc.) и смотрите, какие
учебники используются для аспирантских курсов.

(Reply to this) (Parent) (Thread)

Кстати, а как у Вас это так получилось?
В смысле, сам учусь по программе прикладная математика и информатика, оно ж весьма далеко от нужд чистой математики.

Скажем, та же алгебраическая топология отсутствует в программе в принципе, вместе с гомологической алгеброй и более-менее продвинутой коммутативной; дифференциальной топологии мало или нет вообще; функановые основы некоммутативной геометрии (как я это понимаю), то есть C*-алгебры и связанные с ними радости обычно тоже в курс не входят.

То есть мне лично любопытно было бы почитать про Ваш путь от весьма CS-ной по умолчанию специальности к чистой математике, расскажите (отдельным постом - так вообще прелесть и дико любопытно), пожалуйста.

(Reply to this) (Parent) (Thread)

Ничего из перечисленного в программе моего института, конечно, не было,
и я изучал это самостоятельно.

После третьего курса я в соавторстве с Юрой Лифшицем
придумал новый алгоритм и опубликовал статью про него.
Тогда же я понял, что алгоритмы принадлежат второй
культуре в смысле Gowers'а, а меня гораздо сильнее
привлекает первая культура, как я, например, мог видеть
из курса А. Смирнова по алгебраической геометрии, на который
я начал ходить той же осенью.
По этой причине я прекратил заниматься CS и стал активно
изучать математику,
через года подал документы в аспирантуры нескольких университетов,
и ещё через год уехал в Бёркли, где и учусь до сих пор.

(Reply to this) (Parent)

Автоматические системы управления - это очень скучная и посторонняя вещь, почему бы сразу не пойти на MSc по CS?

Всё очень реально, просто не понятно, зачем дополнительно терять время.

(Reply to this) (Parent) (Thread)

так я и собираюсь на MSc именно на CS :)

(Reply to this) (Parent)