= Комбинаторные конструкции в теоретической информатике (3-ий курс ТИ) 2026 год =

Лекции проходят по понедельникам на четвертой паре в ауд. S328, семинары по понедельникам на пятой паре в S330.
Первая лекция - 19 января, первый семинар 19 января.

Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com телеграм: https://t.me/nikolay_vereshchagin

Семинарист: Сергей Корнеев, SubjectNameHere4444@yandex.ru телеграм: https://t.me/SubjectNameHere4444

Группа в Телеграм: https://t.me/+KV_zm22fF8FjMGYy

[https://docs.google.com/spreadsheets/d/1Yy_D3LUCmW0EOhpoX-VpZuzpdCIvmZBT/edit?usp=sharing&ouid=114867075298197812676&rtpof=true&sd=true Результаты]

==Новости==

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

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

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

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

Итоговая оценка складывается из оценок за домашние задания, за колллоквиум, за экзамен
и за дополнительные сложные задачи.
Она вычисляется так, чтобы усердный студент, хорошо усвоивший курс, но не сделавший ни одной дополнительной задачи, получил 8 баллов.
Оценки за домашние задания, за колллоквиум и за экзамен ставятся по десятибалльной системе. Дополнительные задачи входят в домашние задания и имеют специальные пометки, их будет всего четыре, по одной в каждом ДЗ. За каждую решеннную дополнительную задачу к итоговой оценке прибавляется 0.5 балла, при условии, что эта оценка равна 8.
Точнее, итоговая оценка выставляется по следующуй формуле
MIN{8, 0.2*(оценка за домашние задания)+ 0.4*(оценка за коллоквиум)+ 0.4*(оценка за экзамен)} + (оценка за дополнительные задачи, если этот минимум равен 8).

=== Домашние задания===
В течение двух модулей студентам будет дано 4 домашних задания.
Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается не менее 14 дней, решение ДЗ нужно сдавать семинаристу. Сдача домашних заданий после их срока невозможна.

===Коллоквиум и письменный экзамен===
Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе.

Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен. На пересдачу также могут прийти те, кто в итоге получил менее 4 баллов. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.

===Правила округления===
В вычислениях текущие оценки и промежуточные величины не округляются. Результат
вычисляется точно и округляется (арифметически) только в момент выставления итоговой оценки.

====Коллоквиум====

Коллоквиум состоится 15 июня дистанционно.
[https://www.dropbox.com/scl/fi/nyf1pk04js8op1zux02yw/colloq.pdf?rlkey=69whwpzuq3e7ngo172phq6t6f&st=q4nwam8w&dl=0 Программа коллоквиума.]

Для сдачи коллоквиума нужно записаться в следующую
[https://docs.google.com/spreadsheets/d/1vbVNb8XlrtPNlRnGlTI8zU-09uHQVIBtb0hgCJnqHtA/edit?usp=sharing таблицу], в которой указано время получения билета. В билете будет два теоретических вопроса,  один про экспандеры, другой про коды, и вопрос на определение или формулировку теоремы.  На подготовку ответа у Вас будет ровно час, во время которого можно пользоваться любыми бумажными источниками.  Коллоквиум Вы  сдаёте устно одному из преподавателей.  Для уточнения оценки  преподаватель может задавать дополнительные вопросы на знание определений и  основных фактов курса.  Оценка за коллоквиум формируется следующим образом.  Полный ответ на каждый из теоретических  вопросов оценивается в 4 балла, вопрос на определение --- в два балла.
Во всех теоретических вопросах, содержащих формулировки теорем,  надо знать и рассказать и их   доказательства.

====Экзамен====

Экзамен (письменный) состоится 20 июня с 11 до 12:30 в ауд. R308. Можно пользоваться любыми бумажными материалами.

Студенты на дистанционном обучении решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Ссылка на подключение

Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.  Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.  Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен.

Ссылки на экзаменационные варианты прошлых лет для подготовки к экзамену:

https://www.dropbox.com/scl/fi/yj9ut0k03pn5r59yifxh8/250925.pdf?rlkey=w9zwf95sct1vt9y5egb1jci4k&st=vnmo6sxi&dl=0

https://www.dropbox.com/scl/fi/nvy2aors2otwsn2pieqk4/250620.pdf?rlkey=cosb5ibfaafgy9332ewphk3hj&st=wmppvudb&dl=0

https://www.dropbox.com/scl/fi/cue6a9g5agi69fu61lcjo/240622.pdf?rlkey=95ujffdi17igi1ql5w6drdl8t&st=rm1fv8jv&dl=0

https://www.dropbox.com/s/120kgt6iyuzc1uz/exam_25_06_2021solutions.pdf?dl=0

https://www.dropbox.com/scl/fi/tc49r8k36rxh27p0aah5q/exam-25-06-2021solutions.pdf?rlkey=upby9o043egsjgozpunngor87&dl=0

https://www.dropbox.com/scl/fi/kn3mu8yhqb6t7v0knwvz7/exam.pdf?rlkey=rb95jnijdwk0i46h5tytmtdpi&dl=0

https://www.dropbox.com/scl/fi/kn3mu8yhqb6t7v0knwvz7/200622.pdf?rlkey=rb95jnijdwk0i46h5tytmtdpi&dl=0

https://www.dropbox.com/scl/fi/54oaqjov2rizkneeejze1/exam180123_solutions.pdf?rlkey=4leeqvihcxnk209wa32xwu00w&dl=0

https://www.dropbox.com/scl/fi/cksdtbh2o4ylaej3zzr0y/exam-09-2020.pdf?rlkey=e6dnuxu0om1g2iqa1bekhvb3u&dl=0

https://www.dropbox.com/scl/fi/r8q6v9javnv4f3kzz1ecf/exam-21-06-2023.pdf?rlkey=oza81gx71ibnf6u63w8flhbq4&dl=0

https://www.dropbox.com/scl/fi/q9wgdgbfc40dkertqdtxz/exam-24-06-2022-solutions.pdf?rlkey=0kx3umwc1fm5stly0vzrzkn4t&dl=0

https://www.dropbox.com/scl/fi/10tteeb1vl9jns6iyirq0/exam_25_06_2021solutions.pdf?rlkey=9ia99m8ckzppkl6v8kzc06k5a&dl=0

https://www.dropbox.com/scl/fi/cue6a9g5agi69fu61lcjo/exam-2024-06-22.pdf?rlkey=95ujffdi17igi1ql5w6drdl8t&dl=0

https://www.dropbox.com/scl/fi/54oaqjov2rizkneeejze1/exam180123_solutions.pdf?rlkey=4leeqvihcxnk209wa32xwu00w&dl=0

====Пересдачи====

Первая пересдача состоится ... . Пересдача комиссии ... .

Пересдать можно только письменный экзамен (ранее полученная оценка при этом аннулируется).

==Примерные сроки контрольных мероприятий==

Первое домашнее задание будет выложено 27 февраля, срок сдачи 13 марта.

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

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

Четвёртое домашнее будет задание выложено 31 мая, срок сдачи 14 июня.

==Домашние задания ==

[https://www.dropbox.com/scl/fi/14a1hzpq89vfy00gh8v19/hw1-3.pdf?rlkey=m0a3h4qasgya27h1pbvqt09l3&st=sdhxo859&dl=0 Домашнее задание 1] Срок сдачи: 13 марта.

[https://www.dropbox.com/scl/fi/j2gcpth7zsehbbpemjz5y/hw2.pdf?rlkey=lv0js7vz8bf0yx4wcqski9v2j&st=rsn2cg50&dl=0 Домашнее задание 2] Срок сдачи: 3 апреля.

[https://www.dropbox.com/scl/fi/5gws1e9dkuhqusc87ifeb/hw3.pdf?rlkey=go8fd6ojhnls0ut6hvir2uk60&st=10eu7quu&dl=0 Домашнее задание 3] Срок сдачи: 10 мая.

[https://www.dropbox.com/scl/fi/v6u9yrsvqxdau9orn46g3/hw4.pdf?rlkey=rpnd6wxj5z7fbg7ie84p835fa&st=pgnmivwt&dl=0 Домашнее задание 4] Срок сдачи: 14 июня.

==Результаты ==
[https://docs.google.com/spreadsheets/d/1Yy_D3LUCmW0EOhpoX-VpZuzpdCIvmZBT/edit?usp=sharing&ouid=114867075298197812676&rtpof=true&sd=true Оценки за домашние задания, коллоквиум и экзамен]

==Прочитанные лекции==
====Лекция 1 (19 января). ====
Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).

====Лекция 2 (26 января). ====
Реберное расширение и его связь с вершинным расширением.

Матрица графа и ее собственные числа.
Максимальное по абсолютной величине собственное число регулярного графа. От спектрального экспандера к комбинаторному.
Лемма о перемешивании.

====Лекция 3 (2 февраля). ====
Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа.
Нижняя оценка 2sqrt(d-1)-o(1) на второе собственное число d-регулярного графа.

Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами (начало).
====Лекция 4 (9 февраля). ====
Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами (завершение).
Степень графа и тензорное произведение графов и их собственные числа.
Зигзаг-произведение графов. Видеозапись лекции: https://www.youtube.com/watch?v=0sKCkrV0jeY

====Лекция 5 (16 февраля). ====
Первая оценка собственных чисел зигзаг произведения.
Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.

====Лекция 6 (25 февраля). ====
Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.

Вторая оценка для спектрального зазора зигзаг-произведения.

====Лекция 7 (2 марта). ====
Второе собственное число связного недвудольного графа.
Алгоритм Рейнгольда.

====Лекция 9 (11 марта). ====
Экспандер Маргулиса.

====Лекция 8 (16 марта). ====
Экспандер Маргулиса (окончание доказательства).
Применение экспандеров для дерандомизации (без дополнительной случайности).

====Лекция 9 (23 марта). ====
Применение экспандеров для дерандомизации (случайное блуждание).

Двудольные экспандеры: определение и вероятностное доказательство существования.

====Лекция 10 (6 апреля). ====
Экспандер Варди - Парвареша.

====Лекция 11 (13 апреля). ====
Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время.

====Лекция 12 (20 апреля). ====
Оценка Хэмминга.
Линейные коды. Проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга.
Функция Шеннона для двоичного алфавита.

====Лекция 13 (27 апреля) ====
График оценки Хэмминга для произвольного алфавита.

Оценка Гилберта.
Оценка Варшамова - Гилберта.

Cлучайные линейные коды.

====Лекция 14 (18 мая) ====
Коды Возенкрафта.

Каскадные коды.
Коды Форни.

====Лекция 15. (25 мая) ====
Декодирование каскадного кода.
Геометрические факты к первой оценке Плоткина.

====Лекция 16 (27 мая) ====
Первая оценка Плоткина. Геометрический факт для второй оценки Плоткина и сама оценка.

Улучшение оценки Синглтона с помощью оценки Плоткина.
Коды Адамара.

====Лекция 17 (1 июня ) ====
Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта.
Кодовое расстояние и декодирование списком. Декодирование списком кода Адамара.
[https://youtu.be/XQghOUCsQRs Видеозапись лекции]

==Планируемые лекции==
====Лекция 18 (8 июня). ====
Оценка Джонсона.
Оценка Элайеса - Бассалыго.
Декодирование списком кодов Рида - Соломона.
[https://www.youtube.com/watch?v=-WxESbNqy_Y Видеозапись лекции]

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

=== Семинар 1 (19 января) ===
[https://www.dropbox.com/s/zmh1pxi6bpuek1o/cw1.pdf?dl=0 Листок 1 (комбинаторные экспандеры)]

=== Семинар 2 (26 января) ===
[https://www.dropbox.com/s/pu34evbm8y2maqe/cw_2.pdf?dl=0 Листок 2 (спектр графов)]

=== Семинар 3 (2 февраля) ===
[https://disk.yandex.com/i/uDwJFLoHoTX7yA Листок 3]

=== Семинар 4 (9 февраля) ===
[https://drive.google.com/file/d/13-msSbArI1hB9OZaWm-r8IZFphJg5cw6/view?usp=sharing Листок 4]

=== Семинар 5 (16 февраля) ===
[https://disk.yandex.com/i/knXdYXuxQveTpw Листок 5]

=== Семинар 6 (25 февраля) ===
[https://disk.yandex.com/i/TwcqCNKj7r3LMw Листок 6]

=== Семинар 7 (2 марта) ===
[https://disk.yandex.com/i/PWpellxNlUqCaw Листок 7]

=== Семинар 8 (11 марта) ===
[https://drive.google.com/file/d/1vEA8LpabEkZJVlxmHIsKghoN4eYwli9m/view?usp=sharing Листок 8]

=== Семинар 9 (16 марта) ===
[https://disk.yandex.com/i/wVj1SU8049__lw Листок 9]

=== Семинар 10 () ===
[https://disk.yandex.com/i/KIr9jV6_XkiNmw Листок 10]

=== Семинар 11 () ===
[https://disk.yandex.com/i/2TujLV1mw2clIg Листок 11]

=== Семинар 12 () ===
[https://disk.yandex.com/i/48vcnsi2rjBN8w Листок 12]

=== Семинар 13 () ===
[https://drive.google.com/file/d/1kqITKuAUsKmgyOwS_kwb7Ae4JrEXCqau/view?usp=sharing Листок 13]

=== Семинар 14 () ===
[https://drive.google.com/file/d/1YVacYsaI-y-rpRW1pt6ZnSBqCwq8xkkr/view?usp=sharing Листок 14]

=== Семинар 15 () ===
[https://drive.google.com/file/d/141RLRmbm4DabrnS2ksrOWaRehOM7HBaN/view?usp=sharing Листок 15]

=== Семинар 16 () ===
[https://disk.yandex.com.ge/i/cZdb9GKKihxUGA Листок 16]

=== Семинар 17 () ===
[https://disk.yandex.com/i/BmLdOH21GRBp2w Листок 17]

=== Семинар 18 () ===
[https://disk.yandex.com/i/J534wZHs5xKZWA Листок 18]

==Конспекты лекций==
[https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0 Конспекты лекций об экспандерах, полученные переработкой книги Ромащенко]

[https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0 Конспект лекций о кодах с исправлением ошибок] (переработанная версия брошюры Ромащенко, Румянцева, Шеня. "Заметки по теории кодирования."

==Рекомендуемая литература ==

[https://www.mccme.ru/~anromash/courses/expanders-notes-2014.pdf А.Е. Ромащенко. Экспандеры: конструкции и приложения.]

2026-01-19T09:25:43Z

Nvereshagin:

__NOTOC__
= Учебные курсы факультета компьютерных наук =

{| class="wikitable"
|-
! colspan="2" | <div style="text-align: center;">'''Навигация'''</div>
|-
! [[#bachelors|Курсы бакалавриата ФКН]]
| <div style="text-align:center">[[#AMI|ПМИ]] · [[#SE|ПИ]] · [[#DSBA|ПАД]] · [[#compds|КНАД]] · [[#EDA|ЭАД]] · [[#DRIP|ДРИП]] · [[#electives|майноры и факультативы]]</div>
|-
! colspan="2" | [[#DataCulture|Курсы в рамках проекта Data Culture]] · [[#masters|Курсы магистратуры ФКН]] · [[#other|Курсы других факультетов]] · [[#archive|Архив]]
|}

== Курсы за 2025/26 учебный год ==
{| class="wikitable courses"
|-

! width="21%" | 1 курс !! width="21%" | 2 курс !! width="21%" | 3 курс !! width="21%" | 4 курс !! rowspan="2" | '''майноры и факультативы'''
|-
| colspan="4" style="text-align: center;" | '''ПМИ'''
|-
|

'''М+'''

[[Линейная_алгебра_и_геометрия_на_ПМИ_2025/2026_(пилотный_поток) | Линейная алгебра и геометрия (пилотный поток)]]

[[Математический_анализ_1_2025/26_(пилотный_поток) | Математический анализ-1 (пилотный поток)]]

[[Дискретная математика_на_ПМИ_2025/2026_(пилотный_поток) | Дискретная математика (пилотный поток)]]

[[Теория_чисел_(пилотный_поток)_2025/26 | Теория чисел (пилотный поток)]]

'''М'''

[[Линейная_алгебра_и_геометрия_на_ПМИ_2025/2026_(основной_поток) | Линейная алгебра и геометрия (основной поток)]]

[[Математический_анализ_1_2025/26_(основной_поток) | Математический анализ-1 (ПМИ основной поток)]]

[[DM1PMIbase-2025-26 | Дискретная математика (ПМИ основной поток)]]

[[Теория_чисел_(основной_поток)_2025/26 | Теория чисел (основной поток)]]

'''П'''

[[Язык программирования Python 2025/26 (основной поток) ]]

[[Алгоритмы и структуры данных 1 (основной поток) (2 модуль) 2025/2026]]

'''П+'''

[[Язык программирования C++ (пилотный поток) ]]

[[Алгоритмы и структуры данных пилотный поток 2025/2026 | Алгоритмы и структуры данных (пилотный поток)]]

||

'''М+'''

[[Математический_Анализ_2_на_ПМИ_2025/26_(пилотный_поток) | Математический анализ 2 (пилотный поток)]]

[[Теория_вероятностей_2025/26_(пилотный_поток) | Теория вероятностей (пилотный поток)]]

'''М'''

[[Теория_вероятностей_на_ПМИ_2025/2026_(основной_поток) | Теория вероятностей (основной поток)]]

[[Математический_анализ_-_2_(основной_поток)_ПМИ_и_ЭАД_2025/2026 | Математический анализ-2 (ПМИ + ЭАД)]]

 

'''П'''

[[МО-1 | Машинное обучение 1]]

[[Язык_программирования_Python_(углубленный_курс) | Язык программирования Python (углубленный курс)]]
 

[[CAOS-2025/26 | Архитектура компьютеров и операционные системы]]

[[Инструменты_промышленной_разработки | Инструменты промышленной разработки]]

[[Алгоритмы_и_структуры_данных_2_2025/26 | Алгоритмы и структуры данных 2 2025/26]]

[[Язык_программирования_Go | Язык программирования Go]]

[[Комплексный анализ 2025/26]]

[[Функциональный анализ 2025/26]]

[[ Дискретная_математика_2_2025/26 | Дискретная математика 2 2025/26 ]]

||

[[ PE101-25-26 | Performance engineering 101 ]]

[[ Стохастический_анализ_(весна_2026) | Стохастический анализ ]]

[[Функциональное_программирование_2025/2026 | Функциональное программирование]]

[[ Основы_тензорных_вычислений_(2025/26) | Основы тензорных вычислений ]]

[[Рекомендательные системы 2025/26 | Рекомендательные системы]]

[[Глубинное обучение 1 25/26 | Введение в глубинное обучение]]

[[ Types_25 | Типы в языках программирования ]]

[[ Безопасность_компьютерных_систем_25/26 | Безопасность компьютерных систем ]]

[[ Моделирование временных рядов 2025/26 | Моделирование временных рядов ]]

[[ Случайные_процессы_приложения_2025/26 | Случайные процессы и их приложения ]]

'''ПМИ / МОП'''

[[Машинное_обучение_1_25/26 | Машинное обучение 1]]

[[Математическая_статистика_2_2025/2026 | Математическая статистика 2]]

[[ML_Research_Seminar_1 | НИС Машинное Обучение и Приложения 1]]

'''ПМИ / РС'''

[https://docs.google.com/document/d/1sHfi9_m4hx4y0iIgQEueMCr4qokLxh2Bvyzw_MdE2iI/edit?usp=sharing Распределенные системы]

[https://docs.google.com/document/d/1Hqu7iVY0FpYVujjNpIClkIMOQy32YWJpJHZKPSrOtmA/edit?usp=sharing НИС Распределенные системы]

'''ПМИ / ТИ'''

[[ NIS-TCS-25-26 | НИС Теоретическая информатика ]]

[[KKTI-25-26 | Комбинаторные конструкции в теоретической информатике]]

 

||

[[ PE101-25-26 | Performance engineering 101 ]]

[http://wiki.cs.hse.ru/%D0%93%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D1%8B%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8_%D0%BD%D0%B0_%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%B5_%D0%B4%D0%B8%D1%84%D1%84%D1%83%D0%B7%D0%B8%D0%B8_(25/26) Генеративные модели на основе диффузии 25/26]

[[Большие_языковые_модели_25_26 | Большие языковые модели]]

[[Theory_of_computation_2025 | Theory of computation]]

[[Statistical_learning_theory_2025 | Statistical learning theory]]

[[Теория_и_практика_онлайн-экспериментов_25/26 | Теория и практика онлайн-экспериментов]]

[[Современный_NLP_и_большие_языковые_модели_26 | Современный NLP и большие языковые модели]]

'''ПМИ / МОП'''

[http://wiki.cs.hse.ru/%D0%93%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_2_2025 Глубинное обучение 2]

[[ML_Research_Seminar_2 | НИС Машинное Обучение и Приложения 2]]

[[LSML 2025/2026 | Машинное обучение для больших данных]]

'''ПМИ / РС'''

[https://docs.google.com/document/d/1Q2gx-6ugSi9intAW6ZSsLZNrEvl7S5ClyAhn8EjJnRM/edit?usp=sharing НИС Распределенные системы 2]

[https://gitlab.velkerr.ru/velkerr/msbdp-2026/-/blob/main/README.md?ref_type=heads Методы и системы обработки больших данных]

'''ПМИ / ТИ'''

[[ NIS-TCS-25-26 | НИС Теоретическая информатика ]]

[[ OWF-25-26 | Односторонние функции и их применения ]]

[[ ConvApprox26 | Выпуклое программирование и аппроксимационные алгоритмы ]]

 

| rowspan="11" |


[[Майнор_Биоинформатика_1_год_2025/26|Биоинформатика 1 год 2025/26]]

[[Майнор_Биоинформатика_2_год_2025/26|Биоинформатика 2 год 2025/26]]

[[Введение_в_программирование_25/26|Введение в программирование. Питон 25/26]]

[[Введение_в_базы_данных_25/26|Введение в базы данных 25/26]]

[[Основы_глубинного_обучения_25/26|Основы глубинного обучения 25/26]]

[[Основы_машинного_обучения/2026|Основы машинного обучения 25/26]]

[[Прикладные_задачи_анализа_данных/2026|Прикладные задачи анализа данных 25/26]]

[[Kolmogorov_complexity_fall2025|Introduction to Kolmogorov complexity]]

|-
| colspan="4" style="text-align: center;" | '''ПИ'''
|-
|

[[Алгебра_ПИ_2025-2026|Алгебра 25/26]]

[[Дискретная_математика_25/26|Дискретная математика 25/26]]

[[Математический_анализ_25/26|Математический анализ 25/26]]

|
[[НИС_Методы_и_алгоритмы_защиты_информации_25/26|НИС Методы и алгоритмы защиты информации 25/26]]

[[Теория_вероятностей_25/26|Теория вероятностей 25/26]]
[[Математическая_статистика_25/26 | Математическая статистика 2025/26]]
|
 

||
 

|-
| colspan="4" style="text-align: center;" | '''ПАД'''
|-
|
'''1st year DSBA 2025/2026'''

[[Calculus 1 DSBA 2025/2026 | Calculus 1 (modules 1-4)]]

[[C++ Programming Language DSBA 2025/2026 | C++ Programming Language (modules 1-3)]]

[[English DSBA 2025/2026 | English Language (modules 1-4)]]

[[LAaG DSBA 2025/2026 | Linear Algebra and Geometry (modules 1-4)]]

[[Discrete Mathematics 1 DSBA 2025/2026 | Discrete Mathematics 1 (modules 1-3)]]

[[Russian History DSBA 2025/2026 | Russian History (modules 1-4)]]

[[Economics DSBA 2025/2026 | Economics (modules 2-3)]]

[[Foundations of Russian Statehood DSBA 2025/2026 | Foundations of Russian Statehood (module 3)]]

[[Algebra DSBA 2025/2026 | Algebra (module 4)]]

[[Algorithms and Data Structures 1 DSBA 2025/2026 | Algorithms and Data Structures 1 (module 4)]]

[[Python for Data Science DSBA 2025/2026 | Python for Data Science (module 4)]]

||
'''2nd year DSBA 2025/2026'''

[[Algorithms and Data Structures DSBA 2025/2026 | Algorithms and Data Structures (modules 1-3)]]

[[Discrete Mathematics 2 DSBA 2025/2026 | Discrete Mathematics 2 (modules 1-2)]]

[[Calculus 2 DSBA 2025/2026 | Calculus 2 (modules 1-2)]]

[[Probability Theory DSBA 2025/2026 | Probability Theory (modules 1-2)]]

[[Introduction to Micro and Macroeconomics DSBA 2025/2026 | Introduction to Micro and Macroeconomics (modules 1-4)]]

[[Computer Architecture and Operating Systems DSBA 2025/2026 | Computer Architecture and Operating Systems (modules 3-4)]]

[[Mathematical Statistics DSBA 2025/2026 | Mathematical Statistics (modules 3-4)]]

[[Machine Learning 1 DSBA 2025/2026 modules 3-4 | Machine Learning 1 (modules 3-4)]]

[[Differential Equations DSBA 2025/2026 | Differential Equations (modules (3-4)]]

'''Minors'''

[[Business and Management in Global Context DSBA 2025/2026 | Business and Management in Global Context (modules 1-4)]]

[[Introduction to Finance DSBA 2025/2026 | Introduction to Finance (modules 1-4)]]

||
'''3rd year DSBA 2025/2026'''

[[Databases DSBA 2025/2026 | Databases (modules 1-2)]]

[[Optimization Methods DSBA 2025/2026 | Optimization Methods (modules 1-2)]]

[[Machine Learning 1 DSBA 2025/2026 | Machine Learning 1 (modules 1-2)]]

[[Stochastic processes and applications DSBA 2025/2026 | Stochastic processes and applications (modules 1-2)]]

[[Time Series Analysis DSBA 2025/2026 | Time Series Analysis (modules 3-4)]]

[[Deep Learning DSBA 2025/2026 | Deep Learning (modules 3-4)]]

'''Minors'''

[[Introduction to Entrepreneurship DSBA 2025/2026 | Introduction to Entrepreneurship (business minor, modules 1-2)]]

[[Information Systems Management DSBA 2025/2026 | Information Systems Management (business minor, modules 3-4)]]

[[Econometrics DSBA 2025/2026 | Elements of Econometrics (finance minor, modules 1-4)]]

'''Specialization Data Science in Business'''

[[Research Seminar "Data Analysis in Business" DSBA 2025/2026 | Research Seminar "Data Analysis in Business“ (modules 1-4)]]

[[Data Analysis in Business DSBA 2025/2026 | Data Analysis in Business (modules 1-2)]]

[[Investment Management for Business DSBA 2025/2026 | Investment Management for Business (modules 3-4)]]

'''Specialization Data Science in Finance'''

[[Research Seminar "Data Science in Financial Economics" DSBA 2025/2026 | Research Seminar "Data Science in Financial Economics" (modules 1-4)]]

[[Financial Mathematics DSBA 2025/2026 | Financial Mathematics (modules 1-2)]]

[[Risk Management in Bank DSBA 2025/2026 | Risk Management in Bank (modules 3-4)]]

'''Specialization Data Analysis in Applied Research'''

[[Research Seminar "Data Science in Applied Research" DSBA 2025/2026 | Research Seminar "Data Science in Applied Research" (modules 1-4)]]

[[Methods of Mathematical Modeling DSBA 2025/2026 | Methods of Mathematical Modeling (modules 1-2)]]

[[Applied Statistics for Machine Learning DSBA 2025/2026 | Applied Statistics for Machine Learning (modules 3-4)]]

'''Electives (modules 3-4)'''

[[Operations Research and Game Theory DSBA 2025/2026 | Operations Research and Game Theory]]

[[Advanced Statistical Methods DSBA 2025/2026 | Advanced Statistical Methods]]

[[Recommender Systems DSBA 2025/2026 | Recommender Systems]]

||
'''4th year DSBA 2025/2026'''

[[Strategy DSBA 2025/2026 | Strategy (modules 1-3)]]

[[Statistical Methods for Market Research DSBA 2025/2026 | Statistical Methods for Market Research (modules 2-3)]]

'''Electives block 1 (modules 1-3)'''

[[Core Management Concepts DSBA 2025/2026 | Core Management Concepts]]

[[Asset Pricing and Financial Markets DSBA 2025/2026 | Asset Pricing and Financial Markets]]

'''Electives block 2 (modules 1-2)'''

[[Introduction to the Study of Language for Computer Scientists DSBA 2025/2026 | Introduction to the Study of Language for Computer Scientists]]

[[Quantitative Finance DSBA 2025/2026 | Quantitative Finance]]

[[Information Security Risk Management DSBA 2025/2026 | Information Security Risk Management]]

[[Generative Models in Machine Learning DSBA 2025/2026 | Generative Models in Machine Learning]]

[[Natural Language Processing DSBA 2025/2026 | Natural Language Processing]]

'''Electives block 3 (module 3)'''

[[Information Systems DSBA 2025/2026 | Information Systems]]

[[Cоmputer Vision DSBA 2025/2026 | Cоmputer Vision]]

'''Research Seminar Electives (modules 1-3)'''

[[Research Seminar "Data Analysis in the Natural Sciences" DSBA 2025/2026 | Research Seminar "Data Analysis in the Natural Sciences"]]

[[Research Seminar "Data Science in Financial Markets" DSBA 2025/2026 | Research Seminar "Data Science in Financial Markets"]]

[[Research Seminar "Data analysis in complex systems" DSBA 2025/2026 | Research Seminar "Data analysis in complex systems"]]

|-
| colspan="4" style="text-align: center;" | '''КНАД'''
|-
|
[[Программирование на С++ КНАД ВСН 25-26]]

[[Дискретная_Математика_КНАД_2025/26 | Дискретная математика 2025/26 (КНАД)]]

[[Программирование_на_Python_КНАД_25/26 | Программирование на Python 25/26 (КНАД)]]

[[Python_для_сбора_и_анализа_данных_КНАД_25/26 | Python для сбора и анализа данных КНАД 25/26]]

[[Алгоритмы и структуры данных - 1 2025/2026 2 модуль (КНАД)]]

[[Линейная алгебра КНАД 25/26]]

[[Математический Анализ КНАД 25/26]]

||
[[Алгебра КНАД 2025/2026 | Алгебра]]

[[Алгоритмы_и_структуры_данных_2_КНАД_25/26 | Алгоритмы и структуры данных-2]]

[[Математический_анализ_2_КНАД_2025/26 | Математический анализ-2 2025/26 (КНАД)]]

[[Теория_вероятностей_КНАД_2025/26 | Теория вероятностей 2025/26 (КНАД)]]

[[ACOS_COMPDS_2025/26 | Архитектура Компьютера и Операционные Системы]]

[[Математическая_статистика_КНАД_2025/26 | Математическая статистика 2025/26 (КНАД)]]

||
 

||
 

|-
| colspan="4" style="text-align: center;" | '''ЭАД'''
|-
|
[[Программирование на С++ ЭАД 25/26]]

[[Язык программирования Python 2025/26 (ЭАД) ]]

[[DM1EAD-2025-26 | Дискретная математика 2025/26 (ЭАД)]]

[[Линейная_алгебра_и_геометрия_на_ПМИ_2025/2026_(основной_поток) | Линейная алгебра и геометрия]]

[[Математический_анализ_1_2025/26_(основной_поток)_ЭАД | Математический анализ-1 (ЭАД)]]

[[Алгоритмы и структуры данных-1 2025/2026 2 модуль (ЭАД)]]
||

[[Алгоритмы и структуры данных 2 ЭАД 25/26 | Алгоритмы и структуры данных-2]]

||
 

||
 

|-
| colspan="4" style="text-align: center;" | '''ДРИП'''
|-
|
[[Алгоритмы и структуры данных-1 (ДРИП)]]

[[Ddip2529 | Линейная алгебра и геометрия]]

[[DM_DRIP-2025-26 | Дискретная математика 2025/26 (ДРИП)]]

||
[[Теория_вероятностей_ДРИП_25/56 | Теория вероятностей 2025/26 (ДРИП)]]

||
 

||
 

|}

== Курсы в рамках проекта [https://www.hse.ru/dataculture/ Data Culture] ==

{| class="wikitable"
|-
! Осенний семестр !! Весенний семестр
|-
|
|
|}

== Курсы магистратуры ФКН ==
{| class="wikitable"
|-
! Ссылка !! Дисциплина !! Год обучения
|-
| [[ NIS-TCS-25-26 | НИС Теоретическая информатика ]] || НИС ТИ || СКН, 1-2 год
|-
| [[MOTV_2025 | Mathematical foundations of probability theory]] || Math of Machine Learning, MML || 1 year
|-
| [[MC_2025 | Markov Chains]] || Math of Machine Learning, MML || 1 year
|-
| [[Sample_2026 | Sampling and Generative Modeling ]] || Math of Machine Learning, MML || 1 year
|}

== Курсы других факультетов ==

{| class="wikitable"
|-
! Дисциплина !! Курс !! Период
|-
| [[icef-scalc-2025-fall|Stochastic Calculus Fall 2025]] ||icef, master 1 year || 2 module
|-
|}

== Факультативы ==

{| class="wikitable"
|-
! Дисциплина !! Период
|-
| [[Аналитическая_теория_чисел:_приложения_комплексного_анализа_25/26 | Аналитическая теория чисел: приложения комплексного анализа 25/26]] || 1-2 модуль
|-
|}

= Архив до 2024/25 учебного года включительно =
[[Wiki ФКН/Архив]]

OWF-25-26

2025-12-10T19:11:26Z

Nvereshagin:

= Односторонние функции и их применения (4-ый курс ТИ) осенний семестр 2025 года =

Лекции проходят по средам на второй паре. Первая лекция - 17 сентября. Первые три лекции, 17 и 24 сентября и 1 октября будут онлайн по ссылке https://us06web.zoom.us/j/82714202535?pwd=4TlhkxaqswYTeK5oKMY9lbkQlyDemp.1

Семинары проходят по понедельникам на четвертой паре в ауд. S311. Первый семинар - 22 сентября.

==Новости==

Первые три лекции, 17 и 24 сентября и 1 октября будут онлайн по ссылке https://us06web.zoom.us/j/82714202535?pwd=4TlhkxaqswYTeK5oKMY9lbkQlyDemp.1

==Контакты==

Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, телеграм: nikolay_vereshchagin

Семинарист: Мануйленко Никита Сергеевич, nikitamann1910@gmail.com, телеграм: Ni_Mans

Группа в Телеграм: https://t.me/joinchat/seYgH4TaKrsxY2Yy

==Краткое описание==
Функция f, отображающая слова в слова, называется односторонней, если по x можно найти f(x) за полиномиальное от длины x время, однако в обратную сторону,  по f(x) найти x или какой-то другой прообраз f(x) за полиномиальное время можно только на ничтожной доле входов. В спецкурсе будут доказаны основные факты об односторонних функциях. Односторонние функции применяются в криптографии для построения доказуемо надежных генераторов псевдослучайных чисел,  схем шифрования с открытым и закрытым ключом, протоколов привязки, протоколов бросания монетки по телефону и протоколов идентификации. 

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

[https://www.dropbox.com/s/hjdi78zxb2sx3fz/program.pdf?dl=0 Более подробная программа].

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

Итоговая оценка складывается из оценок за домашние задания, за колллоквиум, за экзамен
и за дополнительные сложные задачи.
Она вычисляется так, чтобы усердный студент, хорошо усвоивший курс, но не сделавший ни одной дополнительной задачи, получил 8 баллов.
Оценки за домашние задания, за колллоквиум и за экзамен ставятся по десятибалльной системе. Дополнительные задачи входят в домашние задания и имеют специальные пометки, их будет всего четыре, по одной в каждом ДЗ. За каждую решеннную дополнительную задачу к итоговой оценке прибавляется 0.5 балла.
Точнее, итоговая оценка выставляется по следующуй формуле
MIN{8, 0.2*(оценка за домашние задания)+ 0.4*(оценка за коллоквиум)+ 0.4*(оценка за экзамен)} + (оценка за дополнительные задачи).

=== Домашние задания===
В течение двух модулей студентам будет дано 4 домашних задания.
Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается не менее 14 дней, решение ДЗ нужно присылать семинаристу (в телеграм или на почту)

===Коллоквиум и письменный экзамен===
Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе.

===Правила округления===
В вычислениях текущие оценки и промежуточные величины не округляются. Результат
вычисляется точно и округляется (арифметически) только в момент выставления итоговой оценки.

====Коллоквиум====
Коллоквиум будет 17 декабря онлайн
[https://www.dropbox.com/scl/fi/2vw2wugsjip34o9781wek/colloq.pdf?rlkey=99nofnit6x0gdkei7na83ub6h&st=p0etbpnu&dl=0 Программа коллоквиума]
На каждый из двух дней имеется 7 слотов и надо вписать свою фамилию в один из них.

Подключившись к конференции в то время, в которое записались (см. ниже ссылку на таблицу), Вы получите  один вопрос на теорему с доказательством.  На подготовку ответа на этот вопрос у Вас будет 30 минут, и в это время можно пользоваться любыми источниками.  После ответа на этот вопрос Вы получите второе задание, состоящее из двух вопросов на определение или формулировку теоремы.  На эти вопросы надо отвечать сразу.  Коллоквиум Вы сдаёте устно он-лайн одному из преподавателей.  Для уточнения оценки  преподаватель может задавать дополнительные вопросы на знание определений и  основных фактов курса.  Оценка за коллоквиум формируется следующим образом.  Полный ответ на первый вопрос оценивается в 5 баллов, а полные ответы на другие два вопроса --- в 2.5 балла. [https://docs.google.com/spreadsheets/d/1KGNJOJwU7nDekpDrVpArA-Bp67XnHjf-PanBbD-bjw4/edit?usp=drive_link Таблица для записи на коллоквиум, в таблице дается также ссылка на подключение.]

====Экзамен====

Письменный экзамен будет 22 декабря в 11:10 в ауд. D724 и будет продолжаться 90 минут. Экзамен будет происходить очно, вариант будет состоять из 4 задач.
Разрешено пользоваться печатными конспектами лекций, а также любыми бумажными материалами. Выходить из аудитории во время экзамена нельзя.

Студенты на он-лайн обучении пишут экзаменационное задание с прокторингом. Более подробная инструкция тут:

1. Присоединиться к конференции надо на десять минут раньше, то есть, в 11:00. В 11:10 станут доступны задания, которые надо загрузить по ссылке в чате конференции. Студенты решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.

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

3. Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.

====Пересдачи====

Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен. На пересдачу также могут прийти те, кто в итоге получил менее 4 баллов, и заново сдать коллоквиум и/или экзамен. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, пересдают письменный экзамен комиссии по тем же правилам,
что и штатный письменный экзамен. Итоговая оценка выставляется по той же формуле. 

==Примерные сроки контрольных мероприятий==

Первое домашнее задание 10 октября (выкладывание), 24 октября (сдача).

Второе домашнее задание 18 октября (выкладывание), 1 ноября (сдача).

Третье домашнее задание 8 ноября (выкладывание), 22 ноября (сдача).

Четвертое домашнее задание 6 декабря (выкладывание), 20 декабря (сдача).

==Домашние задания ==

[https://drive.google.com/file/d/1mIwkU4v87RVW-4OXl5xbUlpYRDe22BCA/view?usp=sharing Домашнее задание 1] Срок сдачи 24 октября, 23:59.

[https://drive.google.com/file/d/1BSORlcj5MPHBOvPPDvskIOaHREO9ZGED/view?usp=sharing Домашнее задание 2] Срок сдачи 19 ноября, 23:59.

[https://drive.google.com/file/d/1hSJ9_1QwhA8kD8J8RnxBzYJjrAKfl3Lc/view?usp=sharing Домашнее задание 3] Срок сдачи 4 декабря, 23:59

[https://drive.google.com/file/d/1d_Zdfv1MmA_2g1pEsI_mCn8BnQ_l3Bpq/view?usp=sharing Домашнее задание 4] Срок сдачи 17 декабря 23:59

==Результаты ==
[ Общая ведомость оценок]

==Прочитанные лекции==
====Лекция 1 (17 сентября). ====

Слабо и сильно необратимые функции для равномерного и неравномерного противника.
Односторонние функции.  Если P=NP, то односторонних функций нет. 

====Лекция 2 (24 сентября). ====
Функция Mult.  Функция SubsetSum. Функция Code.

Преобразование слабо необратимой функции в сильно необратимую.

====Лекция 3 (1 октября). ====
Всюду определенные односторонние перестановки.

Функции Рабина, RSA и дискретная экспонента. Полиномиально моделируемые и доступные распределения. 

====Лекция 4 (8 октября). ====
Односторонние перестановки - общее определение. 
Односторонние  перестановки с секретом - определение. Улучшенные перестановки.

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

====Лекция 5 (15 октября). ====

Любой генератор ПСЧ является слабо односторонней функцией.  Теорема о существовании генератора ПСЧ (без доказательства),  если существуют односторонние функции.
Свойства вычислительно неотличимых случайных величин.
Теорема Блюма и Микэли.

Определение трудного предиката. Теорема Яо. Использование трудного предиката и  инвариантного распределения для построения генератора ПСЧ.

====Лекция 6 (22 октября). ====
Теорема Левина-Голдрайха о коде Адамара. Построение трудного предиката для данной односторонней  функции. 

====Лекция 7 (22 октября). ====
Окончание доказательства корректности построения трудного предиката.

Одноразовые схемы шифрования с закрытым ключом.
Построение одноразовой СШЗК на основе генератора ПСЧ. Одноразовые схемы шифрования с открытым ключом.  Построение
одноразовой СШOК на основе генератора односторонней перестановки с секретом.

====Лекция 8 (5 ноября). ====
Многоразовые схемы шифрования.  Семейства ПСФ. Построение семейства ПСФ на основе  генератора ПСЧ. Многоразовая СШЗК на основе семейства ПСФ.  

====Лекция 9 (12 ноября). ====
 Неинтерактивные протоколы привязки к биту.  Построение протокола привязки к биту на основе инъективной односторонней  функции. Интерактивные алгоритмы. Интерактивные протоколы привязки к биту. 

====Лекция 10 (19 ноября). ====

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

====Лекция 11 (26 ноября). ====

Построение протоколов идентификации  с закрытым ключом для двух других видов атаки.
Построение протоколов идентификации  с открытым ключом для двух других видов атаки.

==Планируемые лекции==

====Лекция 12 (3 декабря). ====
Доказательство неразглашения информации для протокола идентификации  с открытым ключом
при атаке с фальшивым банкоматом.

Криптографические семейства хэш-функций.

====Лекция 13 (10 декабря). ====
Протоколы электронной подписи.

====Лекция 14 (17 декабря). ====
Коллоквиум.

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

====Семинар 1 (22 сентября). ====
[https://drive.google.com/file/d/19DDarvWnjfKiFLG1IQUoggq3w7YnWlxl/view?usp=sharing Листок 1]

====Семинар 2 (29 сентября). ====
[https://drive.google.com/file/d/1tp7BCD74Mb6-FhvRdpJ_titMUwQhA6v9/view?usp=sharing Листок 2]

====Семинар 3 (6 октября). ====
[https://drive.google.com/file/d/1fpkQdvXrzkAmDeujdmlbhRX2GRG4IoZX/view?usp=sharing Листок 3]

====Семинар 4 (13 октября). ====
[https://drive.google.com/file/d/1REv4lckpjBzGu_vx18nlxehdoHdFaiec/view Листок 4]

====Семинар 5 (20 октября). ====
[https://drive.google.com/file/d/1lzQ0BwLYzwh_uuJM8f2QVAW5KsOfMuDq/view?usp=sharing Листок 5]

====Семинар 6 (23 октября). ====
[https://drive.google.com/file/d/1YYN2_NJHWWLpbZO64_PpCOsOiUHr-VT9/view?usp=drivesdk Листок 6]

====Семинар 7 (5 ноября). ====
[https://drive.google.com/file/d/1G9INcVBKRpPnpeEGNwfJhpbi0UPzh1xv/view?usp=sharing Листок 7]

====Семинары 8-9 (10 ноября). ====
[https://drive.google.com/file/d/1pC-jLNrIb42N8gmmdlA4qeLbpjtrG3sV/view?usp=sharing Листок 8]

====Семинар 10 (17 ноября). ====
[https://drive.google.com/file/d/1TEuM6LvEl0tfD5T5kVVotyCpO5iC4y1P/view?usp=sharing Листок 10]

====Семинар 11 (24 ноября). ====
[https://drive.google.com/file/d/1KU0m0XvYD9-2lhFqDvKCbiJJIdnNTQ1A/view?usp=sharing Листок 11]

====Семинар 12 (8 декабря). ====
[https://drive.google.com/file/d/1XBTC3mk7sHNa_lwZrJsPbs9doJnnp1Ld/view?usp=sharing Листок 12]

==Конспекты лекций==

[https://www.dropbox.com/s/tgb6ipbgd9wfpre/lectures.pdf?dl=0 В этой незаконченной книге есть все, что будет на лекциях.]

==Рекомендуемая литература ==

0. Китаев А., Шень А., Вялый М. Классические и квантовые вычисления.  Изд-во МЦНМО.   

1. Введение в криптографию. Под общей редакцией В.В.Ященко. --- 3-е изд. доп. --- М.: МЦНМО: "ЧеРо", 2000. --- 288 с. 
 

2. М.И. Анохин, Н.П.Варновский, В.М.Сидельников, В.В. Ященко. Криптография в банковском деле. М.: МИФИ, 1997.  

3. O. Goldreich. Foundations of cryptography. Basic tools. Cambridge Univ. Press. 2001. 400 p.  

4. O. Goldreich. Foundations of cryptography. Basic applications. Cambridge Univ. Press. 2004.