Русский
Русский
English
Авторизация
Ip-адрес
Восстановление пароля
Регистрация
Статистика
Реклама

Cs центр

Полезные материалы для разработчика

19.03.2021 12:22:16 | Автор: admin

Существует много полезных инструментов, которые помогают автоматизировать рутинную работу и тем самым облегчить жизнь разработчика.

Выпускнику и преподавателю Computer Science Center, Равилю Галееву, пришла идея собрать такие инструменты и технологии в один курс и познакомить студентов с ними. За пример такого курса были взяты The Missing Semester of Your CS Education от MIT, Software Carpentry и cs50.

В этом посте мы собрали видеолекции курса Практический минимум и материалы к занятиям. Благодарим Равиля за подборку!

Содержание

Введение в Linux

Командная строка Linux

Система контроля версий git

Языки разметки и XML

Регулярные выражения

Взаимодействие с сетью

Протокол HTTP

Контейнеризация

Архитектура приложений

Тестирование приложений

Опасность в приложениях

Билд-системы

Кодировки, даты, локали

Дебаг

Набор в Computer Science Center 2021

Введение в Linux

  • Буквально пара слов о том, что такое ядро

  • Набор исторических фактов (от Unix к Linux)

  • Файловая система

  • Пользователи

  • Файлы

  • Процессы

  • Unix way

Слайды

Статьи

Wikipedia History of Unix

Книги

Видео

Курсы

Командная строка Linux

  • bash как REPL

  • Unix way

  • Шебанг

  • make

Слайды

Статьи

Книги

Ian Miell Learn Bash the Hard Way

Видео

Слайды/Презентации

Bash-скрипты из реального мира

Система контроля версий git

  • git

    • commit

    • branch

    • merge

  • git flow

  • github

Слайды

Статьи

Книги

  • Scott Chacon and Ben Straub Pro Git

Видео

Потренироваться

Языки разметки и XML

  • groff

  • LaTex

  • XML, JSON, YAML

  • Markdown, AsciiDoc

  • GraphViz, PlantUML

Слайды

Статьи

Книги

К. В. Воронцов LATEX в примерах

Видео

Слайды и другие материалы

Markdown cheatsheets

Разное

Регулярные выражения

  • Регулярки

  • grep

  • sed

  • awk

Слайды

Статьи

Видео

Слайды и другие материалы

Взаимодействие с сетью

  • Разбираемся как работает посылка пакетов

  • Рассматриваем простейшие утилиты работы с сетью

  • Знакомимся с DNS, CDN, VPN и другими словами на три буквы

  • Пишем сервер на сокетах

Слайды

Материалы

Протокол HTTP

  • HTTP

  • REST

Слайды

Статьи

Видео

Разное

Контейнеризация

  • chroot

  • Docker

  • Docker compose

Слайды

Статьи

Видео

Курсы

Разное

Архитектура приложений

  • ООП

  • Паттерны

  • Многослойная архитектура

Слайды

Статьи

Книги

Курсы

Видео

Тестирование приложений

  • Тестирование

  • Логгирование

Слайды 1

Слайды 2

Статьи

Видео

Опасность в приложениях

  • Хеширование, контрольные суммы

  • Авторизация vs Аутентификация; JWT

  • Обмен ключами Диффи-Хеллман

  • RSA

  • TLS

  • Двухфакторная аутентификация

Слайды

Статьи

Видео

Книги

Билд-системы

  • от make к TravisCI

  • dockerhub

Слайды

Статьи

Видео

Разное

Anatomy of a Continuous Integration and Delivery (CICD) Pipeline

Кодировки, даты, локали

Разбираемся, почему /dev/random печатает краказябры

Слайды

Статьи

Видео

Дебаг

  • Исключения

  • Дебаг

Слайды

Статьи

Книги

Видео

Курсы

Кирилл Кринкин Основы программирования для Linux

Разное

Делитесь в комментариях своими рекомендациями материалов, которые пригодились вам.

Набор в Computer Science Center 2021

Помимо лекций и материалов студентам CS центра на курсе доступны домашние задания. Если вы хотите проходить ещё больше курсов по разным направлениям, приходите поступать.

CS центр это вечерние курсы по математике и программированию. Занятия проходят в Санкт-Петербурге и в Новосибирске. Жители других городов могут поступить на обучение в удалённом формате.

Чтобы поступить:

заполните анкету на сайте до 10 апреля,

решите задания онлайн-теста до 11 апреля,

участвуйте в онлайн-экзамене в конце апреля-начале мая,

пройдите собеседование в мае-июне.

Для тех, кто успешно справится со вступительными испытаниями, занятия начнутся в сентябре. Будьте готовы тратить на учёбу хотя бы 15 часов в неделю в течение двух или трёх лет. Если вы увлечены компьютерными науками или программированием, хотите развиваться в этих областях, любите учиться, то осваивать курсы и работать над проектами будет интересно и полезно.

Задать вопросы про набор можно в телеграм канале или по почте info@compscicenter.ru.

Подробнее..
Категории: Программирование , *nix , Linux , Командная строка , Git , Карьера в it-индустрии , Учебный процесс в it , Блог компании образовательные проекты jetbrains , Cs центр , Bash , Http , Xml , Сеть , Дебаг , Регулярки

PM-школа от CS центра итоги первого года в онлайне глазами выпускников

14.06.2021 20:18:14 | Автор: admin

