Вступление
Давно хотел написать статью про образование в Computer Science, но руки не доходили. Решил все-таки это наконец сделать. Итак, о чем пойдет речь? Речь о том, что из себя представляет диплом MSc Computer Science топовых университетов США (во всех подробностях, включая основные курсы, книги и проекты) и как ему соответствовать.
Почему именно MSc? Это — некая развилка: с одной стороны после MSc — вы уже готовый к жизни инженер (да, речь идет о инженерной подготовке, как мне кажется это самое больное место в нашей системе образования), с другой — можно спокойно идти по пути PhD. Как известно, в PhD программу можно попасть и не особо умея программировать — особенно это касается теоретического Computer Science. С другой стороны найти работу программиста тоже дело не очень сложное, и часто не требует мощного образования. Но достигнув уровня MSc — вы получаете возможность разбираться как во всех новый идеях в Computer Science, так и возможность их воплотить в практику. То есть с одной стороны круто разобраться в каком-нибудь deep learning и сделать в нем что-то новое, а также взять и написать свою операционную систему (кто так сделал?). Причем вы не зажаты в рамки узкой специализации (если конечно продолжаете учиться). То есть вы теперь — универсальный солдат, готовый на все.
Надеюсь что эта статья будет полезна:
1. Студентам, которые хотят соответствовать высоким стандартам топ вузов США, или собирающиеся туда в аспирантуру по Computer Science
2. Профессионалам, которые хотят закрыть «дыры» и пробелы
3. Может кто-то из преподавателей возьмет на заметку для своих курсов.
4. Студентам, аспирантам американских вузов — хотелось бы тоже получить фидбэк, особенно касается последних трендов в образовании
Что же здесь будет написано? Минимум философии и общих мыслей: конкретная программа undergraduate и graduate курсов, конечно из дисциплин наиболее мне близких. Все курсы были лично прочувствованы на собственной шкуре, по этому и пишу. (Я пытался записаться на все интересные курсы, которые были, но мой основной упор — системное программирование, базы данных и искусственный интеллект. Отсюда конечно некий bias, но пытаюсь предложить более-менее универсальную программу).
Содержание
1. Базовая подготовка
2. Undergraduate программа
3. Graduate программа
4. Готовы себя проверить? Computer Science Comps.
Базовая подготовка
Первым делом надо пройтись по математике. Общепринятая теория в российской академической среде — что у нас математика очень очень классная, и мы впереди планеты всей. Но грань между теоретическим Computer Science и математикой тонка, и далее, все, что входит в Computer Science мы математикой называть не будем. Ну а в Computer Science наши успехи последних лет увы…
В двух словах суть такая — хоть математики много не бывает, перегибать палку не стоит. Нам надо получить гибридное образование — смесь ученого и инженера, и сделать это в конечное время. Поэтому математику надо минимизировать. Ибо очень много всего интересного есть в Computer Science.
— Анализ — вполне сойдет уверенное владение основами, то есть многомерный анализ надо понимать, но глубоко вникать со всеми доказательствами не обязательно
— Линейная алгебра — надо хорошо разбираться, очень нужная штука всюду. Причем желательно на довольно продвинутом уровне (собственные вектора, сингулярное разложение, сопряженные градиенты)
— Дифуры — можно спокойно пренебречь, очень редко где они вам понадобятся
— Оптимизация — очень полезно, особенно в машинном обучении это — просто железное требование
— Алгебры, топологии, прочее — с одной стороны это жутко все полезно, но с другой — изучать это по-математически, абстрактно, без прямого применения мне кажется не стоит — можно освоить, когда понадобятся (например реляционная алгебра или теория категорий для систем типов) и нужные свойства и принципы уже изучить в стыке с практикой
— Логика, теория множеств — я считаю что обязательно надо разбираться в основах. ZFC надо брать.
— Теория вероятности, статистика — по минимуму из классической математики, лучше учить то, что нужно для Computer Science в контексте машинного обучения, а то рискуете закопаться в том, что не особо полезно
— Теория игр — полезная штука, но поверхностных знаний хватит надолго
— Функциональный анализ, вариационные методы — очень классно, но изучать только если припрет, например в машинном обучении
— Численные методы — только если хотите ими потом заниматься
Все остальное или не математика, а Computer Science, или не нужно (пока не понадобится для конкретного случая)
Языки программирования
Полемичная тема, выбора много, я предлагаю такой минимальный джентльменский набор:
— ассемблер — чуть-чуть надо владеть каким-нибудь ассемблером, ибо нам придется сделать свой компилятор. Тут несколько вариантов:
- RISC штука хорошая, но где его взять, только эмулировать, не очень удобно. Но если наладите среду — то RISC
- LLVM полезная штука, но много чего упрощает, не 100% железо.
- x86 — ужасен, но gcc -S очень приятно пользоваться прямо на своем ноутбуке.
- JVM bytecode — не пробовал генерить, наверное есть удобный способ. Но, если потом много использовать JVM — может быть очень полезно.
— C++/Java — к сожалению в системном программировании от этих далеко не уйдешь. Но по-максимуму надо обходиться без них.
— Python — быстро что-то сваять, проверить гипотезу, классные библиотеки, особенно в машинном обучении и математике + основные фишки из функционального программирования
— Scala — практический функциональный язык, при желании можно спуститься и достаточно близко к железу. Много всего системного уже пишут на Scala. Следует сделать основной рабочей лошадкой.
(SQL, Prolog — естественно тоже, но это маленькие язычки)
Приступим?
Undergraduate
Курс будем считать как одну четверть — 3 месяца. Пропустим все вводные курсы про программирование.
1. Дискретная математика (не забываем, что это — уже не математика)
Комбинаторика, теория графов, дискретный тер. вер., recurrence relations, функции-генераторы.
На самом деле — это обычно начальный курс, можно посмотреть онлайн, например в MIT:
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/
Все это можно пропустить и освоить в других курсах (так как время не жмет). А то может стать скучно, а это — плохо.
2. Алгоритмы и структуры данных
Начиная от всяких сортировок, хэш-таблиц, разных деревьев, потом алгоритмы на графах (Djikstra, min cut/max flow).
По концептуальным знаниям: оценка сложности в нотации O, жадные алгоритмы, динамическое программирование.
Дополнительные темы: линейное программирование, алгоритмы для строк, рандомные алгоритмы.
Самые первые начала теории сложности.
Книжка: www.amazon.com/Introduction-Algorithms-Edition-Thomas-Cormen/dp/0262033844
Динамическое программирование вездесуще, деревья надо понимать, нижнюю границу для сортировки надо уметь выводить. Чисто теоретический курс, задачки в учебники есть. В общем довольно просто, слишком много времени не займет.
P.S. Алгоритмы дальше свои в каждой предметной области, и вернемся к общему курсу только в graduate программе.
Но сразу можно порекомендовать книгу по рандомным алгоритмам (недавно коллега посоветовал, пока только пролистал, но вроде очень грамотная), она graduate уровня, но погружаться надо начинать пораньше: www.designofapproxalgs.com/index.php
3. Теория вычислений
Здесь я пропагандирую Сипсера, вообще великолепная книжка — must read, причем годится и для graduate программы.
www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X
Это супер-важный курс, он заложит основы для всего остального. У Сипсера очень все очень интуитивно, логично и связано. (Недавно полистал Колмогорова — там сразу дается понять, что без мехматовского уровня лучше не заходить. У Сипстера — наоборот, минимум требований, минимум формализации, только самое необходимое — и все становится очень доступным).
Начинаем с определения «задачи» — у Сипсера это — язык. То есть множество строк. Алгоритм — что-то, что на любую строку говорит — да/нет. В этой концепции идет вся работа. Дальше, иерархия языков: регулярные, контекстно-независимые, вычислимые, перечислимые, невычислимые. Также очень неплохо преподносится complexity — P,NP,NP-complete,NP-hard,co-NP + рандомные классы.
Помимо хорошей теоретической подготовки получаем отличные скилы:
Работаем с конечными автоматами и регулярками
Работаем с грамматиками и с автоматом со стэком
По-программируем на Тюринговой машине — это реально надо поделать, это прикольно, расширяет сознание.
Программировать на машине можно здесь, даже есть брейкпоинты! morphett.info/turing/turing.html
Учимся доказывать, какие задачи нерешаемые, причем самыми удобными и быстрыми способами
Играемся с reductions — перевод одной задачи в другую — также очень расширяет сознание
Курс чисто теоретический, отличные задачи, те, которые со звездочками могут сломать
Например: докажем, что машина Тюринга становится по мощности конечным автоматом, если запретить ей переписывать входные символы на ленте.
4. Математическая логика и теория множеств
Обычно не входит в программу Computer Science, но я считаю надо освоить. Я по этой книжке учился, очень простая книжка, очень приятная:
www.amazon.com/Elements-Set-Theory-Herbert-Enderton/dp/0122384407
Все, на этом чисто теоретическая подготовка в undergraduate Computer Science закончена, теперь — прикладные курсы
5. Компиляторы (2 четверти)
Книга: en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools
Уже многое освоено из теории вычислений, здесь весь акцент на практику. Наша задача — сделать реальный компилятор из серьезного языка в ассемблер. Например нам дали en.wikipedia.org/wiki/Object-Oriented_Turing, но можно что-то более интересное.
— Синтаксический разбор: тут надо брать что-то разумное, вроде JavaCC или ANTLR.
— Перевод в AST
— Семантический анализ: лайтово, хотя можно заморочиться с системами типов
— Генерация кода
Если есть силы и время — добавить сюда Intermediate Language и чуть-чуть оптимизации, самой простой.
В результате отлично понимаем, как работает компилятор, как реализуется вызов функции, как делать объекты, методы, массивы и прочее.
Примечание: нам приходилось все писать на C++, но в современном мире это совершенно не надо для образовательных целей. С другой стороны, если компилятор писать на Питоне или Скале (с питоном умеет работать ANTLR, со Скалой не знаю что есть — если кто-то знает хороший инструмент, просьба подсказать. Пытался понять что Spark SQL использует, но не выкопал) — можно сделать гораздо больше всего интересного с наименьшими потерями.
6. Архитектура
Книжка: www.amazon.com/Computer-Architecture-Fifth-Edition-Quantitative/dp/012383872X
Ну тут так — почитать, поделать задачки. Но если есть возможность — неплохо бы спроектировать мини-CPU.
На чем-нибудь вроде: www.logiccircuit.org/
7. Продвинутые структуры данных
Не уверен какие тут хорошие книжки, но неплохо бы сделать свои индексы на диске:
— B-дерево
— Линейный хэш
— R-дерево
Здесь уже все жестко, C++. Но можно и не заморачиваться, если только не хотите строить базы данных/поисковики.
8. Операционные системы (2 четверти)
Тут у меня такой подход — прочитать книжку: www.amazon.com/Operating-System-Concepts-Abraham-Silberschatz/dp/0470128720, но только ради общих концепций. А реально освоить OS таким образом:
Берем Начос: en.wikipedia.org/wiki/Not_Another_Completely_Heuristic_Operating_System (или Nachos 5.0j) и пишем свои модули:
— Примитивы синхронизации
— Библиотечка потоков
— Мульти-процессинг
— Мини-шелл
— Виртуальную память
— Файловую систему
Примечание: это конечно довольно хард-корно, но стоит того. Наверное лучше взять Nachos 5.0j, дебажить виртуальную память, у которой в самой проблемы с памятью — дело не особо приятное.
После такого упражнения, никакой мистики насчет операционных систем не останется.
9. Базы данных (2 четверти)
Читаем книжку: www.amazon.com/Database-Systems-Complete-Book-Edition/dp/0131873253
Делаем следущий проект: пишем движок SQL сверху простенького хранилища, если времени мало — делаем, как MySQL — запускаем AST. Если времени больше — переводим в реляционную алгебру и добавляем пару оптимизация (каких-нибудь rule-based).
Примечание: опять же, в свое время пришлось все делать на C++/lex/yacc. Время ушло вперед, если делать на Питоне или Скале, можно с меньшими потерями сделать гораздо больше. Или взять сразу более интересный язык запросов, например OQL или SQL++.
10. Искуственный Интеллект
AI — в моих глазах всегда была и будет самой интересной областью в Computer Science, так как там всегда решают очень сложные задачи. При этом, как только что-то хорошо начинает получаться, это прекращает быть AI и выделяется в отдельную дисциплину. В общем читаем замечательную книжку, и делаем 2-3 проекта.
www.amazon.com/Artificial-Intelligence-Modern-Approach-Edition/dp/0136042597
Рекомендуемые проекты:
— A* поиск для задачи 8-королев или еще какой-нибудь, повозиться с эвристиками
— доказатель теорем (resolution theorem proving)
— сделать эффективный вывод для баесовской сети
— реализовать временную логику Алена
— само-обучиться играть в шашки или играть в шахматы mini-max-ом (считая дерево)
Хард кор: можно сделать все задания в курсеровском курсе Probabilistic Graphical Models, но это больше для уровня аспирантуры.
11. Машинное обучение
Без этой темы сейчас никак. Не в курсе, какой учебник лучше для undergrad, но в идеале освоить Бишопа:
www.amazon.com/Pattern-Recognition-Learning-Information-Statistics/dp/0387310738
Вот класс Andew Ng в Стэнфорде для undergrad, не путаем к классом на Курсере, совсем разные уровни:
cs229.stanford.edu/
И еще я нашел просто чудесные лекции на YouTube (mathematicalmonk): www.youtube.com/playlist?list=PLD0F06AA0D2E8FFBA
12. Компьютерная графика
Не особо обязательно, но каждый программист когда-то хотел написать свою игру, так что надо брать для фана и для разговоров за пивом.
Не уверен, какие хорошие книги сейчас.
Мы писали кусок OpenGL на C, очень полезно — дает представление как работают все 3D движки.
Можно еще свой Ray-Tracer написать — тоже прикольная штука.
13. Копьютерные сети
Пропустил этот курс, но есть очень хороший курс на Курсере
www.coursera.org/course/comnetworks
14. Распределенные системы
Сильно пересекаются с операционными системами, но много своих важных фишек.
Я бы просто прочитал книжку, особенно ключевые концепции, а не конкретные системы:
www.amazon.com/Distributed-Systems-Concepts-Design-Edition/dp/0132143011
Синхронизация, глобальное состояние системы, консенсус, транзакции, т.д. Сейчас всякие MPP системы стали очень популярными, здесь — основы, на которых они держатся (или не держатся, готовлю популярную статью про всякие модные базы данных).
15. Языки программирования
Часто попадается такой курс, но обычно — трата времени имо. К этому моменту написан компилятор для Turing и SQL, все ясно. Можно заморочиться чем-нибудь вроде Haskell или ML. Как вариант изучить XQuery для небольшого расширения сознания.
Тут я бы закончил undergrad программу, у вас есть диплом B.Sc., поздравляю.
Или можно пойти вширь: Security/Cryptography, Scientific Programming, забуриться в AI: Computational Lingustics например. Что мы имеем после такой программы? Можно спокойно идти работать, но есть еще пробелы в теоретической базе. Можно все заполнить самостоятельно, а можно продолжать учиться на M.Sc.
Graduate
Аспирантура в Computer Science — это не наша аспирантура. Здесь вы продолжаете учиться пару лет и сдаете comprehensive exam, в случае PhD по 5-ти дисциплинам, то есть надо в голове держать очень серьезную базу на этот момент. Очень полезное упражнение (я сдавал на MSc по 3-м, это намного проще).
И очень быстро начинается специализация. Но давайте основы:
1. Алгоритмы
То же, что и в undergrad, только уже по-настоящему, глубже, плюс рандомизация.
Тут как бы и нет всеми признанной книжки, советую полазить по сайтам университетов. То есть многие обходятся статьями, слайдами и т.п.
Ну и рандомные алгоритмы — это наше все. Так что открываем книгу: www.designofapproxalgs.com/index.php
2. Теория вычислений, по сути чистая Complexity Theory
Можно покрыть Сипсера, и попробовать прочитать еще что-нибудь. У нас был Пападимитроу, но это конечно не для слабонервных. Здесь в основном одни редукции, раньше были NP-complete, сейчас много в рандомных классах.
Еще, если нравится логика, имеет смысл почитать Descriptive Complexity: people.cs.umass.edu/~immerman/book/descriptiveComplexity.html
3. Архитектура
Та же книжка, но уже по-взрослому. Можно построить какой-нибудь продвинутый CPU.
Дальше уже специализация по большому счету. Я бы посоветовал такие области, но это уже мой bias:
4. Машинное обучение
На уровне аспирантуры можно брать Бишопа (сам еще не всего его прошел), и теория машинного обучения
Мне нравится старая добрая: www.amazon.com/An-Introduction-Computational-Learning-Theory/dp/0262111934
Но наверное уже намного актуальнее есть книги.
И можно на курсере зависнуть:
— Probabilistic Graphical Models
— Еще очень хороший курс Natural Language Processing от Columbia University
— Современные нейросети: class.coursera.org/neuralnets-2012-001
5. Теория баз данных
www.e-booksdirectory.com/details.php?ebook=7942
Это очень увлекательное поле, здесь намешано все, что можно: Логика, Теория моделей, Complexity, Descriptive Complexity, даже теорию игр поэксплуатировали. Книга довольно тяжелая и формальная, но стоит того, хотя бы выборочно прочесть и поделать упражнения.
Чего пропущено?
Совсем ничего про формальные методы нету, ну тут сложная штука. По идее между теорией множеств, искуственным интеллектом и теорией баз данных + descriptive complexity — есть весь инструментарий для верификации и доказательств, поэтому такой курс уже должен быть чисто прикладным. Если есть опыт такого курса — очень интересно было бы узнать.
Интернет математика — ну это тоже немного отдельная тема, но вся база заложена.
Все, если дойдете до сюда, делая проекты и решая задачи, можно считать, что вы достигли уровня M.Sc. в Computer Science на уровне топовых университетов мира.
Пройдем тест?
Можете поискать в сети «Computer Science Comprehensive Exam» или что-то вроде этого, и можно найти реальные экзамены уровня M.Sc. и Ph.D.
Я ссылки решил не выкладывать, чтобы не палить лишний раз, так как обычно их не очень распространяют.
P.S. На этом все. Наверное кое-что устарело, но основы всегда остаются актуальными.
P.P.S. Конечно, сидя дома на диване, сложно такую программу осилить. Делать упражнения и большие проекты особенно сложно. Без университетской среды тоже очень сложно (но и в университете бывает непросто — ночи в лаборатории — частное явление). Но! — все возможно. Все приведенные книжки (ну почти все) написаны максимально просто, требуют минимум предварительных знаний, сразу показывают, как полученные знания применять, в общем очень годятся для самостоятельного изучения. Курсы на курсере или записи лекций из университетов — тоже очень полезная штука, посмотреть лекцию требует гораздо меньше усилий, чем читать книжку, решать задачи, и т.п.
P.P.P.S. Советы для профессионалов, которые «все забыли», зажались в своей нише, но хотят опять выйти на bleeding edge: сам через это проходил, бывает замутнение мозгов и кажется что все упущено и нет надежды. Но по сути это как начать заниматься спортом после нескольких лет нездоровой пищи — начинаем с малого, ставим короткие цели, радуемся малейшему прогрессу, и довольнобыстро все формулы станут опять понятными, выстроится опять общая картина мира, и можно вновь ощутить себя студентом/аспирантом.
Сайты университетов:
Stanford: cs.stanford.edu/
MIT: www.eecs.mit.edu/
UC Berkeley: www.cs.berkeley.edu/
UC San Diego: cs.ucsd.edu/ (моя альма-матерь, ну еще не #4, но ползет вверх каждый год!)
Автор: PavelVelikhov
