Computer science что входит
Как разобраться в Computer Science самостоятельно
Авторизуйтесь
Как разобраться в Computer Science самостоятельно
Для большинства программистов Computer Science — факультет в зарубежных вузах, целиком и полностью посвящённый программированию, математике и всему, что связано с разработкой программного обеспечения. К счастью, в современном мире необязательно инвестировать тысячи долларов и 4 года своей жизни в образование, ведь существует бесчисленное множество онлайн-курсов, книг и других ресурсов для изучения компьютерных наук.
Приводить сотни всевозможных материалов для программистов-самоучек мы не будем, а лишь попытаемся ответить на два главных вопроса:
В качестве ответа приведём список материалов, опубликованный Озаном Онай (Ozan Onay) и Майлзом Бёрном (Myles Byrne) — инструкторами в школе компьютерных наук Брэдфилда в Сан-Франциско. Данная подборка литературы и курсов основана на личном опыте обучения сотен программистов-самоучек.
Зачем изучать компьютерные науки?
Существует два типа программистов: те, кто владеют компьютерными науками достаточно хорошо, чтобы совершать инновации, и те, кто вроде как что-то могут благодаря знанию пары-тройки высокоуровневых инструментов.
И те и другие называют себя программистами или инженерами программного обеспечения и имеют примерно одинаковые доходы в начале своей карьеры. Однако первые в итоге становятся более высокооплачиваемыми специалистами. Причём абсолютно неважно, работают они над известными, дорогими и большими коммерческими проектами или над инновационными open-source проектами различной сложности. Они становятся лидерами в своей области и привносят нечто большее и более качественное на рынок.
17–18 марта 2022 года, Москва, Беcплатно
Они углубленно изучают компьютерные науки, читая книги, слушая лекции, практикуясь или же упорно поглощая материал на личном опыте в своей карьере. Вторые же обычно остаются на дне, изучая различные инструменты и технологии для своей работы, а не то, на чём эти технологии основаны. Для них причиной для изучения чего-то нового является появление новых инструментов и, следовательно, устаревание старых.
На данный момент число людей в индустрии постоянно растёт, а число выпускников с факультета компьютерных наук остаётся неизменным. Перенасыщение рынка инженерами второго типа в итоге приводит оных к безработице или к сравнительно дешевому трудоустройству. Вне зависимости от ваших стремлений: хотите вы стать инженером первого типа или просто ищете способ заработать немного денег, изучение Computer Science — единственный надёжный путь для этого.
Дисциплины
Программирование
Структура и интерпретация компьютерных программ
Львиная доля студентов Computer Science начинают с «вводных курсов» по программированию. Однако такие курсы будут полезны не только новичкам, но и вполне себе специалистам, которые по какой-либо причине пропустили некоторые базовые для программирования вещи.
Мы рекомендуем взять во внимание классическую «Структуру и интерпретацию компьютерных программ». Прочтите как минимум три главы приведенной выше книги, выполняя упражнения для практики. Для тех, кому данная книга кажется слишком сложной, рекомендуется «How to design programs». Тем же, кому она наоборот кажется слишком лёгкой, следует обратить внимание на «Concepts, Techniques, and Models of Computer Programming».
Можно также послушать лекции университета MIT по данной теме. Как альтернативу мы рекомендуем прослушать лекции Брайана Харви из университета Беркли, особенно, если для вас это в новинку.
Для дополнительной практики возьмите на заметку ресурс Exercism: на нём можно найти сотни интересных задачек по программированию, которые помогут вам в освоении синтаксиса разных языков программирования и прокачают ваше логическое мышление, которое необходимо программисту, как воздух.
Архитектура ЭВМ
Цифровая схемотехника и архитектура компьютера
Архитектура ЭВМ, также иногда называемая «компьютерными системами» или «организацией компьютера» — достаточно важная тема, описывающая работу аппаратного слоя, который лежит на уровень ниже, чем слой программного обеспечения. Пожалуй, самая недооцененная область среди инженеров-самоучек.
The elements of Computing Systems — амбициозная книга, которая даёт понимание того, как работает компьютер. Каждая глава — строение одной маленькой детали большой системы: от написания логики на HGL (языке описания аппаратуры) через центральный процессор к созданию тетриса.
Мы рекомендуем прочесть как минимум первые 6 глав книги и завершить указанный в ней проект. Это поможет лучше понять отношения между архитектурой компьютера и программным обеспечением, которое на ней работает.
Не ищите простого объяснения сложных вещей в этой книге — автор заходит издалека. Если конкретнее, то в книге, например, почти полностью отсутствуют два очень важных концепта в современной архитектуре ЭВМ — вычислительный конвейер и иерархия памяти.
Как только вы почувствуете себя в своей тарелке, читая эту книгу, смело переходите на Computer Organization And Design, отличный текст, который стал своего рода классикой. Также обратите внимание на курс CS61C, лекции которого доступны онлайн.
Алгоритмы и структуры данных
Алгоритмы Руководство По Разработке
Мы полностью согласны с народной мудростью, которая гласит, что знание алгоритмов и структур данных — один из важнейших аспектов изучения компьютерных наук. К тому же, это отличный способ потренироваться в способности решать разного рода задачи, которые пригодятся в любой области компьютерных наук.
Есть сотни книг для изучения алгоритмов, но наш фаворит — «Алгоритмы Руководство по разработке» от Стивена Скиена. Наш выбор пал именно на неё, потому что автор определенно любит то, что он делает и хочет донести свои знания до читателя.
Для тех же, кто предпочитает лекции в формате видео, Скиена предлагает свой онлайн-курс. Также следует обратить внимание на курс Тима Рафгардена, доступного на Lagunita (сервис от университета Стэнфорда) или на Coursera. Материал обоих авторов очень полезен и информативен и кому из них уделить внимание — решать вам.
Мы практикуемся, решая задачи на Leetcode, потому что их задачи кажутся нам наиболее интересными. К тому же у каждой задачи есть ветка обсуждения и прикрепленное решение для самопроверки. Стоит отметить, что подобного рода задачи могут являться вопросами на интервью и решение их может сыграть вам на руку в будущем трудоустройстве. Для проверки своего знания алгоритмов решите 100 случайных задач на Leetcode.
В завершение, мы настоятельно рекомендуем How to solve it — великолепный материал для практики решения задач. Подходит как тем, кто изучает компьютерные науки, так и математикам.
Математика для компьютерных наук
Mathematics for Computer Science
В каком-то смысле компьютерные науки — это лишь область прикладной математики. Пока некоторые программисты пытаются и возможно преуспевают в попытках оставаться вдали от математики, мы рекомендуем не уподобляться им и изучать её. Ведь знание математики даст вам значительную фору по сравнению с другими программистами, которые математику игнорируют.
В основе большая часть математики для компьютерных наук — дискретная математика, где слово «дискретная» — прямая противоположность слову «непрерывная» и, грубо говоря, является сборником интересных тем в прикладной математике, за пределами математического анализа. Немного расплывчато, согласны. Впрочем, это не так важно: можно поставить себе цель изучить базовую логику, комбинаторику, теорию вероятности, теорию графов, основы криптографии. Линейная алгебра не менее прочего заслуживает вашего внимания, особенно для изучения компьютерной графики или машинного обучения.
Хорошим началом изучения дискретной математики является сборник лекций от László Lovász. Профессор проделал хорошую работу, чтобы сделать математику понятной и интуитивной, так что его работы куда больше подойдут новичкам, чем формальные математические тексты.
Для большего погружения советуем Mathematics for Computer Science — записи с лекций по одноименному курсу MIT, которые по объёму тянут на полноценную книгу. Видео данных лекций, кстати, тоже в свободном доступе.
Для линейной алгебры мы предлагаем начать с плейлиста Основы линейной алгебры.
Операционные системы
Operating Systems: Three Easy Pieces
Operating System Concepts и Modern Operating Systems — классика в вопросе операционных систем. Обе довольно часто подвергались критике в основном за то, что не являются 1000-страничными быстроустаревающими энциклопедиями, новое издание которых приходится покупать каждые пару лет.
Существует ещё одна книга по операционным системам, которую мы также очень рекомендуем к ознакомлению. Three Easy Pieces: структура повествования книги делает её легкой к восприятию, а задания помогут закрепить полученные знания.
После прочтения указанных выше книг имеет смысл пройтись по конкретным операционным системам и прочесть следующее: A commentary on the unix operating system, The design and implementation of the freeBSD operating systems и Mac OS internals.
Идеальный способ закрепить полученные знания — это прочесть код небольшого ядра и внести в него свои изменения. Как вариант можно взять XV6 — современную реализацию 6 версии Unix для архитектуры x86, написанную на ANSI C. В приведённой выше Three Easy Pieces есть раздел с заданиями с XV6, полный интересных идей для потенциальных проектов.
Компьютерные сети
Computer Networking: A Top-Down Approach
Учитывая то, что львиная доля работы у программистов целиком и полностью опирается на веб-сервера, компьютерные сети — одна из самых важных областей компьютерных наук. Программисты-самоучки, которые методично изучают компьютерные сети, хвастают тем, что гораздо лучше многих понимают термины, концепты, протоколы, которыми постоянно окружены в своей карьере.
Наш фаворит в этом вопросе — Computer Networking: A Top-Down Approach. Небольшие проекты и задания для практики на протяжении всего материала весьма интересны и стоят вашего внимания. Также следует обратить внимание на Wireshark labs, любезно предоставленные автором книги.
Для тех же, кто предпочитает просмотр лекций чтению книг, мы рекомендуем серию лекций от университета Стэнфорд Stanford CS 144.
Небольшие проекты, как ни странно, более полезны для освоения компьютерных сетей, нежели задачки. Некоторые из них — HTTP сервер, чат-приложение на UDP, мини TCP stack или же распределённая таблица хэшей и т.д.
Базы данных
Readings in Database Systems
Изучение баз данных требует куда большего упорства, чем нужно для других тем, так как базы данных —относительно новая область компьютерных наук (с 1970-ых). Её основы скрыты от нас по вполне себе понятным коммерческим причинам. К тому же многие потенциальные авторы книг по базам данных предпочли сами стать разработчиками и основали свои компании.
Учитывая приведенные выше обстоятельства, мы настоятельно рекомендуем новичкам избегать книжек и начинать прямиком с записей CS186 весны 2015 от Джо Геллерштейна из университета Беркли. После данного курса уже можно переходить к книжкам.
Одна из них — это Architecture of a Database System от того же профессора из того же университета. Книга даст читателю углубленный взгляд на реляционные базы данных и послужит отличным скелетом для будущих знаний в этой области.
Readings in Database Systems, также известная как красная книга по базам данных (никто не вымирает), представляет собой сборник публикаций по данной теме. Для тех, кто осилил CS186, эта книга может стать следующей остановкой.
Если вы настаиваете на том, чтобы начинать изучение баз данных по книжкам, то советуем обратить внимание на Database management systems.
Сложно закрепить знания в этой области без практики. Студенты CS186 работают над дополнениями для Spark, однако лучшей практикой для начинающих будет всё же написание своей реляционной базы данных с нуля. Скорее всего, она поначалу не будет богата уникальными особенностями, но значительно укрепит ваше понимание темы.
Под конец, моделирование данных — один из самых пренебрегаемых аспектов в изучении баз данных. Здесь нашим фаворитом является Data and Reality: A Timeless Perspective on Perceiving and Managing Information in Our Imprecise World.
Языки и компиляторы
Compilers: Principles, Techniques and Tools
Большинство программистов изучают языки программирования, в то время как специалисты компьютерных наук пытаются понять, как эти языки работают. Эти знания позволяют им опережать своих коллег по карьерной лестнице и быстрее схватывать новый материал.
Классикой в данном вопросе является Compilers: Principles, Techniques and Tools. К сожалению, этот материал больше подходит учителям, нежели самоучкам. Однако книга отлично подойдёт для непоследовательного чтения, для выхватывания отдельных кусков из материала и изучения по ним. К тому же, если у вас будет учитель, это лишь ускорит ваше обучение.
Если же вы решите учиться по данной книге без учителя, то настоятельно рекомендуем обратить внимание на серию лекций от Алекса Айкена из Стэнфордского университета.
Потенциальной альтернативой этой книге может стать Language Implementation Patterns. Она написана с упором на инженеров, которые собираются практиковаться на языках вроде DSL.
В качестве проекта для закрепления материала можно написать свой компилятор для простенького языка вроде COOL. Те, кому данный проект кажется невыполнимым, могут начать с чего-то вроде Make a Lisp.
Распределённые системы
Distributed Systems, 3rd Edition by Maarten van Steen
Число компьютеров и их разнообразие увеличилось за последние несколько десятков лет. Если раньше крупные компании закупали огромные сервера для обеспечения работы каких-либо программ, то сегодня нам кажется очевидным тот факт, что даже самые незначительные программы работают на нескольких компьютерах одновременно. Распределённые системы — наука о том, как это обеспечить.
Книга, которую мы хотим посоветовать, — Distributed Systems, третье издание которой служит прекрасным дополнением всем предыдущим. Учитывая то, что распределенные системы — область, которая достаточно часто меняется, нет уникальной книги, которая проведёт вас по этому тернистому пути. Приведённая же выше книга, по нашему мнению, наиболее близка к этому идеалу.
Можно также обратить внимание на серию лекций MIT 6.824, но, к сожалению, качество записи звука оставляет желать лучшего.
Не имеет значения, какую книгу или сторонний ресурс вы выбрали для изучения распределённых систем, погружение в эту область компьютерных наук требует от студента чтения большого количества литературы. Здесь вы можете найти список полезных книг.
Часто задаваемые вопросы
Что насчет искусственного интеллекта и графики?
Мы постарались ограничить наш материал списком дисциплин, которым, как нам кажется, любой практикующий инженер должен владеть вне зависимости от специальности и индустрии. С таким фундаментом знаний вы сможете гораздо быстрее схватывать новый материал из книг или сторонних ресурсов. Что касается ИИ и графики, вот наш список рекомендуемых материалов:
Насколько важно строго следовать порядку, приведенному в статье?
На самом деле, все 9 дисциплин достаточно часто пересекаются. К примеру, возьмите дискретную математику и алгоритмы: изучение математики поможет вам в освоении алгоритмов. Знание алгоритмов, в свою очередь, даст стимул погрузиться в дискретную математику. В идеальном сценарии программист достаточно часто повторяет данный материал в своей карьере.
По существу наша последовательность сконструирована таким образом, чтобы помочь вам начать. Если у вас есть непреодолимое желание следовать другой последовательности, мы не настаиваем. Однако мы считаем, что освоить архитектуру ЭВМ нужно перед освоением операционных систем и баз данных, а компьютерные сети и операционные системы перед распределёнными системами.
Что общего у данного списка с Open Source Society или FreeCodeCamp?
Первый содержит слишком много дисциплин для изучения, предлагает не самые лучшие материалы для большинства из них и не даёт понять, какие аспекты конкретной дисциплины наиболее ценны. Мы же попытались ограничить наш материал списком дисциплин, которые должен знать каждый инженер, вне зависимости от специальности.
Касательно FreeCodeCamp, данный ресурс сконцентрирован на программировании, а не на компьютерных науках.
А где же язык X?
Изучение конкретного языка программирования — совершенно другая плоскость, нежели изучение компьютерных наук. Изучение языка программирования — задача наиболее простая и менее ценная. Если вы уже знаете пару-тройку языков, то советуем просто следовать нашему списку дисциплин, оставляя языки на потом. Если вы знаете программирование в целом достаточно хорошо и знаете, как работают компиляторы, вам потребуется не больше недели, чтобы выучить новый язык программирования.
Почему вы до сих пор рекомендуете книжку с драконами (Compilers: Principles, Techniques and Tools)?
Потому что книжка с драконами до сих пор является полным и актуальным источником информации по компиляторам. Проблема в том, что никто и предположить не мог, что в итоге книга окажется инструкцией для преподавателей по составлению учебной программы. Вы же можете воспользоваться этим для составления своей собственной программы или следуя программе какого-либо преподавателя.
Сделай сам: MSc Computer Science на уровне топ американских университетов из дома
Вступление
Давно хотел написать статью про образование в 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, или не нужно (пока не понадобится для конкретного случая)
Языки программирования
Полемичная тема, выбора много, я предлагаю такой минимальный джентльменский набор:
— C++/Java — к сожалению в системном программировании от этих далеко не уйдешь. Но по-максимуму надо обходиться без них.
— Python — быстро что-то сваять, проверить гипотезу, классные библиотеки, особенно в машинном обучении и математике + основные фишки из функционального программирования
— Scala — практический функциональный язык, при желании можно спуститься и достаточно близко к железу. Много всего системного уже пишут на Scala. Следует сделать основной рабочей лошадкой.
(SQL, Prolog — естественно тоже, но это маленькие язычки)
Undergraduate
Курс будем считать как одну четверть — 3 месяца. Пропустим все вводные курсы про программирование.
1. Дискретная математика (не забываем, что это — уже не математика)
Комбинаторика, теория графов, дискретный тер. вер., recurrence relations, функции-генераторы.
Все это можно пропустить и освоить в других курсах (так как время не жмет). А то может стать скучно, а это — плохо.
2. Алгоритмы и структуры данных
Начиная от всяких сортировок, хэш-таблиц, разных деревьев, потом алгоритмы на графах (Djikstra, min cut/max flow).
По концептуальным знаниям: оценка сложности в нотации O, жадные алгоритмы, динамическое программирование.
Дополнительные темы: линейное программирование, алгоритмы для строк, рандомные алгоритмы.
Самые первые начала теории сложности.
Динамическое программирование вездесуще, деревья надо понимать, нижнюю границу для сортировки надо уметь выводить. Чисто теоретический курс, задачки в учебники есть. В общем довольно просто, слишком много времени не займет.
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/Object-Oriented_Turing, но можно что-то более интересное.
— Синтаксический разбор: тут надо брать что-то разумное, вроде JavaCC или ANTLR.
— Перевод в AST
— Семантический анализ: лайтово, хотя можно заморочиться с системами типов
— Генерация кода
Если есть силы и время — добавить сюда Intermediate Language и чуть-чуть оптимизации, самой простой.
В результате отлично понимаем, как работает компилятор, как реализуется вызов функции, как делать объекты, методы, массивы и прочее.
Примечание: нам приходилось все писать на C++, но в современном мире это совершенно не надо для образовательных целей. С другой стороны, если компилятор писать на Питоне или Скале (с питоном умеет работать ANTLR, со Скалой не знаю что есть — если кто-то знает хороший инструмент, просьба подсказать. Пытался понять что Spark SQL использует, но не выкопал) — можно сделать гораздо больше всего интересного с наименьшими потерями.
Ну тут так — почитать, поделать задачки. Но если есть возможность — неплохо бы спроектировать мини-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.
Аспирантура в 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/
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.
Я ссылки решил не выкладывать, чтобы не палить лишний раз, так как обычно их не очень распространяют.