Два года назад Computer Science Center провел экспериментальный запуск курса по управлению продуктами, о результатах которого мы рассказывали ранее. Эксперимент удался, и в 2020-21 учебном году прошла уже полноценная годовая программа повышения квалификации с поправкой на новые идеи и вынужденный онлайн-формат. Сегодня выпускники нашей программы поделились своими историями: почему они решили развиваться в продакт-менеджменте, как совмещали учебу и работу и с какими результатами вышли с курса.

До 20 июня открыт набор на третий поток обучения по направлению Product Management с преподавателями и наставниками из ведущих мировых IT-компаний. Подробнее о школе смотрите в записи Дня открытых дверей онлайн и на нашем сайте.

До и После: зачем вы изначально подавали заявку на конкурс и что получилось в результате?

Год назад я решила сменить сферу деятельности и попробовать сделать продукт в той предметной области, в которой работала уже много лет. У меня было много опыта, понимание проблем пользователей, идей по развитию продукта, но очень не хватало уверенности в своих силах хотелось научиться принимать решения не только на основе чутья, но и подкреплять их теорией и овладеть инструментами продакта.

Я дважды пытался запустить стартап и дважды спотыкался о собственную некомпетентность. Профессия Product Manager предполагает, что ты знаешь как из пункта А привести продукт в пункт Б. Когда я увидел, что на продакта будут учить в Computer Science Center, я сразу подал заявку: все мои знакомые, которые проходили курсы в CS центре, говорили о лучшем опыте обучения в своей жизни.

Меня не обманули. Я учился весь год, прошел путь от скачивания Figma до презентации прототипа, от робкого опроса в чатике до профессионального кастдева со скриптом. Преподаватели мотивировали, давали много домашки и жестко оценивали. В спикерах не было случайных людей: мы общались с фаундерами, продактами, маркетологами и дизайнерами. Не слушали, а на каждом занятии решали конкретные прикладные кейсы.

Будь у меня возможность, я бы прошел эту школу еще раз. Зная организаторов, могу гарантировать, что курс станет еще лучше.

Я хотел изменить карьерную траекторию это очень значимое для меня решение. Раньше я работал в сфере ядерной энергетики: занимался как инженерными задачами, так и развитием бизнеса. Понимал, что хочу качественных изменений: новых знаний и практики для старта в IT. Обучение в школе по управлению продуктами от CS центра было для меня этой возможностью. С одной стороны, что-то близкое и знакомое (менеджмент, инженерия и бизнес-анализ), с другой новая сфера инженерии (цифровые продукты).

Результат сейчас обучение завершено. Закрыв одну дверь, я открыл две новые: Business Аnalysis и Product Management. Сейчас я работаю в IT-компании и двигаюсь по треку управляющего цифровыми проектами, потому что мне нужен базовый опыт. После перейду в управление продуктами. Рассчитываю совершить карьерный маневр в течение этого года.

Сначала был конкурс: первое впечатление от знакомства и советы бывалых будущим абитуриентам.

Во время отбора советую выложиться по полной, особенно при записи видео. Постарайтесь посмотреть и оценить, чем вас привлекает работа продакта, или что интересного и непонятного в этой профессии.

Собеседование с организаторами это челлендж, к которому невозможно подготовиться! Нужно не бояться, быстро думать, выдавать много идей, не мяться и не мямлить. Команда организаторов не звери: кусаться не будут, но точно попытаются испытать вас на прочность, так как работа продакта это всегда вызов.

Самое сложное в отборе ответить на три довольно глобальных вопроса в двухминутном видео. Съемка этого видео заняла у меня пару часов: хотелось сделать что-то задорное, но информативное о себе и моем опыте. В итоге все получилось: благодаря видео я попала на собеседование, а после него и на курс. Если у вас совсем нет знаний о работе IT-продуктов, для подготовки к интервью рекомендую послушать лекции из Школы менеджеров Яндекса.

Во время собеседования кураторы и преподаватели школы хотели оценить мой подход к созданию продуктов, софт-скилы и представления о том, как должен создаваться продукт. Поскольку курс рассчитан на начинающих, интервьюеров скорее интересовал ход рассуждения, а не наличие правильных ответов. От этого разговора у меня осталось очень приятное впечатление. Было интересно порассуждать над вопросами и проблемами из кейсов.

Совет: если вам кажется что вы не знаете правильного ответа не уходите в себя, а начинайте рассуждать вслух. Диалог с интервьюерами поможет вам избежать эффекта лестницы и, возможно, даже найти отличное решение уже в ходе интервью.

В процессе: как справлялись с учебной нагрузкой и какие изменения происходили с вами в течение учебного года?

На задания уходило довольно много времени и сил, особенно в начале. Когда слишком много неопределенности, есть страх пойти не тем путем и оказаться в ситуации, что все сделанное нужно выбросить и начать сначала. В общем, как и в жизни, когда начинаешь делать продукт. В этом смысле курс стал отличным тренажером по прокачке не только знаний, но и собственного упорства, гибкости, умении довести начатое до результата.

Заметила, что в целом стала мыслить по-другому: мозг начал очень быстро генерировать идеи и так же быстро их критиковать и свои, и чужие. Очень полезным оказался навык посмотреть на любую идею с рациональной точки зрения и отойти от парадигмы я придумал крутую штуку, сейчас я завоюю мир. Я окончательно убедилась, что хочу заниматься продакт-менеджментом дальше. А еще за этот год сформировалась привычка все время учиться: теперь не могу остановиться и просто посмотреть в свободное время сериал, все время уходит на прокачку каких-то компетенций.

Учебы было очень много. Во-первых, тут нет лекций это оставьте для YouTube. Каждое занятие решение практической задачи с однокурсниками в ограниченное время, потом фидбэк от преподавателя. В первом семестре надо пройти путь от гипотезы до запуска продукта в составе команды тут можно работать бесконечно. Пару раз ловил себя в 6 утра, зарывшись в прототипирование или в оценку рынка. Самое важное в школе, что вы будете учиться работать в команде. Не в компании друзей, а с незнакомыми людьми короче говоря, все будет пугающе близко к действительности.

Во втором семестре будут нагружать не меньше: каждую неделю преподаватели задают массивные домашки, цель которых развить вас в сбалансированного продакт-менеджера. Мне понравились домашки по маркетингу, дизайну и архитектурным требованиям.

По окончании курса я получил три оффера на позицию продакт-менеджера. В конце учебного года пришло осознание, что я только в начале пути. Надо погружаться, углублять экспертизу во всех областях. Но места, где можно понять, что именно надо знать, в каком объеме, о чем мечтать и как этого достичь, лучше этого курса вы не найдете.

Ключевой вопрос во время учёбы грамотное планирование и организация. Первый семестр был непростым работа в удаленном режиме, в распределенной команде. Каждую неделю новые задачи, причем совершенно нетипичные для меня. Я справился с этим темпом благодаря тому, что мы в команде помогали друг другу, и той самой командной ответственности. Всем было тяжело совмещать учебу с работой, однако вечерний формат и удаленка помогли сделать это приятным событием. Я очень горд результатом первого семестра.

Второй семестр был менее динамичным, однако тут настало время прохождения индивидуальной практики в компаниях. Мне повезло попасть к хорошему ментору Матвею Брыксину, Product Lead в Arrival. Нагрузка была умеренной, в этот раз я успевал делать задачки хорошо, а не в режиме стартапера, которому нужно было вчера. Работая для корпорации, я получил совершенно другой опыт. Мне было интересно заниматься реальной проблемой бизнеса.

Атмосфера на курсе: ощущения от взаимодействия с организаторами, преподавателями и друг другом.

Когда я рефлексирую на тему школы, то слово, которое приходит на ум это живой. Люди на курсе живые и очень разные, как преподаватели/кураторы, так и студенты. Благодаря этому в рамках курса создается очень благоприятная и дружелюбная атмосфера получения новых знаний. Все готовы делиться друг с другом опытом, информацией, фидбэком. Даже сама программа школы специально подстраивается под поток.

Мне было комфортно общаться с организаторами и преподавателями, я быстро почувствовал, что все на курсе Свои. Сконнектиться с ребятами было чуть сложнее: нас много, общения друг с другом меньше, и только онлайн. В основном мы взаимодействовали на воркшопах, во время практических заданий, или уже в команде при работе над проектом.

Уже к концу первого семестра у нас сложилось настоящее дружеское общение с напарницей по проекту поддерживающее и внимательное. И продолжается до сих пор, за рамками школы, чему я отдельно рад! К концу второго семестра появилось чувство, что узнал многих ребят. Отдельно понравилось, как каждый из студентов приносил в обсуждение свой бэкграунд, а с ним часто и новый угол взгляда на вопрос.

Несмотря на то, что курс требовал много времени и усилий, общий настрой помогал не терять интерес. Преподаватели на лекциях заряжали энтузиазмом и любовью к своему делу. Мотивировала поддержка организаторов, кураторов и студентов. Мы вместе генерировали идеи, проводили друг с другом интервью для проверки гипотез, делились контактами и опытом.

Что дальше: что вы будете делать с полученными знаниями, опытом и связями после выпуска?

Весь полученный багаж знаний и связей я буду максимально применять в карьерном росте. Искать возможность приложить свои знания на текущем месте работы. Стараться смотреть на принимаемые решения в компании новыми глазами. Думать, как я могу открывать свои проекты.

Моя позиция в компании не изменилась, я все также отвечаю за клиентский опыт в одном из сервисов Яндекса. Однако теперь я строю процессы в поддержке с учетом знаний о продукте, это оказалось супер полезно. В июне я немного передохну от учебы и буду искать работу продактом или брать больше продуктовых задач в рамках клиентской поддержки.

Знания, которые я получил в процессе обучения, помимо собственно понимания, какие процессы и фреймворки существуют в области создания продуктов, значительно расширили мой профессиональный и общий кругозор. Хоть я и не планирую в ближайшее время переходить на позицию продакт-менеджера, многое я смогу применить в роли Lead-engineer. Большая часть вопросов относительно ожиданий бизнеса и прогнозирования хода проекта стали разрешимы с меньшим объемом коммуникаций. Да и возможность видеть что-либо на большем уровне абстракции само по себе прекрасно и интересно.

Курс был однозначно полезен, и я рад, что смог дойти до конца и получить такие ценные знания!

Новые идеи для работы и жизни

Курс и общение в рамках него помогли мне взглянуть на уже имеющиеся знания под новым, продуктовым углом, что невероятно круто и полезно. Неважно, какая тема рассматривалась, занятия помогают заново переосмыслить ее, даже если тебе казалось, что это я уже знаю. А еще общение и обмен знаниями на курсе помогают подзарядиться внутренней мотивацией брать и пробовать.

Мне понравилась вроде бы простая мысль, что вся задача сделать хороший интерфейс вертится вокруг учитывания особенностей человека от строения тела до специфики восприятия и паттернов мышления. И как гармонично вокруг этого наслаивается всё остальное в теории дизайна.

У меня бэкграунд разработчика, и для меня оказалось важным обсудить ощущения продакта от сделанной работы, особенно на определенном этапе развития продукта. Например, у программистов после написания кода результат работы видно наглядно. А продакт при проработке идей часто ходит кругами, отбрасывая большую часть неработающего. И хорошо, если в сито останется немного золота, ведь на коротком интервале иногда просто ничего не срабатывает. В связи с этим мне понравился взгляд ментора практики Татьяны Васильевой на часть работы продакта, как на своеобразное разбрасывание семян идей в свою и чужие головы, с последующим бережным наблюдением за их прорастанием и метаморфозами, и своевременным подхватыванием удачных плодов, иногда падающих с веток коллективного разума.

Пришло понимание, что чтобы делать хорошие продукты, недостаточно знать разные фреймворки и инструменты и уметь работать с людьми. Не менее важны вера в продукт и команду, умение не сдаваться и не терять мотивацию, когда что-то не получается или твоя идея себя не оправдывает.

Здесь и сейчас мир меняется слишком быстро, чтобы работали готовые рецепты. Поэтому приходите учиться думать! Думать опережая изменения, которые с космической скоростью происходят в реальности. Видеть мир так, чтобы ни один аспект не ускользнул от вашего мышления. Формировать сеть профессиональных контактов, чтобы решать сверхсложные задачи. Создавать продукты, которые создают будущее.

Заявки принимаются до 20 июня на https://pmcsc.ru/ ;)

Подробнее..
Категории: Управление проектами , Карьера в it-индустрии , Учебный процесс в it , Product management , Блог компании образовательные проекты jetbrains , Cs центр , Школа , Повышение квалификации

Жадные гипотезы в задаче о кратчайшей надстроке

18.12.2020 16:04:56 | Автор: admin
В задаче о надстроке по входному набору строк требуется найти кратчайшую строку, которая содержит каждую из них в качестве подстроки. Данная задача возникает в разных приложениях, например, в сборке генома или сжатии данных. Эта задача NP-трудная, поэтому рассчитывать на эффективный алгоритм поиска точного решения не приходится.

Максим Николаев аспирант ПОМИ РАН, преподаватель Computer Science Center и СПбГУ, учитель математики в лицее 533 в Санкт-Петербурге. В 2019 году он окончил CS центр по направлению Современная информатика. В статье ниже Максим рассказывает о своей исследовательской работе во время обучения по поиску приближенных решений задачи о надстроке.



Жадная гипотеза


Как и в других NP-трудных задачах, в задаче о надстроке представляют интерес и активно изучаются приближенные алгоритмы, которые достаточно быстро находят достаточно точное решение. Наилучший известный на сегодняшний день полиномиальный алгоритм находит надстроку не более, чем в $2\frac{11}{23}$ раза более длинную, чем точное решение.

В то же время уже более 30 лет остается нерешённой так называемая жадная гипотеза, которая утверждает, что элементарный жадный алгоритм выбери две строки с максимальным пересечением и слей их; продолжай так делать, пока не останется одна строка является 2-приближенным.

Более подробно о задаче и возникающих в ней гипотезах можно узнать в замечательной открытой лекции CS центра. Далее будет изложена краткая выжимка из неё и описание моих результатов.

Иерархический граф и надстроки


В попытке подобраться к решению жадной гипотезы и к разработке более качественных приближенных алгоритмов группой Александра Куликова был разработан теоретико-графовый подход, который позволяет в удобной форме изучать структуру пересечений исходных строк друг с другом. Для этого вводится так называемый иерархический граф, в котором вершинами являются исходные строки и всевозможные их подстроки, а ориентированные ребра идут из префикса каждой строки в эту строку и из строки в ее суффикс. Под префиксом и суффиксом строки понимаются строки, которые получаются при выкидывании последней и первой её буквы соответственно. Вершины графа удобно расположить по уровням в зависимости от длины соответствующих строк, поэтому граф и называется иерархическим. На рисунке ниже показан иерархический граф для исходного набора строк {aaa, cae, aec, eee}, которые изображаются в прямоугольниках. Пустая строка обозначается через $\varepsilon$.


Где же здесь надстроки? Надстрокам в этом графе соответствуют циклы, проходящие через $\varepsilon$ и все исходные вершины. По каждому такому циклу можно восстановить надстроку, и наоборот. Например, на рисунке ниже отмечен цикл, соответствующей надстроке aaaecaeee. В этой надстроке исходные строки встречаются в порядке aaa $\rightarrow$ aec $\rightarrow$ cae $\rightarrow$ eee, и именно в таком порядке их обходит упомянутый цикл.


Нетрудно показать, что длина надстроки всегда равна количеству идущих вверх стрелок в соответствующем цикле (в примере их 9). Это значит, что задача поиска кратчайшей надстроки превращается в задачу поиска кратчайшего цикла в иерархическом графе.

Greedy Hierarchical Algorithm и Collapsing Algorithm


Естественно, такая замечательная структура как иерархический граф так и просит, чтобы на её основе разработали интересные алгоритмы. Моя задача состояла в изучении двух таких алгоритмов.

Первый из них, Greedy Hierarchical Algorithm (GHA), является, по-видимому, самым простым способом построить цикл, проходящий через исходные вершины и который бы мог претендовать на хорошее приближение точного решения. Как следует из названия, он является жадным и кратко может быть описан так: пройдем по уровням графа сверху вниз, а внутри уровня по всем вершинам в лексикографическом порядке; для каждой из вершин, во-первых, обеспечим равную входящую и исходящую степень (чтобы решение было циклом) за счет добавления подходящего количества ребер между текущим уровнем и более низким, а во-вторых, если вершина является исходной или если она является последней в лексикографическом порядке вершиной некоторой уже построенной циклической компоненты (ребра которой лежат выше данного уровня), то мы выпускаем из неё два ребра в её префикс и суффикс. Работа алгоритма для нашего датасета из предыдущих примеров отражена на рисунке ниже. Нетрудно видеть, что на второй картинке ребра из aa и ee были выпущены, чтобы обеспечить связь исходных строк aaa и eee с $\varepsilon$, а ребра из ca и ec чтобы сбалансировать соответствующие вершины.


