Алгоритмы - чистая олимпиадность. Каждый алгоритм не похож на другой и сам поиск этих алгоритмов чаще всего либо инженерный (задача решается в лоб), либо из разряда "Эврика!" - хорошо, конечно, но _любой алгоритм_ (во всяком случае из Кнута, за исключением отдельных узкоспецифичных) можно объяснить без привлечения математических дисциплин нематематику. Конечно есть всякие методы работы с полиномами еще, например, но это опять же именно небольшая узкая область где математика задействована.

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

Комбинаторика - pure mathematics. Никакого отношения к computer science не имеет вообще. Чудесная кстати наука. Очень жалею что имею в ней лишь ограниченные познания, а углубляться пока времени нет.

Вычислимость, сложность - слишком непрактично и хоть каких-то результатов сложнее тривиальных очень мало. (Они есть, но мало и никуда ничего не движется).

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

Я поясню. Я сам учился на CS. Отучился, но отказался от диплома, потому что иметь диплом того заведения, где я учился - все равно что пожизненно себя опидарасить (один из самых престижных ВУЗов рашки). Все пять лет обучения по курсу CS была примитивнейшая хуйня. Плюс надо добавить, что я туда не случайно попал - как писал выше, мечтал заниматься созданием искусственного интеллекта. По этой причине перелопатил тонны литературы по нейронным сетям, decision making, data mining, генетическим алгоритмам, автоматам и т. д. - везде наталкивался на исключительную примитивщину, которая ловко прячется за красивой терминологией, да отдельные высосанные из пальца примеры.

Я видел кучу аспирантов и к.т.н. от CS - непроходимые дебилы и быдло. Я читал диссертации - зачастую там просто написан бред, который вообще не понятно как могли пропустить.

Конечно же я не эксперт в CS, и я безусловно не претендую на абсолютное знание. Но в CS наука растворена в ничтожных пропорциях. Я не говорю что вся CS - ерунда и не наука. Я сам могу привести примеры интереснейших результатов. Но результатов там ничтожное количество в сравнении с объемами воды, да и результаты эти - решения отдельных головоломок, а не результат развития науки. Каждый из результатов CS мог бы возникнуть независимо от остальных вообще без какой-либо науки.

> вполне тривиальными и потому бессмысленными доказательствами

Это из-за карри-ховарда в основном.

Вот коллега Пирс разъясняет:
http://www.vimeo.com/6615365