Факультетский день 2021-2022 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Занятие 5. 13.01.2022)
(Программирование и анализ данных на Python (часть 1))
Строка 86: Строка 86:
 
Теория:  
 
Теория:  
 
* Понятие o ("о" - маленькое)
 
* Понятие o ("о" - маленькое)
* Асимптотический анализ для n^k, a^n. Сравнение скоростей роста функций.
+
* Асимптотический анализ для n^k и a^n. Сравнение скоростей роста функций.
 
* Оценка сложности экспоненциальных алгоритмов.
 
* Оценка сложности экспоненциальных алгоритмов.
  
Строка 93: Строка 93:
 
=== Занятие 5. 13.01.2022 ===
 
=== Занятие 5. 13.01.2022 ===
 
Теория:
 
Теория:
* Функция логариav
+
* Функция логарифм
 +
* Асимптотический анализ для log(n) и n^k. Сравнение скоростей роста функций.
 
* Бинарный поиск
 
* Бинарный поиск
 
* Инвариант цикла
 
* Инвариант цикла

Версия 12:26, 22 декабря 2021

Факультетский день — особая форма проведения занятий для учеников Лицея ВШЭ и школьников из других школ Распределенного лицея ВШЭ.

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

Общая группа в Telegram

Таблица с оценками

Программирование и анализ данных на Python (общая информация)

Zoom ссылка на лекцию

Идентификатор конференции: 261 255 6227

Код доступа: 939738

Плейлист с лекциями

Расписание

  • Лекция - 10:00 - 11:00
  • Индивидуальные беседы - 11:10 - 14:00

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

Изучается возможность использования языка Python для создания web-приложений на микрофремворке Flask.

Изучаются основы работы с библиотекой поддержки больших многомерных массивов NumPy, пакетом анализа данных Pandas и пакетом машинного обучения Scikit-learn. Также в курсе излагаются базовые вопросы из теории вероятностей и математической статистики, необходимые для понимания алгоритмов машинного обучения.

Конспекты лекций по Python М.С. Густокашина: https://yadi.sk/i/BkcKilJkumcPV

Видео-лекции можно смотреть тут: https://www.coursera.org/learn/python-osnovy-programmirovaniya/home/welcome (платить денег ни в коем случае не нужно)

Преподаватели И. Ю. Самоненко, А. Д. Игнатов.

Учебный ассистент Алексей Носов @alexnosof.

Учебному ассистенту можно:

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

Программирование и анализ данных на Python (часть 1)

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

Если логин и пароль так и не приходят, то заполните форму.

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

Каждый контест открыт в течение 14 дней. Срок устной сдачи решенного контеста - до начала 3 части курса (ориентировочно 14.04.2022).

Система оценки контестов

  1. Контест считается сданным только после устной сдачи преподавателю или ассистенту.
  2. Если в контесте решена как минимум 1 задача, то оценка 3.
  3. Если в контесте решено более половины обычных задач, то оценка 4.
  4. Если в контесте решено все обычные задачи, а также не менее половины задач со звездочкой (*), то ставится оценка 5.
  5. Если в контесте решены не все обычные задачи, но несколько задач со звездочкой (*), то одна задача со звездочкой может быть засчитана на две простых задачи. Далее действует предыдущий пункт.
  6. Независимо от предыдущих пунктов каждая решение хотя бы одной задачи с двумя звездочками (**) из контекста оценивается дополнительной бонусной оценкой 5.
  7. Если на устной сдачи выясняется, что ученик не может объяснить код, т.е. списал задачу, то выставляется оценка 1 за контест.
  8. Если ученик не решал контекст или решил, но не сдал его, то выставляется оценка 2.

Занятие 1. 02.12.2020

Теория: Нет

Контест: https://official.contest.yandex.ru/contest/32664/problems/

Занятие 2. 09.12.2021

Теория:

  • Проблема оценки сложности работы программ
  • Асимптотический анализ: Понятие O ("О" большое)

Контест: https://official.contest.yandex.ru/contest/32667/problems/

Занятие 3. 16.12.2021

Теория:

  • Понятие Θ ("Тета большое")
  • Асимптотический анализ для полиномов.
  • Оценка сложности полиномиальных алгоритмов

Контест: https://official.contest.yandex.ru/contest/32668/problems/

Занятие 4. 24.12.2021

Теория:

  • Понятие o ("о" - маленькое)
  • Асимптотический анализ для n^k и a^n. Сравнение скоростей роста функций.
  • Оценка сложности экспоненциальных алгоритмов.

Контест: https://official.contest.yandex.ru/contest/32669/problems/

Занятие 5. 13.01.2022

Теория:

  • Функция логарифм
  • Асимптотический анализ для log(n) и n^k. Сравнение скоростей роста функций.
  • Бинарный поиск
  • Инвариант цикла
  • Поиск аргумента, при которой возрастающая функция принимает заданное значение.

Контест: https://official.contest.yandex.ru/contest/32670/problems/

Занятие 6. 20.01.2022

Теория:

  • Сортировка выбором, сортировка вставкой
  • Сложность сортировок, инвариант сортировок

Контест: https://official.contest.yandex.ru/contest/32671/problems/

Занятие 7. 27.01.2022

Теория:

  • Нижняя оценка сложности алгоритмов сортировки: n*log(n).

Контест: https://official.contest.yandex.ru/contest/32672/problems/

Занятие 8. 03.02.2022

Теория:

  • Сортировка слиянием.
  • Быстрая сортировка.
  • Оценка времени работы и использованной памяти.

Контест: https://official.contest.yandex.ru/contest/32674/problems/

Занятие 9. 10.02.2022

Теория:

  • Приоритетная очередь. Построение на базе массивов.

Контест: https://official.contest.yandex.ru/contest/32675/problems/

Занятие 10. 17.02.2022

Теория:

  • Структура данных куча. Добавление, изменение значений, изъятие минимального элемента.
  • Сортировка массива при помощи кучи.

Контест: https://official.contest.yandex.ru/contest/32677/problems/

Занятие 11. 24.02.2022

Теория:

  • Связный список. Сравнение с массивом.

Контест: https://official.contest.yandex.ru/contest/32678/problems/

Занятие 12. 24.02.2022

Теория:

  • Хеш-таблица. Разрешение коллизий методом цепочек (списка)

Контест: ...

Программирование и анализ данных на Python (часть 2)

Программирование и анализ данных на Python (часть 3)

Математические основы информатики

Первое занятие: 9.12.2021

Zoom конференция

Идентификатор конференции: 581 195 5118

Код доступа: pE6Umj

Расписание

  • Группа 1 - 11:10 - 12:30
  • Группа 2 - 12:40 - 14:00

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

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

Темы курса

Раздел №1 Комбинаторика

  1. Множества и операции с ними. Геометрия комбинаторных задач;
  2. комбинаторное правило суммы и произведения событий (дерево решений);
  3. общая схема решения комбинаторных задач, урновая схема шаров и урн (случаи различимых и неразличимых объектов);
  4. формула включений-исключений;
  5. перестановки, размещения с повторениями и без повторений;
  6. сочетания, доказательство Эйлера для формулы сочетаний без повторений;
  7. свойства биномиальных коэффициентов;
  8. бином Ньютона;
  9. разбиения на упорядоченные группы;
  10. разбиения на неупорядоченные группы, задача о разбиении натурального числа на сумму натуральных;
  11. принцип отражения и лемма о баллотировке;
  12. задача о разборчивой невесте;
  13. принцип Дирихле;
  14. инверсии, игра в 15.
  15. перечисление цветов, группы симметрии.

Раздел №2 Рекурсия и производящие функции

  1. рекуррентные отношения
  2. конечные разности;
  3. факториальные многочлены;
  4. числа Стирлинга первого рода и числа Стирлинга второго рода;
  5. суммирование разностей;
  6. производящие функции, сущность подхода;
  7. производящие функции, рекуррентные отношения и комбинаторные подсчеты.

Раздел №3 Теория графов

  1. основные определения теории графов;
  2. ориентированные графы
  3. деревья;
  4. пути и циклы Эйлера;
  5. игра “Мгновенное безумие”;
  6. алгебраические свойства графов;
  7. планарные графы;
  8. пути и циклы Гамильтона;
  9. алгоритм поиска кратчайшего пути.

Раздел №4 Логика

  1. исчисление предикатов;
  2. основные положения теории доказательств;
  3. математическая индукция;
  4. сравнения.

Преподаватель А.В. Булычев

Научно-исследовательский семинар

Группа в Telegram: https://t.me/+t_DyBE3eJLs1ZjUy

Преподаватель И. Ю. Самоненко

Консультации: 14:00 - 14:20

Список тем

  1. Декабрь - Мировые ИТ компании
  2. Январь - Языки программирования
  3. Февраль - Интересное приложение
  4. Март - Цифровой стартап
  5. Апрель - История одной железки
  6. Май - Урок информатики
  7. Сентябрь - Задание в Latex
  8. Октябрь - Задание на визуализацию

Темы 1. - 6.

  • Выбрать определенный предмет изучения
  • Подготовить конспект (1-2 страницы)
  • Подготовить презентацию (количество слайдов не регламентируется, но важно, чтобы они хорошо иллюстрировали Ваш доклад)
  • Записать 15-20 минутный доклад (презентация + рассказ)

Задание в Latex

Вам необходимо зарегистрироваться на сайте https://www.overleaf.com/. Допустимо также установить себе на компьютер пакет Latex и некоторый редактор, но это не обязательно, и можно пользоваться web версией.

Необходимо выбрать пять заданий по математике и информатике, например, из ЕГЭ:

  • два задания по алгебре, где требуется решения уравнений;
  • два задания по геометрии, где для решения требуется построение чертежа;
  • одно задание по информатике, где требуется написать код.

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

  • Для заданий по алгебре необходимо пользоваться версткой формул, которые есть в Latex. Если необходимо построить график, то воспользуйтесь какой-то системой построения графиков, например http://yotx.ru/ или аналогичной. Полученные картинки добавьте в Ваш документ.
  • Для построения геометрических чертежей воспользуйтесь системой Geogebra: https://www.geogebra.org. Полученные картинки добавьте в Ваш документ.
  • Для решения задачи по информатике изучите, как правильно оформить код: http://mydebianblog.blogspot.com/2012/12/latex.html

Для каждой задачи запишите ее условие и подробное образцовое решение.

В результате Вам необходимо подготовить и отправить:

  • Архив tex файлом и всеми дополнительными файлами (в overleaf есть кнопка "Download" в списке проектов)
  • Итоговый PDF файл (в overleaf при редактировании есть "Download PDF")

Задание будет оцениваться по количеству задач и качеству оформления текста.

Задание на визуализацию

Вам необходимо выбрать пять каких-то понятий или явлений и построить для них диаграмму связей (mind map, ментальная карта). Что такое диаграммы связей можно почитать, например, тут:

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

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

  • либо подумайте еще, скорее всего еще не до конца разобрались;
  • либо выберете другое понятие или явление.

Вы можете воспользоваться различными online сервисами для построения mind map, например https://www.mindmup.com. Но допускается нарисовать все вручную на бумаге, красиво графически оформив Ваш рисунок.

Архив с 5 изображениями надо отправить в качестве ответа на задание. Оцениваться будет разумность схемы, ее подробность и красота оформления.