Компьютер сайнс что это
Давно хотел написать статью про образование в 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, функции-генераторы.
Все это можно пропустить и освоить в других курсах (так как время не жмет). А то может стать скучно, а это — плохо.
2. Алгоритмы и структуры данных
Начиная от всяких сортировок, хэш-таблиц, разных деревьев, потом алгоритмы на графах (Djikstra, min cut/max flow).
По концептуальным знаниям: оценка сложности в нотации O, жадные алгоритмы, динамическое программирование.
Дополнительные темы: линейное программирование, алгоритмы для строк, рандомные алгоритмы.
Самые первые начала теории сложности.
Динамическое программирование вездесуще, деревья надо понимать, нижнюю границу для сортировки надо уметь выводить. Чисто теоретический курс, задачки в учебники есть. В общем довольно просто, слишком много времени не займет.
Это супер-важный курс, он заложит основы для всего остального. У Сипсера очень все очень интуитивно, логично и связано. (Недавно полистал Колмогорова — там сразу дается понять, что без мехматовского уровня лучше не заходить. У Сипстера — наоборот, минимум требований, минимум формализации, только самое необходимое — и все становится очень доступным).
Начинаем с определения «задачи» — у Сипсера это — язык. То есть множество строк. Алгоритм — что-то, что на любую строку говорит — да/нет. В этой концепции идет вся работа. Дальше, иерархия языков: регулярные, контекстно-независимые, вычислимые, перечислимые, невычислимые. Также очень неплохо преподносится complexity — P,NP,NP-complete,NP-hard,co-NP + рандомные классы.
Помимо хорошей теоретической подготовки получаем отличные скилы:
Работаем с конечными автоматами и регулярками
Работаем с грамматиками и с автоматом со стэком
По-программируем на Тюринговой машине — это реально надо поделать, это прикольно, расширяет сознание.
Программировать на машине можно здесь, даже есть брейкпоинты! morphett.info/turing/turing.html
Учимся доказывать, какие задачи нерешаемые, причем самыми удобными и быстрыми способами
Играемся с reductions — перевод одной задачи в другую — также очень расширяет сознание
Курс чисто теоретический, отличные задачи, те, которые со звездочками могут сломать мозг
Например: докажем, что машина Тюринга становится по мощности конечным автоматом, если запретить ей переписывать входные символы на ленте.
Все, на этом чисто теоретическая подготовка в undergraduate Computer Science закончена, теперь — прикладные курсы
5. Компиляторы (2 четверти)
— Синтаксический разбор: тут надо брать что-то разумное, вроде JavaCC или ANTLR.
— Перевод в AST
— Семантический анализ: лайтово, хотя можно заморочиться с системами типов
— Генерация кода
Если есть силы и время — добавить сюда Intermediate Language и чуть-чуть оптимизации, самой простой.
В результате отлично понимаем, как работает компилятор, как реализуется вызов функции, как делать объекты, методы, массивы и прочее.
Примечание: нам приходилось все писать на C++, но в современном мире это совершенно не надо для образовательных целей. С другой стороны, если компилятор писать на Питоне или Скале (с питоном умеет работать ANTLR, со Скалой не знаю что есть — если кто-то знает хороший инструмент, просьба подсказать. Пытался понять что Spark SQL использует, но не выкопал) — можно сделать гораздо больше всего интересного с наименьшими потерями.
7. Продвинутые структуры данных
Не уверен какие тут хорошие книжки, но неплохо бы сделать свои индексы на диске:
— B-дерево
— Линейный хэш
— R-дерево
Здесь уже все жестко, C++. Но можно и не заморачиваться, если только не хотите строить базы данных/поисковики.
Примечание: это конечно довольно хард-корно, но стоит того. Наверное лучше взять Nachos 5.0j, дебажить виртуальную память, у которой в самой проблемы с памятью — дело не особо приятное.
После такого упражнения, никакой мистики насчет операционных систем не останется.
Примечание: опять же, в свое время пришлось все делать на C++/lex/yacc. Время ушло вперед, если делать на Питоне или Скале, можно с меньшими потерями сделать гораздо больше. Или взять сразу более интересный язык запросов, например OQL или SQL++.
Хард кор: можно сделать все задания в курсеровском курсе Probabilistic Graphical Models, но это больше для уровня аспирантуры.
Вот класс Andew Ng в Стэнфорде для undergrad, не путаем к классом на Курсере, совсем разные уровни:
cs229.stanford.edu
12. Компьютерная графика
Не особо обязательно, но каждый программист когда-то хотел написать свою игру, так что надо брать для фана и для разговоров за пивом.
Не уверен, какие хорошие книги сейчас.
Мы писали кусок OpenGL на C, очень полезно — дает представление как работают все 3D движки.
Можно еще свой Ray-Tracer написать — тоже прикольная штука.
Синхронизация, глобальное состояние системы, консенсус, транзакции, т.д. Сейчас всякие 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-м, это намного проще).
И очень быстро начинается специализация. Но давайте основы:
2. Теория вычислений, по сути чистая Complexity Theory
Можно покрыть Сипсера, и попробовать прочитать еще что-нибудь. У нас был Пападимитроу, но это конечно не для слабонервных. Здесь в основном одни редукции, раньше были NP-complete, сейчас много в рандомных классах.
Еще, если нравится логика, имеет смысл почитать Descriptive Complexity: people.cs.umass.edu/~immerman/book/descriptiveComplexity.html
3. Архитектура
Та же книжка, но уже по-взрослому. Можно построить какой-нибудь продвинутый CPU.
Дальше уже специализация по большому счету. Я бы посоветовал такие области, но это уже мой bias:
Чего пропущено?
Совсем ничего про формальные методы нету, ну тут сложная штука. По идее между теорией множеств, искуственным интеллектом и теорией баз данных + 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: сам через это проходил, бывает замутнение мозгов и кажется что все упущено и нет надежды. Но по сути это как начать заниматься спортом после нескольких лет нездоровой пищи — начинаем с малого, ставим короткие цели, радуемся малейшему прогрессу, и довольнобыстро все формулы станут опять понятными, выстроится опять общая картина мира, и можно вновь ощутить себя студентом/аспирантом.
Прочитав название книги, многие из вас, наверное, скажут: «Ну вот, ещё одна книга для чайников. Опять нам будут рассказывать о том, что такое двоичная система исчисления и какие бывают циклы». Отчасти вы будете правы: в книге, действительно, рассказывается о простых и базовых понятиях и принципах, которые должен знать каждый программист. Только вот «теоретический минимум», изложенный в книге, включает в себя множество интересных и полезных вещей, о которых мало пишут в подобной литературе начального уровня. Задайте себе вопрос: действительно ли вы так хорошо знаете основы того, что называется Computer Science?
Бонусная задача
В заключение — небольшая задача из книги на знание теории вероятности.
Ваш замок защищён пятью башнями. Каждая имеет 20%-ную вероятность поразить захватчика, прежде чем он достигнет ворот. Каковы шансы остановить его?
Если вы думаете, что ответ — 100% (20% умножить на 5), то вы ошибаетесь. Не суммируйте вероятности независимых событий. Правильный ответ есть в книге.
Около года назад, после курсов по Data Science и работы над несколькими научно-исследовательскими проектами я, наконец, получил должность в компании, занимающейся электронной коммерцией. В этой статье я расскажу о рабочих нюансах, с которыми редко сталкиваются обычные энтузиасты Data Science.
Просто, как бином
В первой главе книги излагаются самые основы: блок-схемы, булева алгебра, базовые формулы комбинаторики и теории вероятности. Это именно то, чему студентов технических специальностей учат на предметах «Информатика» и «Дискретная математика». Если вы знаете, что A XOR B тождественно !(А↔B) и как вычислить вероятность наступления совместных, несовместных и взаимодополняющих событий, то можете смело пропускать эту главу. Кстати, на каждое правило в главе приведены довольно интересные примеры.
Распределённые системы
Лучшая книга:
SQL vs NoSQL
Шестую главу большинство читателей может лишь бегло пролистать. Ну кто из программистов не знает о реляционных и нереляционных базах данных, SQL, индексах, транзакциях и распределённых моделях? Тем же, кто только начинает свой путь в области разработки будет полезно прочитать эту главу, чтобы систематизировать базовые знания и ничего не упустить.
Часто задаваемые вопросы
Operating Systems: Three Easy Pieces
Лучшая серия лекций: Berkeley CS 162
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, полный интересных идей для потенциальных проектов.
Зачем изучать компьютерные науки?
Существует два типа программистов: те, кто владеют компьютерными науками достаточно хорошо, чтобы совершать инновации, и те, кто вроде как что-то могут благодаря знанию пары-тройки высокоуровневых инструментов.
И те и другие называют себя программистами или инженерами программного обеспечения и имеют примерно одинаковые доходы в начале своей карьеры. Однако первые в итоге становятся более высокооплачиваемыми специалистами. Причём абсолютно неважно, работают они над известными, дорогими и большими коммерческими проектами или над инновационными open-source проектами различной сложности. Они становятся лидерами в своей области и привносят нечто большее и более качественное на рынок.
Они углубленно изучают компьютерные науки, читая книги, слушая лекции, практикуясь или же упорно поглощая материал на личном опыте в своей карьере. Вторые же обычно остаются на дне, изучая различные инструменты и технологии для своей работы, а не то, на чём эти технологии основаны. Для них причиной для изучения чего-то нового является появление новых инструментов и, следовательно, устаревание старых.
На данный момент число людей в индустрии постоянно растёт, а число выпускников с факультета компьютерных наук остаётся неизменным. Перенасыщение рынка инженерами второго типа в итоге приводит оных к безработице или к сравнительно дешевому трудоустройству. Вне зависимости от ваших стремлений: хотите вы стать инженером первого типа или просто ищете способ заработать немного денег, изучение Computer Science — единственный надёжный путь для этого.
Compilers: Principles, Techniques and Tools
Большинство программистов изучают языки программирования, в то время как специалисты компьютерных наук пытаются понять, как эти языки работают. Эти знания позволяют им опережать своих коллег по карьерной лестнице и быстрее схватывать новый материал.
Классикой в данном вопросе является Compilers: Principles, Techniques and Tools. К сожалению, этот материал больше подходит учителям, нежели самоучкам. Однако книга отлично подойдёт для непоследовательного чтения, для выхватывания отдельных кусков из материала и изучения по ним. К тому же, если у вас будет учитель, это лишь ускорит ваше обучение.
Если же вы решите учиться по данной книге без учителя, то настоятельно рекомендуем обратить внимание на серию лекций от Алекса Айкена из Стэнфордского университета.
Потенциальной альтернативой этой книге может стать Language Implementation Patterns. Она написана с упором на инженеров, которые собираются практиковаться на языках вроде DSL.
В качестве проекта для закрепления материала можно написать свой компилятор для простенького языка вроде COOL. Те, кому данный проект кажется невыполнимым, могут начать с чего-то вроде Make a Lisp.
Это не Кнут, но тоже полезно
Нужно понимать, что «Теоретический минимум по Computer Science» — это не Дональд Кнут и его «Искусство программирования». Те, кто давно и профессионально занимается программированием, пожалуй, не найдут в этой книге для себя ничего нового. Она, скорее, будет интересна начинающим программистам и другим специалистам IT-сферы: тестировщикам, техническим писателям, постановщикам задач. В любом случае всегда полезно проверить и систематизировать свои базовые знания в том, что называется Computer Science. Для этого книга Владстона Феррейра Фило очень хорошо подходит. Мне как непрофессиональному программисту читать некоторые разделы этой книги было интересно — я не знал, как ответить, на часть вопросов, заданных в начале этой статьи.
Алгоритмы Руководство По Разработке
Мы полностью согласны с народной мудростью, которая гласит, что знание алгоритмов и структур данных — один из важнейших аспектов изучения компьютерных наук. К тому же, это отличный способ потренироваться в способности решать разного рода задачи, которые пригодятся в любой области компьютерных наук.
Есть сотни книг для изучения алгоритмов, но наш фаворит — «Алгоритмы Руководство по разработке» от Стивена Скиена. Наш выбор пал именно на неё, потому что автор определенно любит то, что он делает и хочет донести свои знания до читателя.
Для тех же, кто предпочитает лекции в формате видео, Скиена предлагает свой онлайн-курс. Также следует обратить внимание на курс Тима Рафгардена, доступного на Lagunita (сервис от университета Стэнфорда) или на Coursera. Материал обоих авторов очень полезен и информативен и кому из них уделить внимание — решать вам.
Мы практикуемся, решая задачи на Leetcode, потому что их задачи кажутся нам наиболее интересными. К тому же у каждой задачи есть ветка обсуждения и прикрепленное решение для самопроверки. Стоит отметить, что подобного рода задачи могут являться вопросами на интервью и решение их может сыграть вам на руку в будущем трудоустройстве. Для проверки своего знания алгоритмов решите 100 случайных задач на Leetcode.
В завершение, мы настоятельно рекомендуем How to solve it — великолепный материал для практики решения задач. Подходит как тем, кто изучает компьютерные науки, так и математикам.
Математика для компьютерных наук
Лучшая книга:
А где же язык X?
Изучение конкретного языка программирования — совершенно другая плоскость, нежели изучение компьютерных наук. Изучение языка программирования — задача наиболее простая и менее ценная. Если вы уже знаете пару-тройку языков, то советуем просто следовать нашему списку дисциплин, оставляя языки на потом. Если вы знаете программирование в целом достаточно хорошо и знаете, как работают компиляторы, вам потребуется не больше недели, чтобы выучить новый язык программирования.
Надейтесь на лучшее, но готовьтесь к худшему
Во второй главе книги автор рассказывает о понятии вычислительной сложности алгоритмов. В ней приведена методика расчёта временно́й сложности алгоритма — так называемого «О большого» — по числу требуемых операций и количеству входных данных. Наглядно показано, как различаются алгоритмы с единичной, линейной, логарифмической, квадратичной и экспоненциальной сложностью. Рассказано о том, почему первые — самые лучшие, а вторые — самые худшие алгоритмы. Ну и про пространственную сложность алгоритмов тоже упомянуто — память у современных компьютеров большая, но всё же конечная. Кстати, недавно в ленте Tproger ВКонтакте выкладывали шпаргалку со сложностью всех популярных алгоритмов. В этой главе книги как раз говорится о том, что такое сложность алгоритма и как её вычислить.
Mathematics for Computer Science
В каком-то смысле компьютерные науки — это лишь область прикладной математики. Пока некоторые программисты пытаются и возможно преуспевают в попытках оставаться вдали от математики, мы рекомендуем не уподобляться им и изучать её. Ведь знание математики даст вам значительную фору по сравнению с другими программистами, которые математику игнорируют.
В основе большая часть математики для компьютерных наук — дискретная математика, где слово «дискретная» — прямая противоположность слову «непрерывная» и, грубо говоря, является сборником интересных тем в прикладной математике, за пределами математического анализа. Немного расплывчато, согласны. Впрочем, это не так важно: можно поставить себе цель изучить базовую логику, комбинаторику, теорию вероятности, теорию графов, основы криптографии. Линейная алгебра не менее прочего заслуживает вашего внимания, особенно для изучения компьютерной графики или машинного обучения.
Хорошим началом изучения дискретной математики является сборник лекций от László Lovász. Профессор проделал хорошую работу, чтобы сделать математику понятной и интуитивной, так что его работы куда больше подойдут новичкам, чем формальные математические тексты.
Для большего погружения советуем Mathematics for Computer Science — записи с лекций по одноименному курсу MIT, которые по объёму тянут на полноценную книгу. Видео данных лекций, кстати, тоже в свободном доступе.
Для линейной алгебры мы предлагаем начать с плейлиста Основы линейной алгебры.
Опять пресловутая задача о коммивояжёре
Пятая глава содержит описание и разбор различных наиболее часто используемых алгоритмов: сортировки, поиска узла и оптимального пути в графах. Кратко рассказывается об алгоритмах решения задач линейной оптимизации, поиска максимального потока в графе, раскраски графов. Прочитав эту главу, вы получите представление о том, какие существуют стандартные алгоритмы и как их правильно применять.
Почему вы до сих пор рекомендуете книжку с драконами (Compilers: Principles, Techniques and Tools)?
Потому что книжка с драконами до сих пор является полным и актуальным источником информации по компиляторам. Проблема в том, что никто и предположить не мог, что в итоге книга окажется инструкцией для преподавателей по составлению учебной программы. Вы же можете воспользоваться этим для составления своей собственной программы или следуя программе какого-либо преподавателя.
SQL — король данных
Каждый Data Science-проект начинается с данных. И большую часть времени данные, использующиеся для решения проблемы, не очень-то легко достать — их приходится собирать из отдельных датасетов и заносить в несколько таблиц базы данных.
SQL — стандартный язык запросов для баз данных. Он используется для быстрого объединения, агрегирования, извлечения необходимой информации и позволяет удобно работать с наборами данных. Проблема в том, что большинство энтузиастов Data Science не работают с базами данных, так как обучающие датасеты обычно уже созданы кем-то другим. В действительности же 90% времени тратится на сбор и подготовку данных. Да, звучит разочаровывающе, но без данных не было бы науки о данных.
Следует отметить, что в SQL есть много диалектов, однако они похожи друг на друга — зная один, можно легко адаптироваться к другому. Просто выберите любой диалект и начните изучать его.
Насколько важно строго следовать порядку, приведенному в статье?
На самом деле, все 9 дисциплин достаточно часто пересекаются. К примеру, возьмите дискретную математику и алгоритмы: изучение математики поможет вам в освоении алгоритмов. Знание алгоритмов, в свою очередь, даст стимул погрузиться в дискретную математику. В идеальном сценарии программист достаточно часто повторяет данный материал в своей карьере.
По существу наша последовательность сконструирована таким образом, чтобы помочь вам начать. Если у вас есть непреодолимое желание следовать другой последовательности, мы не настаиваем. Однако мы считаем, что освоить архитектуру ЭВМ нужно перед освоением операционных систем и баз данных, а компьютерные сети и операционные системы перед распределёнными системами.
Нужно общаться с людьми из разных сфер
Круг общения эксперта по Data Science может быть гораздо шире, чем у обычного разработчика ПО или учёного. Исследователи Data Science тесно сотрудничают как с техническими специалистами, так и с бизнес-представителями, поэтому им необходимо знать как деловую, так и техническую сторону проектов.
Представители бизнеса, как правило, являются заказчиками готового продукта — их не волнует сложность вашей модели или красота кода, они заботятся только о причинах и следствиях. Именно здесь играют большую роль линейные и древовидные модели, которые являются «белыми ящиками». Принцип их работы можно легко объяснить и интерпретировать, чтобы доказать заказчику, что модель машинного обучения действительно решит поставленную проблему. Поскольку такие модели создаются для удовлетворения потребностей бизнеса, они должны быть адаптированы к требованиям бизнес-руководителей.
При создании и тестировании моделей специалисты Data Science тесно сотрудничают с разработчиками. Последние обычно занимаются обработкой и перемещением данных и используют результаты работы алгоритмов для превращения абстрактного кода в готовый продукт.
Исследователи Data Science должны понимать потребности бизнеса и ресурсы разработчиков, чтобы знать возможности и ограничения с обеих сторон.
Компьютерные сети
Лучшая книга:
Признаки важнее, чем модель
Линейные модели обычно считаются слишком простыми и не подходящими для реальных задач машинного обучения. Разве можно получить правильный результат, просто линейно увеличивая число признаков? На самом деле — можно.
Более сложные модели, такие как случайный лес, xgboost, SVM и DNN, ищут нелинейные границы в пространстве признаков. Это происходит либо разделением пространства на небольшие участки, либо сопоставлением признаков с пространством большей размерности, где границы выглядят линейно. Проще говоря, процесс построения модели можно рассматривать как подгон прямой линии под вновь сгенерированные точки данных. Поскольку модели не знают истинных значений признаков, они пытаются создать эти новые точки на основе некоторого ядра или путём оптимизации псевдо-функции правдоподобия.
Переход в пространство признаков большей размерности, источник
Звучит довольно сложно, верно? Вот почему такие модели часто называются серыми или чёрными ящиками. С другой стороны, если вы знаете реальные значения признаков, вы можете генерировать новые конструктивные признаки с помощью данных. Процесс генерации, преобразования и предварительной обработки признаков называется конструированием признаков. К его основным подходам относятся поиск стандартного отклонения, дискретизация, агрегирование признаков и так далее.
С правильно спроектированной моделью можно добиться отличных результатов. Линейные алгоритмы обычно лучше интерпретируются — вы можете увидеть значимость сгенерированных признаков и понять по их коэффициентам, насколько достоверна модель. Если коэффициент, который по логике должен быть положительным, оказался отрицательным, — вероятно, что-то не так с моделью, данными или изначальными предположениями.
Distributed Systems, 3rd Edition by Maarten van Steen
Число компьютеров и их разнообразие увеличилось за последние несколько десятков лет. Если раньше крупные компании закупали огромные сервера для обеспечения работы каких-либо программ, то сегодня нам кажется очевидным тот факт, что даже самые незначительные программы работают на нескольких компьютерах одновременно. Распределённые системы — наука о том, как это обеспечить.
Книга, которую мы хотим посоветовать, — Distributed Systems, третье издание которой служит прекрасным дополнением всем предыдущим. Учитывая то, что распределенные системы — область, которая достаточно часто меняется, нет уникальной книги, которая проведёт вас по этому тернистому пути. Приведённая же выше книга, по нашему мнению, наиболее близка к этому идеалу.
Можно также обратить внимание на серию лекций MIT 6.824, но, к сожалению, качество записи звука оставляет желать лучшего.
Не имеет значения, какую книгу или сторонний ресурс вы выбрали для изучения распределённых систем, погружение в эту область компьютерных наук требует от студента чтения большого количества литературы. Здесь вы можете найти список полезных книг.
Языки и компиляторы
Лучшая книга:
Алгоритмы и структуры данных
Лучшая книга:
Общие впечатления
В каждом разделе книги изложение ведётся от простого к сложному. Есть в книге и совсем базовые знания. Например, в ней, действительно, описываются двоичная система, булева алгебра и блок-схемы. Но автор делает это кратко, чтобы затем перейти к изложению более интересных вещей. Вообще, в книге почти нет ничего лишнего — вся информация изложена сжато, но вполне доступно. Несущественные и очевидные промежуточные шаги часто пропущены. Благодаря этому описание алгоритмов и правил читается легко. Как говорил Гомер Симпсон, «Мне некогда читать, передай смысл». Это как раз то, чего не хватает многим учебникам начального уровня, которые переполнены лишней и ненужной информацией.
Примеры алгоритмов в книге оформлены очень удобно — в виде псевдокода, который будет понятен всем, кто хоть раз в жизни самостоятельно написал программку с использованием функций, циклов, условий и оператора присваивания.
В конце каждой главы приведены ссылки на полезные материалы. Все они оформлены как разделы на сайте code.energy. Вот пример. В некоторых случаях они ведут на страницу с соответствующей книгой в магазине Amazon. Но есть и такие, которые открывают страницы или PDF-файлы. Последние, конечно, полезнее, чем ссылки на книгу в магазине.
Сначала стратегия, потом тактика
Третья глава называется «Стратегия». В ней очень доходчиво объясняется, что такое итерация и рекурсия и в каких случаях их лучше всего использовать. Автор рассказывает о том, как лучше организовать проверку всех подходящих решений задачи — от грубого полного перебора до поиска с возвратом и эвристических алгоритмов, а также объясняет, как использовать разделение множеств для оптимизации сортировки значений и решения других задач. Также здесь немного рассказано о динамическом программировании и методе ветвей и границ. В целом эта глава о том, как выбрать оптимальный метод для решения поставленной задачи.
Есть не только императивное программирование
Наконец, в восьмой главе содержится то, ради чего всё затевалось — рассказ о программировании. Глава разделена на два подраздела: «Лингвистика» и «Парадигмы программирования». В первом излагаются совсем базовые вещи. Например, что такое переменная. А второй подраздел можно читать, как отдельную статью-обзор современных парадигм разработки. К примеру, если вы адепт императивного программирования и не знаете, что такое карринг и замыкание, вам будет интересно познакомиться с декларативным программированием. Кстати, есть ещё логическая парадигма, о ней тоже кратко рассказывается в этой главе.
Эксперимент и запуск продукта — совершенно разные вещи
Чаще всего специалисты Data Science работают в Jupyter Notebook — это простое и удобное приложение для экспериментов и визуализации. Можно быстро попробовать что-то новое, обучить модель или увидеть результат вычислений, просто открыв ячейку и запустив несколько строк кода.
Но как только модель готова к выпуску в продакшн, господство Jupyter Notebook заканчивается, и власть переходит к Python-файлам. Продакшн — это работа ваших алгоритмов в реальной жизни. Конечный пользователь всегда смотрит на качество итогового продукта, поэтому код продакшна должен быть быстрым, чистым, читабельным, отказоустойчивым и простым в отладке.
Скорость кода не так важна, если вы просто экспериментируете и запускаете программу один-два раза. Однако в продакшне ваш код, вероятно, будет выполняться несколько раз в день и влиять на другие части продукта, поэтому скорость станет важна.
Посмотрим правде в глаза, наверняка в большинстве ваших .ipynb-файлов много неупорядоченных строк, неиспользованных import и ненужных ячеек. И это нормально, когда вы просто экспериментируете. Но перед выпуском в продакшн код нужно «очистить». Считайте, что ваш код достаточно чист, если кто-то в вашей команде может просмотреть его и с лёгкостью понять назначение каждой строки. Вот почему вы должны давать правильные имена своим переменным и функциям.
Стоит выводить важные шаги выполнения кода на экран оболочки, а также в лог-файл. Это поможет быстро выявить возможные проблемы. Хороший лог-файл должен содержать время начала и окончания выполнения, результаты и записи исключений.
Иногда даже проверенный код по какой-либо причине начинает давать сбой, и пользователи видят странные результаты. Хороший продакшн-код должен уметь обрабатывать возможные исключения и заранее выводить предупреждения в случае неожиданной или нерешаемой проблемы. В зависимости от ситуации неисправный код можно откатить до предыдущего состояния или заставить его выдать предварительные результаты. Всегда лучше потратить время на написание отказоустойчивого кода, чем потом в спешке всё переделывать.
Но даже в отказоустойчивом коде могут быть ошибки, приводящие к непредвиденным результатам. В этом случае программу нужно отлаживать. Чтобы процесс отладки был понятным и простым, всегда следите за чистотой и качеством кода: используйте функции вместо повторяющихся конструкций, помните про правило «одна функция = одна решаемая задача» и избегайте «грязных» функций. Такая практика позволит легко найти источник ошибки в коде.
Для написания продакшн-кода вместо Jupyter Notebook лучше использовать текстовый редактор или IDE, например VS Code или PyCharm. Эти инструменты сделают разработку проще и быстрее. Если вы всё же хотите работать с Jupyter, можете попробовать использовать расширение nbconvert, которое конвертирует скрипты .ipynb в .py-файлы.
Computer Networking: A Top-Down Approach
Лучшая серия лекции: Stanford CS 144
Учитывая то, что львиная доля работы у программистов целиком и полностью опирается на веб-сервера, компьютерные сети — одна из самых важных областей компьютерных наук. Программисты-самоучки, которые методично изучают компьютерные сети, хвастают тем, что гораздо лучше многих понимают термины, концепты, протоколы, которыми постоянно окружены в своей карьере.
Наш фаворит в этом вопросе — Computer Networking: A Top-Down Approach. Небольшие проекты и задания для практики на протяжении всего материала весьма интересны и стоят вашего внимания. Также следует обратить внимание на Wireshark labs, любезно предоставленные автором книги.
Для тех же, кто предпочитает просмотр лекций чтению книг, мы рекомендуем серию лекций от университета Стэнфорд Stanford CS 144.
Дисциплины
Архитектура ЭВМ
Лучшая книга:
Почему памяти полно, а программа всё равно «тормозит»
Седьмая глава называется просто и незамысловато: «Компьютеры». В ней (сюрприз!) рассказывается о том, что такое ЦП и ОЗУ и как они обмениваются командами и данными. А ещё про ассемблер, операционные системы и компиляторы. Упоминание команд одного из первых процессоров удивительным образом перекликается с разделом «Программное обеспечение с открытым исходным кодом». Сразу вспоминается рассказ Линуса Торвальдса о том, как всё начиналось, в книге «Just for fun».
Дальше рассказывается о такой полезной вещи, как иерархия памяти. Если вы не смогли ответить на вопрос про кэш уровня L1, L2 и L3, то вам стоит почитать эту часть книги.
Программирование
Лучшая книга:
Вывод
Настоящая работа Data Science-специалиста совершенно не похожа на создание любительских моделей машинного обучения для Kaggle. Я попытался перечислить ключевые различия, которые могут быть неочевидны и неизвестны заранее, и надеюсь, что вы найдёте их полезными.
Для большинства программистов Computer Science — факультет в зарубежных вузах, целиком и полностью посвящённый программированию, математике и всему, что связано с разработкой программного обеспечения. К счастью, в современном мире необязательно инвестировать тысячи долларов и 4 года своей жизни в образование, ведь существует бесчисленное множество онлайн-курсов, книг и других ресурсов для изучения компьютерных наук.
Приводить сотни всевозможных материалов для программистов-самоучек мы не будем, а лишь попытаемся ответить на два главных вопроса:
- Какие дисциплины следует изучать и почему?
- Какие из доступных ресурсов, книг, серий лекций для конкретной дисциплины имеет смысл посмотреть?
В качестве ответа приведём список материалов, опубликованный Озаном Онай (Ozan Onay) и Майлзом Бёрном (Myles Byrne) — инструкторами в школе компьютерных наук Брэдфилда в Сан-Франциско. Данная подборка литературы и курсов основана на личном опыте обучения сотен программистов-самоучек.
A/B-тесты важнее обучения модели
Важным процессом в Agile и Data Science являются A/B-тесты. Ваша модель может превзойти предыдущее решение во время обучения, но может не работать в реальной жизни. Обучающие данные — это лишь подмножество реальных данных. Они могут быть устаревшими и содержать ошибки. Поэтому модель выпускается в продакшн только в том случае, если она показывает лучшие результаты во время A/B-тестирования.
Data Science привязан к Agile
Ещё одна концепция в мире технологий — использование гибких методологий для построения рабочих процессов. Agile — философия разработки, при которой проекты делятся на небольшие задачи.
На самом деле про гибкие методологии гораздо легче рассказать, чем реализовать их. Agile больше подходит командам разработчиков с чётко определёнными тактиками решения задач. Data Science-проекты же создаются путём проб и ошибок, а время выполнения конкретных задач сложно оценить из-за высокой изменчивости. Ирония в том, что Data Science-специалист даёт точные прогнозы для других бизнес-процессов, но не может сделать то же самое для своих задач.
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.
MVP лучше, чем долгосрочное исследование
Мир технологий конкурентоспособен и изменчив. В большинстве случаев у компаний нет времени ждать идеального решения, которое достигло бы наилучшего уровня производительности. Вместо этого они начинают проект с минимально жизнеспособного продукта (minimum viable product, MVP) и развивают его. MVP должен удовлетворять самым основным потребностям проекта — ни больше, ни меньше.
Перфекционистам и людям, внимательным к деталям (то есть большинству Data Science-энтузиастов), зачастую сложно работать над MVP. Обычно исследователи стремятся тщательно проанализировать данные, опробовать множество различных моделей и найти наилучшее решение. Наука о данных по сути ориентирована именно на такой подход, однако мы не зря говорим о прикладной области Data Science.
Нужно понимать, что в разработке самый важный актив — время. Никто не может предсказать путь, по которому пойдёт продукт. Возможно, со временем проект приостановят или полностью закроют. MVP создаётся, чтобы свести риски к минимуму. Даже если продукт гарантированно будет развиваться, поначалу ему может не хватать необходимых ресурсов. Построение простой модели и её постепенное развитие с появляющимися новыми данными и технологиями даёт более надёжные результаты.
Критика формы
Ещё один недостаток бумажного издания — это очень плохой мягкий переплёт со склейкой страниц у корешка. Знаете, есть такие книги, которые при первом прочтении начинают странно потрескивать, когда вы переворачиваете страницы. А при втором прочтении они просто распадаются на отдельные страницы. Эта книга как раз из таких — «одноразовых». Так что советую читать эту книгу в электронном варианте.
Балансируем деревья
Четвёртая глава книги посвящена структурам и абстрактным типам хранения данных. Я просто перечислю те структуры и типы, о которых в ней говорится: стек, очередь, очередь с приоритетом, список, сортированный список, множество, массив, связный список, двусвязный список, дерево, двоичное дерево, двоичная куча, граф, хеш-таблица. Никаких сюрпризов в этой главе нет, автор последовательно и обстоятельно рассказывает о каждом типе и каждой структуре.
Операционные системы
Лучшая книга:
Что насчет искусственного интеллекта и графики?
Мы постарались ограничить наш материал списком дисциплин, которым, как нам кажется, любой практикующий инженер должен владеть вне зависимости от специальности и индустрии. С таким фундаментом знаний вы сможете гораздо быстрее схватывать новый материал из книг или сторонних ресурсов. Что касается ИИ и графики, вот наш список рекомендуемых материалов:
- ИИ: пройдите введение в ИИ от университета Беркли и выполните проект Pacman. Прочтите великолепную книгу от Рассела и Новрига Artificial Intelligence: A Modern Approach;
- Машинное обучение: пройдите этот курс на Coursera и убедитесь, что действительно понимаете смысл повествования и основы машинного обучения, прежде чем переходить на Deep Learning;
- Графика: ознакомьтесь с серией лекций из университета Беркли CS184 и прочтите книгу Computer Graphics: Principles and Practice.
Основная работа ведётся на удалённом сервере
Большинство людей начинают своё путешествие по Data Science на персональных компьютерах. Однако в реальных проектах зачастую требуется гораздо большая вычислительная мощность, которую не сможет обеспечить ни ноутбук, ни даже игровой ПК. Поэтому исследователи Data Science используют свои компьютеры для доступа к удалённому серверу по SSH (Secure Shell). SSH позволяет безопасно подключиться к вычислительной машине. После установки соединения удалённый сервер можно использовать как командную оболочку вашего компьютера. Поэтому при работе с сервером пригодится знание основных команд для Linux и опыт использования терминала.
Что общего у данного списка с Open Source Society или FreeCodeCamp?
Первый содержит слишком много дисциплин для изучения, предлагает не самые лучшие материалы для большинства из них и не даёт понять, какие аспекты конкретной дисциплины наиболее ценны. Мы же попытались ограничить наш материал списком дисциплин, которые должен знать каждый инженер, вне зависимости от специальности.
Касательно FreeCodeCamp, данный ресурс сконцентрирован на программировании, а не на компьютерных науках.
А вы в этом уверены?
Давайте проведём небольшой эксперимент. Попробуйте ответить на следующие вопросы:
- Сколько вы знаете методов сортировки массива, кроме метода «пузырька»?
- Почему двоичное дерево поиска должно быть хорошо сбалансировано?
- Зачем в процессоре выделяют кэш уровня L1, L2 и L3?
- Чем декларативное программирование отличается от логического и императивного?
- Почему алгоритмы с экспоненциальной временно́й сложностью на большом объёме данных считаются невыполнимыми?
- Какие задачи относятся к классу NP-полных?
- Как хранятся связный и двусвязный списки в памяти компьютера?
- Что такое каррированная функция?
Если вы не смогли уверенно ответить на бо́льшую часть этих вопросов, но сами вопросы показались вам интересными, то вам стоит прочитать эту книгу. Хотя бы для общего развития.
Базы данных
Лучшая книга:
Структура и интерпретация компьютерных программ
Львиная доля студентов Computer Science начинают с «вводных курсов» по программированию. Однако такие курсы будут полезны не только новичкам, но и вполне себе специалистам, которые по какой-либо причине пропустили некоторые базовые для программирования вещи.
Мы рекомендуем взять во внимание классическую «Структуру и интерпретацию компьютерных программ». Прочтите как минимум три главы приведенной выше книги, выполняя упражнения для практики. Для тех, кому данная книга кажется слишком сложной, рекомендуется «How to design programs». Тем же, кому она наоборот кажется слишком лёгкой, следует обратить внимание на «Concepts, Techniques, and Models of Computer Programming».
Можно также послушать лекции университета MIT по данной теме. Как альтернативу мы рекомендуем прослушать лекции Брайана Харви из университета Беркли, особенно, если для вас это в новинку.
Для дополнительной практики возьмите на заметку ресурс Exercism: на нём можно найти сотни интересных задачек по программированию, которые помогут вам в освоении синтаксиса разных языков программирования и прокачают ваше логическое мышление, которое необходимо программисту, как воздух.
Цифровая схемотехника и архитектура компьютера
Лучшая серия лекций: Berkeley CS 61C
Архитектура ЭВМ, также иногда называемая «компьютерными системами» или «организацией компьютера» — достаточно важная тема, описывающая работу аппаратного слоя, который лежит на уровень ниже, чем слой программного обеспечения. Пожалуй, самая недооцененная область среди инженеров-самоучек.
The elements of Computing Systems — амбициозная книга, которая даёт понимание того, как работает компьютер. Каждая глава — строение одной маленькой детали большой системы: от написания логики на HGL (языке описания аппаратуры) через центральный процессор к созданию тетриса.
Мы рекомендуем прочесть как минимум первые 6 глав книги и завершить указанный в ней проект. Это поможет лучше понять отношения между архитектурой компьютера и программным обеспечением, которое на ней работает.
Не ищите простого объяснения сложных вещей в этой книге — автор заходит издалека. Если конкретнее, то в книге, например, почти полностью отсутствуют два очень важных концепта в современной архитектуре ЭВМ — вычислительный конвейер и иерархия памяти.
Как только вы почувствуете себя в своей тарелке, читая эту книгу, смело переходите на Computer Organization And Design, отличный текст, который стал своего рода классикой. Также обратите внимание на курс CS61C, лекции которого доступны онлайн.
Читайте также: