Wiki - Факультет компьютерных наук - Вклад [ru]

Theory of Computing 2018 2019

2018-09-26T12:23:10Z

Storandrew:

== General Information ==

[http://www.mi.ras.ru/~podolskii/files/computability1819/grading.pdf Grading]

Send your home assignments '''only in pdf''' format to the teacher assistant (Andrey Storozhenko) by email (''storozhenkoaa [at] yandex.ru'') with the following subject: "'''[Computing, Name Surname, HWx]'''". You can also submit them in person before the deadline.

[https://docs.google.com/spreadsheets/d/1SnGKycG4m42VtKTq3Yb6rF5e0756GboLjIBO3GthpmE/edit?usp=sharing Homework results]

== Dates and Deadlines ==

Homework 1, deadline: 2 Oktober, before the lecture.

== Course Materials ==

{| class="wikitable"
|-
! Date !! Summary !! Problem list
|-
|| 4/9 || Time and space hierarchy theorems (see also Sipser Section 9.1) || [http://www.mi.ras.ru/~podolskii/files/computability1819/prob_1.pdf Problem list 1 ]
|-
|| 11/9 || Complexity class NP. Examples. Inclusions between P, NP and EXP. Non-deterministic TMs. Another definition of NP. Polynomial reductions, their properties. NP-hardness and NP-completeness, their properties. || [http://www.mi.ras.ru/~podolskii/files/computability1819/prob_2.pdf Problem list 2 ]
|-
|| 18/9 || NP-completeness: Circuit-SAT, 3-SAT, NAE-3-SAT, IND-SET || [https://www.dropbox.com/s/8nisqdaia715ib0/prob_3.pdf?dl=0 Problem list 3]
|-
|| 25/9 || NP-completeness: Subset-SUM, 3COLORING || [https://www.dropbox.com/s/h5or8izfv7m5pn8/prob_4.pdf?dl=0 Problem list 4]

|}

During the first module, we follow Sipser's book [https://theswissbay.ch/pdf/Book/Introduction%20to%20the%20theory%20of%20computation_third%20edition%20-%20Michael%20Sipser.pdf Introduction to the theory of computation], chapters 7-9.

== Office hours ==

{| class="wikitable"
|-
! !! Person !! Monday !! Tuesday !! Wednesday !! Thursday !! Friday
|-
| <center>1</center> || Vladimir Podolskii, room 621 || || 18:00–19:00 || 16:40–18:00 || ||
|-
| <center>2</center> || Bruno Bauwens, room 620 || 16:40–19:00 || 15:00–18:00 || || ||
|}

Theory of Computing 2018 2019

2018-09-26T11:06:25Z

Storandrew:

== General Information ==

[http://www.mi.ras.ru/~podolskii/files/computability1819/grading.pdf Grading]

Send your home assignments '''only in pdf''' format to the teacher assistant (Andrey Storozhenko) by email (''storozhenkoaa [at] yandex.ru'') with the following subject: "'''[Computing, Name Surname, HWx]'''". You can also submit them in person before the deadline.

== Dates and Deadlines ==

Homework 1, deadline: 2 Oktober, before the lecture.

== Course Materials ==

{| class="wikitable"
|-
! Date !! Summary !! Problem list
|-
|| 4/9 || Time and space hierarchy theorems (see also Sipser Section 9.1) || [http://www.mi.ras.ru/~podolskii/files/computability1819/prob_1.pdf Problem list 1 ]
|-
|| 11/9 || Complexity class NP. Examples. Inclusions between P, NP and EXP. Non-deterministic TMs. Another definition of NP. Polynomial reductions, their properties. NP-hardness and NP-completeness, their properties. || [http://www.mi.ras.ru/~podolskii/files/computability1819/prob_2.pdf Problem list 2 ]
|-
|| 18/9 || NP-completeness: Circuit-SAT, 3-SAT, NAE-3-SAT, IND-SET || [https://www.dropbox.com/s/8nisqdaia715ib0/prob_3.pdf?dl=0 Problem list 3]
|-
|| 25/9 || NP-completeness: Subset-SUM, 3COLORING || [https://www.dropbox.com/s/h5or8izfv7m5pn8/prob_4.pdf?dl=0 Problem list 4]

|}

During the first module, we follow Sipser's book [https://theswissbay.ch/pdf/Book/Introduction%20to%20the%20theory%20of%20computation_third%20edition%20-%20Michael%20Sipser.pdf Introduction to the theory of computation], chapters 7-9.

== Office hours ==

{| class="wikitable"
|-
! !! Person !! Monday !! Tuesday !! Wednesday !! Thursday !! Friday
|-
| <center>1</center> || Vladimir Podolskii, room 621 || || 18:00–19:00 || 16:40–18:00 || ||
|-
| <center>2</center> || Bruno Bauwens, room 620 || 16:40–19:00 || 15:00–18:00 || || ||
|}

Theory of Computing 2018 2019

2018-09-26T11:04:28Z

Storandrew: /* General Information */

== General Information ==

[http://www.mi.ras.ru/~podolskii/files/computability1819/grading.pdf Grading]

Send your home assignments to the teacher assistant (Andrey Storozhenko) by email (storozhenkoaa [at] yandex.ru) with the following subject: "[Computing, Name Surname, HWx]". You can also submit them in person before the deadline.

== Dates and Deadlines ==

Homework 1, deadline: 2 Oktober, before the lecture.

== Course Materials ==

{| class="wikitable"
|-
! Date !! Summary !! Problem list
|-
|| 4/9 || Time and space hierarchy theorems (see also Sipser Section 9.1) || [http://www.mi.ras.ru/~podolskii/files/computability1819/prob_1.pdf Problem list 1 ]
|-
|| 11/9 || Complexity class NP. Examples. Inclusions between P, NP and EXP. Non-deterministic TMs. Another definition of NP. Polynomial reductions, their properties. NP-hardness and NP-completeness, their properties. || [http://www.mi.ras.ru/~podolskii/files/computability1819/prob_2.pdf Problem list 2 ]
|-
|| 18/9 || NP-completeness: Circuit-SAT, 3-SAT, NAE-3-SAT, IND-SET || [https://www.dropbox.com/s/8nisqdaia715ib0/prob_3.pdf?dl=0 Problem list 3]
|-
|| 25/9 || NP-completeness: Subset-SUM, 3COLORING || [https://www.dropbox.com/s/h5or8izfv7m5pn8/prob_4.pdf?dl=0 Problem list 4]

|}

During the first module, we follow Sipser's book [https://theswissbay.ch/pdf/Book/Introduction%20to%20the%20theory%20of%20computation_third%20edition%20-%20Michael%20Sipser.pdf Introduction to the theory of computation], chapters 7-9.

== Office hours ==

{| class="wikitable"
|-
! !! Person !! Monday !! Tuesday !! Wednesday !! Thursday !! Friday
|-
| <center>1</center> || Vladimir Podolskii, room 621 || || 18:00–19:00 || 16:40–18:00 || ||
|-
| <center>2</center> || Bruno Bauwens, room 620 || 16:40–19:00 || 15:00–18:00 || || ||
|}

Theory of Computing 2018 2019

2018-09-26T09:40:48Z

Storandrew:

== General Information ==

[http://www.mi.ras.ru/~podolskii/files/computability1819/grading.pdf Grading]

Send your home assignment to the teacher assistant (Andrey Storozhenko) by email (storozhenkoaa [at] yandex.ru) or submit them in person before the deadline.

== Dates and Deadlines ==

Homework 1, deadline: 2 Oktober, before the lecture.

== Course Materials ==

{| class="wikitable"
|-
! Date !! Summary !! Problem list
|-
|| 4/9 || Time and space hierarchy theorems (see also Sipser Section 9.1) || [http://www.mi.ras.ru/~podolskii/files/computability1819/prob_1.pdf Problem list 1 ]
|-
|| 11/9 || Complexity class NP. Examples. Inclusions between P, NP and EXP. Non-deterministic TMs. Another definition of NP. Polynomial reductions, their properties. NP-hardness and NP-completeness, their properties. || [http://www.mi.ras.ru/~podolskii/files/computability1819/prob_2.pdf Problem list 2 ]
|-
|| 18/9 || NP-completeness: Circuit-SAT, 3-SAT, NAE-3-SAT, IND-SET || [https://www.dropbox.com/s/8nisqdaia715ib0/prob_3.pdf?dl=0 Problem list 3]
|-
|| 25/9 || NP-completeness: Subset-SUM, 3COLORING || [https://www.dropbox.com/s/h5or8izfv7m5pn8/prob_4.pdf?dl=0 Problem list 4]

|}

During the first module, we follow Sipser's book [https://theswissbay.ch/pdf/Book/Introduction%20to%20the%20theory%20of%20computation_third%20edition%20-%20Michael%20Sipser.pdf Introduction to the theory of computation], chapters 7-9.

== Office hours ==

{| class="wikitable"
|-
! !! Person !! Monday !! Tuesday !! Wednesday !! Thursday !! Friday
|-
| <center>1</center> || Vladimir Podolskii, room 621 || || 18:00–19:00 || 16:40–18:00 || ||
|-
| <center>2</center> || Bruno Bauwens, room 620 || 16:40–19:00 || 15:00–18:00 || || ||
|}

Рендзю (семинар)

2017-01-28T13:10:11Z

Storandrew:

Описание [[Рендзю (проект)|проекта]], последний [[Рендзю_(семинар)#.D0.A1.D0.B5.D0.BC.D0.B8.D0.BD.D0.B0.D1.80.D1.8B|семинар]].

==Правила игры ==
* '''Ментор:''' [[Участник:Simagin.denis|Симагин Денис]].
* '''Место:''' офис Яндекса ([https://maps.yandex.ru/213/moscow/?ll=37.590150%2C55.734065&z=18&l=stv%2Csta&panorama%5Bpoint%5D=37.589416%2C55.733747&panorama%5Bdirection%5D=40.412258%2C-11.910596&panorama%5Bspan%5D=130.000000%2C52.209677 место встречи])
* '''Время:''' c 19:00, каждую среду.

Общение с ментором вне занятий приветствуется. Можно задавать вопросы, в том числе философские. Но перед тем, как написать, попробуйте спросить это у [https://ya.ru Яндекса]. Также не обижайтесь, если в ответ вам пришла ссылка на документацию или какую-то статью.

===Ключевые точки===
Сверху нам спущены ключевые точки выполнения проекта. Для нас они скорее явлются формальными, тем не менее мы должны их соблюдать.
# '''12-17 декабря''' - все включились в работу
# '''20-25 марта''' - реализован объем работ, необходимый для зачета
# '''30 мая - 3 июня''' - окончание проектной работы, вы готовы, как пионеры.
# '''начало июня''' - конкурс проектов.

===Правило 2Х===
У вас есть право на одну ошибку. Следующая - я отказываюсь с вами работать.

===Репозитории===
Студенты хранят свой код в следующих репозиториях
{| class="wikitable"
|-
| Ментор || https://github.com/dasimagin/renju
|-
| Харламов || https://github.com/gamers5a/renju
|-
| Сопов || https://github.com/PreFX48/renju
|-
| Vodim || https://github.com/EterniusVGM/Renju
|-
| Yuriy || https://github.com/yurriy/renju
|-
| Storozh || https://github.com/storandrew/Renju
|}

===Разбор статьи===
В рамках проекта студент должен разобрать интересную для него статью и доложить ее на общем семинаре.

{| class="wikitable"
|-
! Студент !! Статья !! Дата
|-
| Харламов || http://web.stanford.edu/~takapoui/linear_bandits.pdf || -
|-
| Сопов || https://papers.nips.cc/paper/6068-learning-feed-forward-one-shot-learners.pdf || -
|-
| Гринберг || https://arxiv.org/pdf/1611.01626.pdf || -
|-
| Баранов || https://arxiv.org/pdf/1611.01224.pdf || -
|-
| Стороженко || https://arxiv.org/pdf/1511.06581v3.pdf || -
|}

===Лабораторные===
Лабораторные проводятся для практического закрепления материала. Их выполнение учитывается в итоговой оценке.

# Результатом работы является jupyter notebook, где сохранен вывод вашего кода, графики и т.п. А так же его импорт в формат .py. Для автоматизации процесса можно настроить jupyter.
# Когда сроки выполнения лабораторной завершены, вы выкладываете ее на ревью, создавая соответствующее задание и запрос на объединение ветки с мастером (не забудьте добавить проверяющего).
# Ваш коллега проводит ревью кода и может оставлять замечания, как в виде комментариев к заданию, так и в файле .py. Оно предполагает проверку стиля и правильность кода, а также конструктивные замечания по производительности. Однако не стремитесь сразу оптимизировать код. Добейтесь лучше того, чтобы все работало правильно.
# Когда ревью завершено, влейтесь в мастер и закройте задание.

===Результаты===
Текущие результаты можно найти [https://docs.google.com/spreadsheets/d/1VAaIoKGOYkMYKxYMPjHs_TsYabjHo27jA4fiQg_R344/edit?usp=sharing здесь]. Оценка складывается из нескольких частей:
# Работа на семинаре
# Доклад статьи
# Итоговое качество игры

==Семинары==

===S01.02, S08.02, 15.02, 22.02, 01.03===
Разбор статьи
===S25.01===
# Поговорили на тему [https://en.wikipedia.org/wiki/Multi-armed_bandit многоруких бандитов].
# Начали осваивать [https://en.wikipedia.org/wiki/Reinforcement_learning reinforcment learning].

Полезная книга может быть найдена [https://webdocs.cs.ualberta.ca/~sutton/book/bookdraft2016sep.pdf здесь].

===L4===

{| class="wikitable"
|-
! Ревьюер !! Разработчик !! Оценка
|-
| Сопов || Харламов|| -
|-
| Гринберг || Сопов || -
|-
| Баранов || Гринберг || -
|-
| Стороженко || Баранов || -
|-
| Харламов || Стороженко || -
|}

Появилась очередная лабораторная работа [https://github.com/dasimagin/renju/blob/master/labs/L4%20-%20Reinforcement%20learning.ipynb L4], сроки '''...'''.

===S18.01===
В связи с болезнью ментора занятие отменено.

===H11.01===
Произвели разбор L3. Описание модели победителя можно найти [здесь], а baseline доступен [https://github.com/dasimagin/renju/blob/master/labs/L3%20-%20Baseline.ipynb здесь].

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

===S14.12===
Начали разбирать нашу [https://storage.googleapis.com/deepmind-media/alphago/AlphaGoNaturePaper.pdf статью]. Есть пара источников на русском:
* [https://ru.wikipedia.org/wiki/AlphaGo Статья] на wikipedia
* [https://habrahabr.ru/post/279071/ Статья] на хабре

===H11.12===
Занятие было посвящено выполнению второй лабораторной. Интересный ноутбук скоро появится [здесь].

===S08.12===
'''1. Известные архитектуры сверточных сетей'''
* [https://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf Alexnet]
* [https://arxiv.org/pdf/1409.1556.pdf VGG net]
* [https://arxiv.org/pdf/1409.4842v1.pdf GoogLeNet]
* [https://arxiv.org/pdf/1512.03385.pdf ResNet]
'''2. Поговорили:'''
* На что активируются нейроны в зависимости от слоя
* Генерация 'похожих картинок'
* Послойное обучение сети
* Переобучение или дообучение уже готовой сети
'''3. Изучили примеры для библиотеки Keras'''
* [https://github.com/fchollet/keras/blob/master/examples/mnist_mlp.py Полносвязанная сеть]
* [https://github.com/fchollet/keras/blob/master/examples/mnist_cnn.py Сверточная сеть ]
* [https://github.com/fchollet/keras/blob/master/examples/mnist_transfer_cnn.py Переобучение] сверточной сети

===L3===

{| class="wikitable"
|-
! Студент !! CPU !! RAM !! GPU
|-
| Пример || 6 core, 3,5 GHz || 64GB || NVIDIA TITAN X
|-
| Харламов || 4 core, 3,6 GHz || 16GB || NVIDIA GTX 960m 2GB
|-
| Сопов || 4 core, 2,7 GHz || 8GB || NVIDIA GTX 940m
|-
| Гринберг || 4 core, 3,6 GHz || 16 GB || NVIDIA GTX 1070 8GB
|-
| Баранов || 4 core, 3,5GHz || 8GB || NVIDIA GTX 960m 2GB
|-
| Стороженко || 6 core 3.0 GHz || 16 GB || NVIDIA GTX 1060 6GB
|}

Победить в [https://inclass.kaggle.com/c/ch-ch конкурсе] классификации, срок 3 января, 23:59.

Для этого вам понадобится
* Установить [https://www.tensorflow.org Tensorflow]
* Установить [https://keras.io Keras]
* Запастись терпением

===S01.12===
'''1. Полносвязанные сети:'''
* Подсчитаны производные для [https://en.wikipedia.org/wiki/Backpropagation Backpropagation], обсуждены тонкости реализации.
* Различные виды нелинейности: [https://en.wikipedia.org/wiki/Rectifier_(neural_networks) ReLu], [https://arxiv.org/pdf/1502.01852v1.pdf PReLu], [https://en.wikipedia.org/wiki/Sigmoid_function Sigmoid].
* Обучение сетей при помощи [https://en.wikipedia.org/wiki/Autoencoder Autoencoder].

'''2. Сверточные сети:'''
* Cтруктура [https://en.wikipedia.org/wiki/Convolutional_neural_network CNN].
* Затронуты: [https://en.wikipedia.org/wiki/Convolution Convolution], [https://en.wikipedia.org/wiki/Convolutional_neural_network#Pooling_layer Pooling].
* Влияние различных ядер свертки на структуру сети.
* [https://en.wikipedia.org/wiki/Convolutional_neural_network#Choosing_hyperparameters Feature maps].
* Разобрана архитектура [https://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf Alexnet].
* Сочетание из Convolutional и Dense слоев.

===S24.11===
'''1. Регуляризация:'''
* Разобрали L1 и L2 регуляризаторы, можно найти [https://en.wikipedia.org/wiki/Regularization_(mathematics) здесь].
* Используйте простые классификаторы
* Раняя остановка (смотрим качество на отложенном множестве)
* Добавление шума
* Комбинирование классификаторов

'''2. Полносвязанные сети:'''
* Множественная классификация и [https://en.wikipedia.org/wiki/Softmax_function softmax].
* Метод [http://www.machinelearning.ru/wiki/images/0/0f/karpinskaya-2010.pdf обратного распространения ошибки], проблема при обучении.
* Инициализация весов: и [http://jmlr.org/proceedings/papers/v9/glorot10a/glorot10a.pdf xavier] и другие [https://arxiv.org/pdf/1502.01852v1.pdf вариации].
* Кратко о [https://en.wikipedia.org/wiki/Convolutional_neural_network#Dropout dropout].

===L2===
Задание можно найти [https://github.com/dasimagin/renju/blob/master/labs/L2%20-%20Nets.ipynb здесь], срок 23:59 11 декабря.

===S02.11===
# [https://en.wikipedia.org/wiki/Feature_(machine_learning) Признаки] и какие они бывают. Об отборе признаков, кратко [https://habrahabr.ru/post/264915/ тут]. Может помочь на конкурсе.
# Задача [http://www.machinelearning.ru/wiki/index.php?title=Линейный_классификатор бинарной классификации].
# [http://www.machinelearning.ru/wiki/index.php?title=Метод_градиентного_спуска Градиентный спуск].
# [http://www.machinelearning.ru/wiki/index.php?title=Метод_стохастического_градиента Стохастический градиентный спуск]. На английской [https://en.wikipedia.org/wiki/Stochastic_gradient_descent вике] больше интересной информации.

'''Для дополнительного чтения:'''
# [https://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf Что полезно знать о машинном обучении].
# [https://en.wikipedia.org/wiki/Feature_(machine_learning) Английская вика про признаки]
# [http://www.jmlr.org/papers/volume3/guyon03a/guyon03a.pdf Отбор признаков].
# Мощная теоретическая работа про [https://mipt.ru/upload/medialibrary/d7e/41-91.pdf стохастический градиентный спуск].

===L1===

{| class="wikitable"
|-
! Ревьюер !! Разработчик !! Оценка
|-
|Харламов || Сопов || 9
|-
| Сопов || Гринберг || 10
|-
| Гринберг || Баранов || 8
|-
| Баранов || Стороженко || 10
|-
| Стороженко || Харламов || 8
|}

Для [https://github.com/dasimagin/renju/blob/master/labs/L1%20-%20Gradient%20descent%20and%20linear%20models.ipynb первой] лабораторной работы вам потребуется:
# Настроить себе [https://pip.pypa.io/en/stable/ pip] для Python3
# Освоить [http://jupyter.org Jupyter notebook]
# Установить пакеты [http://www.scipy.org scipy]: numpy, scipy, matplotlib