Видно, что алгоритм старается добавлять как можно меньше ребер он делает это только для обеспечения цикличности и связности необходимых условий для того, чтобы цикл соответствовал некоторой надстроке.

Второй алгоритм в некотором смысле противоположен первому. Он называется Collapsing Algorithm (CA), и если GHA стартует с пустого графа и добавляет ребра только в случае необходимости, то CA стартует с некоторого решения и пытается убрать из него лишние ребра. Убирание лишних ребер происходит следующим образом: алгоритм движется по графу сверху вниз, на каждом уровне обходя вершины в лексикографическом порядке; если для некоторой вершины $\mathtt{v}$ на в цикле имеется галка $\mathtt{pref(v)} \rightarrow \mathtt{v} \rightarrow \mathtt{suff(v)}$, то алгоритм старается её обвалить (поэтому и Collapsing), заменив её на галку $\mathtt{pref(v)} \rightarrow \mathtt{pref(suff(v))} \rightarrow \mathtt{suff(v)}$, но только если это не нарушит связность цикла. Если же $\mathtt{v}$ находится на первом уровне, то эта галка просто удаляется. Таким образом алгоритм старается сбросить все лишние пары ребер вниз, после чего удалить. Пример работы CA на удвоенном оптимальном решении (удвоенность нужна, чтобы были лишние ребра) можно увидеть на рисунке ниже.


Разные гипотезы


Моей задачей было исследование описанных алгоритмов с прицелом на доказательство или опровержение какой-нибудь из гипотез, описанных ниже.

Гипотеза Collapsing Conjecture возьмите любое решение, удвойте в нем ребра и подайте на вход CA. Полученный результат не зависит от изначального решения!

Если эта гипотеза верна, то у нас появляется очень простой 2-приближенный алгоритм: возьмите любое решение (например, тривиальное, которое получается конкатенацией всех исходных строк), удвойте в нем ребра и обвалите. В итоге получится то же самое, как если бы вы удвоили и обвалили оптимальное решение. Но если так, то полученный результат не более чем в два раза длиннее оптимального.

Гипотеза Greedy Hierarchical Conjecture граф, получающийся после обвала любого удвоенного решения, это в точности граф, который строит GHA!

Данная гипотеза была проверена на очень большом количестве случайных и неслучайных наборов исходных строк, но контрпример найти так и не удалось. В частности, для приведенных выше примеров, иллюстрирующих работу GHA и CA, гипотеза верна. Из этой гипотезы сразу следует, что GHA является 2-приближенным.

Гипотеза Weak Greedy Hierarchical Conjecture GHA является 2-приближенным.

Даже если предыдущие две гипотезы неверны, то GHA все равно может быть 2-приближенным.

Моя работа


Первое, что меня заинтересовало: как связан GHA с обычным жадным алгоритмом? На некоторых примерах GHA строит более короткое решение, но всегда ли это происходит? Можем ли мы показать, что GHA не хуже жадного? Как в терминах иерархического графа описать жадный алгоритм? Как в иерархическом графе увидеть момент склейки двух строк в одну?

В процессе работы над всеми этими вопросами я выяснил, что GHA на самом деле является частным случаем обычного жадного алгоритма! Дело в том, что жадный алгоритм является недетерминированным: в его описании не оговаривается, что происходит, если есть несколько пар строк с максимальным пересечением. Предполагается, что алгоритм может выбрать произвольную пару, а значит, вообще говоря, даже на одном и том же датасете он может выдавать различные решения. GHA по своей сути является некоторой детерминацией алгоритма в его определении заложено, в каком именно порядке будут объединяться пары строк, таким образом по данному набору исходных строк всегда строится одно и то же решение. Данное свойство означает, что из жадной гипотезы следует 2-приближенность GHA, поэтому, строго говоря, доказать Weak Greedy Hierarchical Conjecture должно быть проще, чем жадную гипотезу.

Также оказалось, что эта детерминация не лучше исходного алгоритма существуют примеры, на которых GHA работает хуже, чем некоторая другая детерминация жадного.

Следующий этап моего исследования был посвящен более подробному изучению работы GHA на датасете, в котором длина всех строк ограничена некоторой константой. Если эта константа 2, то GHA является точным, а сама задача, стало быть, из класса P, а начиная с максимальной длины 3 задача становится NP-полной и для этого случая уже было неясно, насколько приближенным является GHA.

Для случая строк длины не больше 3 я показал, что GHA является 1.5-приближенным и эта оценка является асимптотически точной, т. е. для любого $\delta > 0$ можно привести датасет, на котором GHA построит решение в $1.5 \delta$ раз более длинное, чем точное.

К сожалению, для случая строк длины 4 или более ничего придумать не удалось, и я решил переключиться на исследование остальных гипотез.

Во-первых, после работы над строками длины не больше 3 я решил попробовать разобраться с Greedy Hierarchical Conjecture для этого случая, и мне это удалось. Причем был доказан даже более сильный результат: для того, чтобы все обвалилось, в GHA не нужно удваивать всё решение достаточно добавить к решению произвольное покрытие исходных вершин циклами (которые уже не обязаны образовывать один связный цикл).

Во-вторых, я выяснил, что если в общем случае к решению, полученному GHA, приклеить произвольный набор циклов (к примеру, подходит само решение GHA), а потом все обвалить, то снова получится GHA. Это означает, что из Collapsing Conjecture следует Greedy Hierarchical Conjecture. Так как обратное следствие очевидно, то выходит, что эти две гипотезы равносильны.

Конференция APPROX 2019


Все полученные результаты, кроме 1.5-приближенности, были включены в статью Collapsing Superstring Conjecture, которая была принята на конференцию APPROX 2019 и опубликована в ее трудах. Эта одна из ведущих конференций по приближенным алгоритмам, что свидетельствует об актуальности темы и интересе к ней у научного сообщества, несмотря на то, что ни одна из гипотез доказана или опровергнута не была.

Дальнейшая работа


После выпуска из центра я все еще периодически возвращаюсь к этой задаче. Ни по какой из гипотез на момент осени 2020 так ничего определенного не известно, но всё равно появляется более глубокое понимание проблем, которые препятствуют их решению. В случае, если эта задача покажется интересной, можно обращаться к Александру Куликову за актуальной информацией и подробными комментариями.
Подробнее..
Категории: Алгоритмы , Блог компании образовательные проекты jetbrains , Cs центр

Автоматическая генерация сообщений к коммитам

31.05.2021 20:20:52 | Автор: admin
Привет! Меня зовут Александра Елисеева, я студентка Computer Science Center. В рамках практики в осеннем семестре 2020 года я участвовала в проекте BERT for Source Code под руководством Тимофея Брыксина и Ярослава Соколова из JetBrains Research. Я исследовала решение задачи автоматической генерации сообщений к коммитам с помощью языковой модели BERT. Что получилось, а над чем еще предстоит поработать, расскажу в этом посте.



О проекте


В области обработки языков программирования есть много интересных задач, автоматическое решение которых может пригодиться для создания удобных инструментов для разработчиков.

Исходный код программ во многом отличается от текстов на естественном языке, но его тоже можно воспринимать как последовательность токенов и использовать аналогичные методы. Например, в области обработки естественного языка активно применяется языковая модель BERT. Процесс её обучения предполагает две стадии: предобучение на большом наборе неразмеченных данных и дообучение под конкретные задачи на более маленьких размеченных датасетах. Такой подход позволяет многие задачи решать с очень хорошим качеством.

Недавние работы (1, 2, 3) показали, что если обучить модель BERT на большом датасете программного кода, то она и в этой области неплохо справляется с несколькими задачами (среди них, например, локализация и устранение неправильно использованных переменных и генерация комментариев к методам).

Проект направлен на исследование применения BERT для других задач, связанных с исходным кодом. В частности, мы сосредоточились на задаче автоматической генерации сообщений к коммитам.

О задаче


Почему мы выбрали эту задачу?

Во-первых, системы контроля версий используются при разработке многих проектов, поэтому инструмент для автоматического решения этой задачи может быть актуален для широкого круга разработчиков.

Во-вторых, мы предположили, что применение BERT для этой задачи может привести к хорошим результатам. Это обусловлено несколькими причинами:

  • в существующих работах (4, 5, 6) данные собираются из открытых источников и требуют серьёзной фильтрации, поэтому примеров для обучения остаётся немного. Здесь может пригодиться способность BERT дообучаться на небольших датасетах;
  • state-of-the-art результат на момент работы над проектом был у модели архитектуры Transformer, которая достаточно специфичным способом предобучена на небольшом датасете (6). Нам интересно было сравнить его с моделью на основе BERT, которая предобучена по-другому, но на гораздо большем количестве данных.

За семестр мне нужно было сделать следующее:

  • изучить предметную область;
  • найти датасет и выбрать представление входных данных;
  • разработать пайплайн для обучения и оценки качества;
  • провести эксперименты.

Данные


Существует несколько открытых датасетов для этой задачи, я выбрала наиболее отфильтрованный из них (5).

Датасет собирался из топ-1000 открытых GitHub репозиториев на языке Java. После фильтрации из исходных миллионов примеров осталось около 30 тысяч.

Сами примеры представляют собой пары из вывода команды git diff и соответствующего короткого сообщения на английском языке. Выглядит это как-то так:



И изменения, и сообщения в датасете короткие не более 100 и 30 токенов соответственно.

В большинстве существующих работ, исследующих задачу автоматической генерации сообщений к коммитам, на вход моделям подается последовательность токенов из git diff.

Встречается и другая идея: явно выделить две последовательности, до изменений и после, и выровнять их с помощью классического алгоритма для подсчета редакционного расстояния. Таким образом измененные токены всегда находятся на одинаковых позициях.

В идеале нам хотелось попробовать несколько подходов и понять, насколько они влияют на качество решения этой задачи. На начальном этапе я использовала достаточно простой: на вход модели подавались две последовательности, до изменений и после, но без какого-либо выравнивания.

BERT для sequence-to-sequence задач


И входные, и выходные данные для задачи автоматической генерации сообщений к коммитам представляют собой последовательности, длина которых может отличаться.

Для решения подобных задач обычно используют архитектуру энкодер-декодер, состоящую из двух компонент:

  • модель-энкодер на основе входной последовательности строит векторное представление,
  • модель-декодер на основе векторного представления генерирует выходную последовательность.

Модель BERT основана на энкодере из архитектуры Transformer и сама по себе для такой задачи не подходит. Возможно несколько вариантов, чтобы получить полноценную sequence-to-sequence модель, самый простой - использовать с ней какой-либо декодер. Такой подход с декодером из архитектуры Transformer хорошо себя показал, например, для задачи нейронного машинного перевода (7).

Пайплайн


Для проведения экспериментов необходим был код для обучения и оценки качества подобной sequence-to-sequence модели.

Для работы с моделью BERT я использовала библиотеку HuggingFaces Transformers, а для реализации в целом фреймворк PyTorch.

Так как в начале у меня было мало опыта с PyTorch, я во многом опиралась на существующие примеры для sequence-to-sequence моделей других архитектур, постепенно адаптируя под специфику моей задачи. С таким подходом, к сожалению, получилось большое количество кода плохого качества.

В какой-то момент было решено заняться рефакторингом, практически переписав пайплайн. Структурировать код помогла библиотека PyTorch Lightning, позволяющая собрать всю основную логику модели в одном модуле и во многом автоматизировать её.

Эксперименты


В ходе экспериментов нам хотелось понять, позволяет ли использование предобученной на программном коде модели BERT улучшить state-of-the-art результат в этой области.

Среди обученных на коде моделей BERT нам подошла только CodeBERT (1), так как только у неё в примерах для обучения присутствовал язык программирования Java. Сначала, используя CodeBERT в качестве энкодера, я попробовала декодеры разных архитектур:

  1. Я предполагала, что с этим вариантом удастся быстро получить какой-нибудь базовый результат. GRU не так часто используют с архитектурой Transformer, поэтому было не до конца понятно, чего ожидать.
    В итоге какого-либо разумного качества получить не удалось даже после подбора нескольких влияющих на процесс обучения гиперпараметров.
  2. Я попробовала второй вариант, используя для этого предобученную на английском языке GPT-2 (8) модель на основе декодера из архитектуры Transformer, часто применяемую для задач генерации, а также её более маленькую версию distilGPT-2 (9).

На дальнейшие эксперименты времени в осеннем семестре не хватило, я продолжила их уже зимой. Мы рассмотрели несколько других способов представления входных данных: попробовали выравнивать последовательности до изменений и после, а еще просто подавать git diff.

Основные результаты экспериментов выглядят следующим образом:





Подводя итоги


В целом предположение о пользе применения CodeBERT к данной задаче не подтвердилось, во всех случаях обучаемая с нуля модель Transformer показала качество выше. Лучшим методом в этой области остаётся модель CoreGen6: это тоже Transformer, но дополнительно предобученный с использованием предложенной авторами целевой функции.

Для решения этой задачи можно рассмотреть еще много идей: например, попробовать представление данных на основе абстрактных синтаксических деревьев, которое часто применяется при работе с программным кодом (10, 11), попробовать другие предобученные модели или провести какое-нибудь специфичное для этой области предобучение, если есть необходимые ресурсы. Мы же в весеннем семестре сосредоточились на более практическом применении полученных результатов и занимались автодополнением сообщений к коммитам. Об этом расскажу во второй части :)

В заключение хочу сказать, что участвовать в проекте было действительно интересно, я погрузилась в новую для себя предметную область и многому научилась за это время. Работа над проектом была очень здорово организована, за что большое спасибо моим руководителям.

Спасибо за внимание!

Источники


  1. Feng, Zhangyin, et al. Codebert: A pre-trained model for programming and natural languages. 2020
  2. Buratti, Luca, et al. Exploring Software Naturalness through Neural Language Models. 2020
  3. Kanade, Aditya, et al. Learning and Evaluating Contextual Embedding of Source Code. 2020
  4. Jiang, Siyuan, Ameer Armaly, and Collin McMillan. Automatically generating commit messages from diffs using neural machine translation. 2017
  5. Liu, Zhongxin, et al. Neural-machine-translation-based commit message generation: how far are we?. 2018
  6. Nie, Lun Yiu, et al. CoreGen: Contextualized Code Representation Learning for Commit Message Generation. 2021
  7. Rothe, Sascha, Shashi Narayan, and Aliaksei Severyn. Leveraging pre-trained checkpoints for sequence generation tasks. 2020
  8. Radford, Alec, et al. Language models are unsupervised multitask learners. 2019
  9. Sanh, Victor, et al. DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter. 2019
  10. Yin, Pengcheng, et al. Learning to represent edits. 2018
  11. Kim, Seohyun, et al. Code prediction by feeding trees to transformers. 2021
Подробнее..
Категории: Машинное обучение , Учебный процесс в it , Блог компании образовательные проекты jetbrains , Cs центр , Практика , Коммит

Эффективный поиск функциональных зависимостей в базах данных

22.06.2020 16:10:43 | Автор: admin
Поиск функциональных зависимостей в данных применяется в разных направлениях анализа данных: управление базами данных, очистка данных, ревёрс-инжиниринг баз данных и эксплорация данных. Про сами зависимости мы уже публиковали статью Анастасии Бирилло и Никиты Боброва. В этот раз Анастасия выпускница Computer Science Center этого года делится развитием этой работы в рамках НИР, которую она защитила в центре.



Выбор задачи


Во время обучения в CS центре я начала углублённо изучать базы данных, а именно, поиск функциональных и разностных зависимостей. Эта тема была связана с темой моей курсовой в университете, так что во время работы над курсовой я начала читать статьи про различные зависимости в базах данных. Я написала обзор этой области одну из первых своих статей на английском языке и подала её на конференцию SEIM-2017. Я была очень рада, когда узнала, что её всё же приняли, и решила углубиться в тему. Сама концепция не новая её начали применять еще в 90х годах, но и сейчас она находит применение во многих областях.

Во втором семестре обучения в центре я начала научно-исследовательский проект по улучшению алгоритмов поиска функциональных зависимостей. Работала над ним вместе с аспирантом СПбГУ Никитой Бобровым на базе JetBrains Research.

Вычислительная трудоёмкость поиска функциональных зависимостей


Основная проблема вычислительная трудоёмкость. Число возможных минимальных и нетривиальных зависимостеи ограничено сверху значением $\frac{N}{2} \cdot 2^N$, где $N$ число атрибутов таблицы. Время работы алгоритмов зависит не только от количества атрибутов, но и от количества строк. В 90-х годах алгоритмы по поиску ФЗ на обычном настольном ПК могли обрабатывать наборы данных, содержащие до 20 атрибутов и десятки тысяч строк, до нескольких часов. Современные алгоритмы, работающие на многоядерных процессорах, обнаруживают зависимости для наборов данных, состоящих из сотен атрибутов (до 200) и сотен тысяч строк, примерно за то же время. Тем не менее этого недостаточно: такое время неприемлемо для большинства реальных приложении. Поэтому мы разрабатывали подходы для ускорения существующих алгоритмов.

Схемы кэширования для пересечения партиций


В первой части работы мы разработали схемы кэширования для класса алгоритмов, использующих метод пересечения партиций. Партиция для атрибута представляет собои набор списков, где каждыи список содержит номера строк с одинаковыми значениями для данного атрибута. Каждый такой список называется кластер. Многие современные алгоритмы используют партиции для определения, удерживается зависимость или нет, а именно придерживаются леммы: Зависимость $AB \rightarrow C$ удерживается, если $|\pi(AB)| = |\pi(AB \cup C)|$. Здесь $\pi$ обозначается партиция и используется понятие размер партиции количество кластеров в ней. Алгоритмы, использующие партиции, при нарушении зависимости добавляют дополнительные атрибуты в левую часть зависимости, после чего пересчитывают её, производя операцию пересечения партиций. Такая операция в статьях называется специализацией. Но мы заметили, что партиции для зависимостей, которые будут удержаны лишь после нескольких раундов специализации, могут быть активно переиспользованы, что может существенно сократить время работы алгоритмов, так как операция пересечения является дорогой.

Поэтому мы предложили эвристику, основанную на Энтропии Шеннона и неопределённости Джинни, а также нашей метрике, которую мы назвали Обратная Энтропия. Она является незначительной модификацией Энтропии Шеннона и растёт по мере того, как растёт уникальность набора данных. Предложенная эвристика выглядит следующим образом:

$ if(PLIUniqueness(C) \leq \\medianUniqueness \cdot (1 + mod_1(C) + mod_2(C))~then~cache$



Здесь $PLIUniqueness(C)$ степень уникальности недавно вычисленнои партиции $C$, а $medianUniqueness$ является медианои степенеи уникальности для отдельных атрибутов. В качестве метрики уникальности были опробованы все три метрики, описанные выше. Также можно заметить, что в эвристике присутствуют два модификатора. Первый указывает, насколько близка текущая партиция к первичному ключу и позволяет в большеи степени кэшировать те партиции, которые далеки от потенциального ключа. Второй модификатор позволяет отслеживать занятость кэша и тем самым стимулирует добавление большего количества партиции в кэш при наличии свободного места. Успешное решение этой задачи позволило ускорить алгоритм PYRO на 10-40% процентов в зависимости от датасета. Стоит отметить, что алгоритм PYRO является наиболее успешным в этой области.

На рисунке ниже можно увидеть результаты применения предложенной эвристики по сравнению с базовым подходом по кэшированию, основанном на подбрасывании монетки. Ось X логарифмическая.

image

Альтернативный способ хранения партиций


Затем мы предложили альтернативный способ хранения партиций. Партиции представляют собои набор кластеров, в каждом из которых хранятся номера кортежеи с одинаковыми значениями по определённым атрибутам. Эти кластеры могут содержать длинные последовательности номеров кортежеи, например, если в таблице данные упорядочены. Поэтому мы предложили схему сжатия для хранения партиции, а именно интервальное хранение значении в кластерах партиции:

$$display$$\pi(X) = \{\{\underbrace{1, 2, 3, 4, 5}_{Первый~интервал}, \underbrace{7, 8}_{Второй_интервал}, 10\}\}\\ \downarrow{Сжатие}\\ \pi(X) = \{\{\underbrace{$, 1, 5}_{Первый~интервал}, \underbrace{7, 8}_{Второй_интервал}, 10\}\}$$display$$



Этот метод смог сократить потребление памяти во время работы алгоритма TANE от 1 до 25%. Алгоритм TANE классический алгоритм по поиску ФЗ, он использует партиции в ходе своей работы. В рамках практики был выбран именно алгоритм TANE, так как внедрить в него интервальное хранение было значительно проще, чем, например, в PYRO, чтобы оценить, работает ли предлагаемый подход. Полученные результаты представлены на рисунке ниже. Ось X логарифмическая.

image

Конференция ADBIS-2019



По результатам исследования в сентябре 2019 года я выступила со статьёй Smart Caching for Efficient Functional Dependency Discovery на конференции 23rd European Conference on Advances in Databases and Information Systems (ADBIS-2019). Во время выступления работу отметил Bernhard Thalheim, значимый человек в области баз данных. Результаты исследований легли в основу моей диссертации в магистратуре мат-меха СПбГУ, в ходе которой оба предложенных подхода (кэширование и сжатие) были внедрены в оба алгоритма: TANE и PYRO. При этом результаты показали, что предложенные подходы являются универсальными, так как на обоих алгоритмах при обоих подходах наблюдалось значительное сокращение потребляемой памяти, а также значительное сокращение времени работы алгоритмов.
Подробнее..
Категории: Блог компании образовательные проекты jetbrains , Cs центр

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru