Дискретный анализ и теория вероятностей, осень 2017

Описание

Семинары по курсу Дискретный анализ и теория вероятностей в Новосибирске.

Проходят по вторникам в аудитории 416. Первый семинар 19 сентября.

Семинаристы: Пережогин Алексей Львович, Быков Игорь Сергеевич

Контакты
Пережогин Алексей Львович pereal128@yandex.ru
Быков Игорь Сергеевич igor.s.bykov@yandex.ru

Видеолекции по курсу: https://wiki.school.yandex.ru/shad/Videocollections2.0/FirstYear/videoDiscreteAnalysis

Краткое описание

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

Отчётность по курсу и критерии оценки

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

Система оценок по дискретному анализу (ДА), теории вероятностей (ТВ) и статистике: за каждое задание может быть проставлена красная клетка (0 баллов), жёлтая клетка (0,5 балла) или зелёная клетка (1 балл). Границы цветов определяются исходя из распределения оценок после проверки соответствующего домашнего задания. Первое и второе ДЗ будет дано по ДА, третье - по ТВ, а четвёртое - по ТВ и статистике.

Система оценок по линейной алгебре: за две лабораторные суммарно можно получить белую клетку (0 баллов), красную клетку (0,5 балла), жёлтую клетку (1 балл), зелёную клетку (1,5 балла) или синюю клетку (2 балла).

Домашние задания сдаются через страницу центра. Полученную в конце семестра итоговую оценку исправить нельзя.

Итоговые критерии оценки:

отлично - хотя бы 3 балла за ДА, ТВ и статистику + 2 за линейную алгебру или хотя бы 3,5 балла за ДА, ТВ и статистику + 1,5 за линейную алгебру или 4 балла за ДА, ТВ и статистику + 1 балл за линейную алгебру

хорошо - хотя бы 2,5 балла за ДА, ТВ и статистику + 1,5 балла за линейную алгебру или хотя бы 3 балла за ДА, ТВ и статистику + 1 балл за линейную алгебру или 3,5 балла ДА, ТВ и статистику + 0,5 баллов за линейную алгебру

зачёт - хотя бы 3 балла за ДА, ТВ и статистику + 0,5 баллов за линейную алгебру или хотя бы 2,5 баллов за ДА, ТВ и статистику + 1 балл за линейную алгебру (при условии, что сдано хотя бы одно задание по теории вероятностей)

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

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

Правила оформления домашних работ

Хорошее оформление решения ДЗ. Нужно загружать работы на страницу центра. Работы принимаются в формате pdf. Очень удобно, если свои решения Вы набираете в TEXe. Можно сдавать отсканированные решения, но работа должна быть собрана в один pdf файл. Если Вы сдаёте скан работы, написанной от руки, то там всё должно быть написано разборчиво! Помните: Ваши решения внимательно читаются. Если что-то не понятно в решении или не можем разобрать почерка, даётся балльный штраф за задачу. В целом, может быть назначен балловый штраф за плохое (реально минус баллы будут ставиться за совершенно отвратительное оформление решения) оформление или совсем уже неразборчивый почерк.

Штрафы. Работы, сданные после дедлайна или не в том формате, проверяться не будут. Если в нескольких работах задача решена одинаково (одинаковые ошибки или одинаковые нетривиальные шаги и т.д.) задача в этих работах получает метку "подозрение на списывание". Работа, собравшая три таких метки, оценивается красной клеткой без права апелляции. Чтобы этого не произошло рецепт прост: прорешайте последний раз и запишите решение задачи без помощи друзей или литературы. Использование последних возможно только на этапе разбора и нахождения идей решения задач.

Ключевые факты. При проверке решений прежде всего обращается внимание на так называемые "ключевые факты и утверждения." Чаще всего, они возникают в задачах, в которых нужно что-то доказать. Основная идея состоит в том, что то, что я считаю ``ключевым фактом'' в данном утверждении обязательно должно быть доказано аккуратно, иначе последует штраф на баллы. Часто я не могу точно указать, каковы эти ключевые утверждения, так как это будет уж очень серьезной подсказкой для студента. Поэтому действует основное правило: слова "очевидно", "легко понять" и им подобные противопоказано употреблять. Если Вам это очевидно - докажите это! Категория "интуитивно очевидно" вообще мне неизвестна - у всех интуиция разная, мне это не очевидно! В целом, задачи на доказательство какого-то утверждения или в которых нужно будет что-то доказать, будут проверяться особенно придирчиво и аккуратно. Там будет проверяться именно качество и детальность доказательства. Если Ваше решение будет нестрогим, то Вы не получаете полного балла за решение.

Грубейшие ошибки в решениях. За некоторые ошибки в решениях будет ставиться $0$ баллов, даже если остальной ход решения и ответ получается верно, так как подобные ошибки отнесены к категории грубейших. Полный список подобных "смертных грехов" здесь привести довольно сложно, так как он велик. Но на семинарах они все будут обозначены. Особенно много грубейших ошибок можно допустить при решении задач 1-го домашнего задания.

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

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

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

Мини-курс по линейной алгебре

Краткое описание
За три-четыре занятия мы планируем рассказать о двух полезных, но не очень известных широкой публике сюжетах из линейной алгебры: о матричном дифференцировании и о некоторых матричных разложениях. Также речь пойдёт о тензорах и тензорных разложениях.
Сразу предупреждаем, что вам предстоит (достаточно много) использовать язык Python и IPython (Jupyter) ноутбуки. Это не значит, что нужно будет программировать на Питоне, поэтому не расстраивайтесь, если вы не на специализации БД! Тем не менее, в качестве подготовки стоит хотя бы установить Python. Мы настоятельно рекомендуем Anaconda Python, так как этот дистрибутив содержит все необходимые библиотеки и поддержку среды IPython Notebook. Если вы не хотите устанавливать Анаконду, проверьте, что вы можете работать с IPython (Jupyter) ноутбуками и у вас установлены библиотеки numpy, pandas, matplotlib, time, а также последняя версия библиотеки scipy (0.19.1). В Анаконде обновить её можно с помощью команды conda update scipy.

Отчётность по курсу и критерии оценки
Вас ожидают 2 лабораторных работы. Предварительные критерии оценок:
синяя клетка: 32 балла;
зелёная клетка: 25 баллов;
жёлтая клетка: 18 баллов;
красная клетка: 12 баллов.
Они ещё могут измениться!!!

Требования к оформлению работ и возможность сдавать курс
Домашние работы нужно сдавать через сайт CS-центра
Название файла должно иметь вид: Фамилия_Имя_Отделение - лабораторная №
Пожалуйста, не загружайте в систему архивы; если нужно прикрепить несколько файлов - прикрепляйте несколько файлов.

Домашние задания
Условия домашних заданий выкладываются в виде Jupyter ноутбуков. Решения нужно писать прямо в ноутбуке, и его сдавать через сайт центра. Пожалуйста, не удаляйте из ноутбука условия задач или хотя бы оставляйте заголовки. Решения теоретических задач можно присылать в отдельном .pdf файлов (но лучше всё-таки в ноутбуке вместе с остальными задачами: Jupyter отлично поддерживает LATEX).
Чтобы загрузить файл .ipynb в Jupyter, перетащите его мышкой в список файлов и папок на главной странице Jupyter и нажмите Upload. После этого файл появится в списке, и если не него кликнуть, то он откроется в новой вкладке. Чтобы сохранить ноутбук на диск, воспользуйтесь командой File->Download as->IPython Notebook из верхнего меню. Если Jupyter ругается на отсутствие подходящего ядра (kernel), то вы можете указать ядро вручную, выбрав в верхнем меню Kernel->Change Kernel->Python 2 или Kernel->Change Kernel->Python 3 в зависимости от того, какой Питон у вас стоит. Мы будем принимать решения, сделанные как во втором, так и в третьем Питоне. Тем не менее, по умолчанию задания сделаны в синтаксисе третьего Питона.

Программа курса
Лекция 1 (26 октября)
Векторные и матричные нормы. Число обусловленности. LU-разложение. Разложение Холецкого. QR-разложение.
Лекция 2 (2 ноября)
Производные векторов и матриц и производные по векторам и по матрицам.
Лекция 3 (9 ноября)
Матричные разложения с точки зрения анализа данных. Сингулярное разложение. Псевдообратные матрицы.
Лекция 4 (16 ноября)
Тензорные разложения

Видеолекций этого года, к сожалению, не будет. Смотрите лекции и семинары за прошлые года.