Swifty Finch
ШАД, Алгоритмы и структуры данных
21.02.2018
8 мин
Статья является логическим продолжением моей последней публикации, в конце которой рассказывается о том как я получил интересную возможность стать вольнослушателем в Школе Анализа Данных в Екатеринбурге и изучать Алгоритмы и Структуры Данных.
В этой статье я расскажу о том как готовился к обучению, что происходило на первом семестре и как всегда поделюсь своими впечатлениями. Я постараюсь следовать Кодексу чести студента ШАД в своем рассказе и не выдать ничего лишнего.
Для кого эта статья?
Скорее для тех, кому интересны алгоритмы, структуры данных, обучение и ШАД. Также для тех кто не знает как к этому всему подступиться. Я не рассчитываю, что смогу заинтересовать других людей. Но если вам понравились прошлые статьи, прочтите и эту.
Подготовка
Начало обучения было запланировано на сентябрь 2017 года, и у меня было около двух месяцев на подготовку. Может показаться странным, а зачем готовиться к обучению? Курс Алгоритмы и Структуры Данных предполагает, что студент уже знает базовые алгоритмы и структуры данных, а также много разной математики. Но это явно не про меня.
Также мне заранее сказали, что скорее всего вся практика будет сдаваться на языке программирования C++. Я немного изучал язык С на первом курсе университета лет 10 назад, а из С++ знал только cin и cout. Этого явно было достаточно, чтобы успешно завалить этот курс.
Я решил начать свою подготовку с общих теоретических знаний и выбрал для этого книгу Алгоритмы: Санджой Дасгупта, Христос Пападимитриу, Умеш Вазирани. Не только потому, что мне понравились фамилии авторов, но и по рекомендациям это была самая простая книга об алгоритмах. Я бегло прочитал её за неделю. Книга оказалась очень полезной по разным причинам. К примеру, на меня снизошло прозрение в операциях по модулю.
Затем я начал смотреть различные видеолекции, в частности и старые лекции ШАД на YouTube. На это ушло много времени, я часто пересматривал одно и тоже пытаясь понять хоть что-то. Хочу признаться, это было очень тяжело. Чувствовалась нехватка знаний. Со временем я понял — пора переходить к практике так как я стал забывать, что смотрел в самом начале.
В качестве практики я решил разобрать и написать простые структуры данных и алгоритмы на Swift. Мне очень помог Swift Algorithm Club. Для мотивации я решил каждый день что-то выкладывать на Github в свой репозиторий специально созданный для этих целей.
После этого я наткнулся на статью на Habrahabr и понял, что курс Основы разработки на C++: белый пояс мне идеально подходит. Курс рассчитан на 5 недель, но у меня было только две. Этого оказалось вполне достаточно, если ударно учиться по выходным и после работы.
Как выяснилось позже всё это мне очень сильно пригодилось, без этого я скорее всего не сдал бы даже первую домашнюю работу.
Первый день обучения
В середине сентября я пошел на первый семинар в университет. Пропуска у меня еще не было и я кое-как объяснил охраннику что я пришел учиться в школу. Мне нужно было попасть в аудиторию 611. Я заблудился, и начал всех спрашивать как пройти. Мне попадались студенты, которые или не говорят на русском или говорили мне — это на 6 этаже. Но я то уже пробовал подниматься на самый верх и знал, что в этом здании всего 4 этажа…
С горем пополам я нашел нужную аудиторию. Вторым моим удивлением стало то, что в ней было около 50 человек и казалось что все уже знали друг друга, кроме меня. Позже я понял, что этот курс преподается не только для студентов ШАД, но и для магистрантов МатМеха. На последние семинары приходило всего человек 10.
На первом семинаре рассказали, что все обучение состоит из видеолекций, семинаров и домашних заданий. Видеолекции и семинары не обязательны. Всё это можно было пропускать на свой страх и риск.
Также рассказали сколько балов нужно получить на зачет/хорошо/отлично. Что балы дают в основном за решение задач и рассказ решения на семинаре у доски. Также очень важны review-задачи.
Домашние задания
Задания выдаются комплектами по несколько задач, за каждую своя оценка в балах. У каждого комплекта свой срок сдачи, до которого необходимо получить положительный результат от системы тестирования. Также необходимо описать решение задачи в PDF, оценить её сложность по времени и памяти, и доказать что алгоритм корректен и конечен.
Основной язык на котором нужно было сдавать был С++. Система тестирования также жёстко проверяла стиль кода. Нельзя было использовать однобуквенные переменные, даже в циклах. Никаких using namespace std, ограничения на ширину строк, пробелы вместо табуляции и тп. На каждую задачу прогонялось около 100 тестов, которые были закрыты. Система сообщает только номер проваленного теста.
Задачи условно можно поделить на три типа. Offline задачи — когда ваше решение практически не проверяется до окончания срока сдачи, и только после этого прогоняются все тесты без возможности внести исправления. Review задачи — когда код проверяется преподавателем, а также возможно необходимо описать алгоритм в уже объявленном интерфейсе с различными особенностями C++. И простые задачи, которые можно было отправлять на тестирование до 100 попыток.
В целом на каждую задачу я тратил около 10 часов, ближе к концу я справлялся по шустрее. Конечно всё зависит от конкретной задачи, но в целом почти все они были довольно сложными (для меня). В эти часы я также включаю просмотр видео и разбор теории. Семинары это ещё минус 3–4 часа свободного времени в неделю, если учитывать дорогу.
Процесс обучения
Так как я iOS разработчик все задачи я решал в Xcode. На мой взгляд это бесконечно удобная среда разработки, в которой приятно писать любой код (и почти не падает, да).
Я пересмотрел огромное количество лекций ШАД за разные годы, видео на YouTube из различных летних школ, зарубежных институтов (Princeton, Massachusetts, Harvard, etc.), и вот этого замечательного парня. В совокупности всё оказалось очень полезным.
Для написание теории в PDF я выбрал приложение Bear. Ограничений на формат не было, главное описать алгоритм, сложность и объяснить что он конечен и корректен. А в Bear просто приятно делать заметки.
Я не пропустил ни одного семинара. К сожалению, один семинар совпал с iOS Party, но таинственным образом преподаватель его отменил. В конце семестра я даже пару раз объяснял решения задач у доски с мелом, как настоящий школьник.
Кроме этого на семинарах рассказывали об устройстве памяти, об алгоритмах применяемых в базах данных, о сжатии различных данных и тп. В целом мне очень понравилось посещать семинары, в своё время когда я учился всё казалось очень скучным и такого желания не было.
Когда я не смог вовремя решить одну из задач мне было очень интересно узнать как её решили другие. Я почти бегом бежал на семинар и всё равно умудрился опоздать как раз на 10–15 минут, за которые и была рассказана моя задача. Очень порадовало, что преподаватель просто взял и объяснил мне её после занятия. Правда я всё равно не понял. Ничего. Позже я разобрался с ней дома.
Конец
В итоге я смог решить 21 задачу из 24. Сдал 3 review и написал 21 PDF с теорией. Были ещё дополнительные небольшие задачи и одна очень сложная задача, которую не решал никто и мы её даже не разбирали. Этого с не плохим запасом хватило на отлично.
Сложно сказать сколько времени я потратил на обучение, но думаю очень и очень много. Я очень рад, что у меня было это время благодаря гибкому графику и удаленной работе. Также очень здорово, что я получил возможность бесплатно обучаться на этом курсе благодаря Яндекс.
Хочется заметить, что ШАД это школа только по своим размерам. На самом деле учиться в ней приходится исключительно самостоятельно, иначе вы обречены на провал. В практических задачах часто требуется фантазия, чтобы увидеть определенную структуру или алгоритм. Это не просто задачи по типу напишите сортировку, как я изначально ожидал. Было действительно сложно и мне всё понравилось.
Очень частый вопрос: А тебе это всё пригодиться хотя бы? В моей работе скорее всего нет, это маловероятно. Я считаю, что это основы которые просто полезно знать любому программисту. Computer Science, расширение кругозора и всё вот это. Сейчас я перетаскиваю кнопки в iOS, а чем захочу заниматься в будущем неизвестно.
Это конец первого семестра, а я отправляюсь на второй) Обещали графы для взрослых. Не уверен, что смогу уделять также много времени и в целом потяну обучение. Я обязательно поделюсь новыми впечатлениями о втором семестре уже этим летом! Но, это не точно.
Надеюсь моя статья была вам полезна, или хотя бы интересна. Или может вы улыбнусь пока читали. Чуть-чуть. Нет…? А я вот ещё схему сделал:
А нет, не конец. Или Второй семестр
Пол года спустя. Сначала я планировал написать новую статью, но материала получилось не очень много. Я не могу рассказывать детали, описание задач. Поэтому…
Зимой перед вторым семестром вышел новый курс по С++. На этот раз жёлтый пояс. Я с удовольствием его прошел и считаю, что он оказался очень полезным для прохождения ревью по одной из задач второго семестра. Нужно было написать сложный алгоритм в рамках уже подготовленного интерфейса на 2000+ строк. Да, это жёстко)
Во время обучения мы изучали различные строковые алгоритмы, контекстно-свободные грамматики и алгоритмы на графах. Семинары были в самом конце семестра. Когда они проходили я уже и не мог вспомнить как решал часть задач) но я не оставил попытки выступлений у доски.
В целом учиться было сложнее чем на первом семестре, но я втянулся и смог решить 17 задач из 20. Сдал все ревью. В этот раз было сложнее оценивать алгоритмы при написании теории в pdf. Часть мне возвращали на доработку и я не всегда сразу мог понять в чем же проблема. В конечном итоге я получил отлично!
На этом всё) Если у вас есть вопросы — пишите. В ближайшее время я планирую искать возможности применения новых знаний на практике. Но, это не точно. Также вскоре я планирую новую экспериментальную статью про алгоритмы, Swift и всё вот это.