Сделай сам: MSc Computer Science на уровне топ американских университетов из дома
Вступление Давно хотел написать статью про образование в Computer Science, но руки не доходили. Решил все-таки это наконец сделать. Итак, о чем пойдет речь? Речь о том, что из себя представляет диплом MSc Computer Science топовых университетов США (во всех подробностях, включая основные курсы, книги и проекты) и как ему соответствовать.
Почему именно MSc? Это — некая развилка: с одной стороны после MSc — вы уже готовый к жизни инженер (да, речь идет о инженерной подготовке, как мне кажется это самое больное место в нашей системе образования), с другой — можно спокойно идти по пути PhD. Как известно, в PhD программу можно попасть и не особо умея программировать — особенно это касается теоретического Computer Science. С другой стороны найти работу программиста тоже дело не очень сложное, и часто не требует мощного образования. Но достигнув уровня MSc — вы получаете возможность разбираться как во всех новый идеях в Computer Science, так и возможность их воплотить в практику. То есть с одной стороны круто разобраться в каком-нибудь deep learning и сделать в нем что-то новое, а также взять и написать свою операционную систему (кто так сделал?). Причем вы не зажаты в рамки узкой специализации (если конечно продолжаете учиться). То есть вы теперь — универсальный солдат, готовый на все.
Надеюсь что эта статья будет полезна:1. Студентам, которые хотят соответствовать высоким стандартам топ вузов США, или собирающиеся туда в аспирантуру по Computer Science2. Профессионалам, которые хотят закрыть «дыры» и пробелы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, но ползет вверх каждый год!)
