Комбинаторные конструкции в теоретической информатике — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Новая страница: «= Комбинаторные конструкции в теоретической информатике (3-ий курс ТИ) 2021 год = Лекции про…»)
 
Строка 6: Строка 6:
  
 
==Новости==
 
==Новости==
−
====20 июня====
 
−
Экзамен состоится 22 июня в 12.10 и будет продолжаться 90 минут. Более подробная инструкция тут:
 
−
 
−
1.  Экзамен письменный и проходит с прокторингом через Зум в двух конференциях
 
−
https://zoom.us/j/91507546088
 
−
https://zoom.us/j/94570444864
 
−
(распределение по конференциям [https://docs.google.com/spreadsheets/d/1mrsKOieGXr-98mUCnjiJFAgPKH9RlvFvybqQmocLQB8/edit#gid=0 здесь)]. Присоединиться к конференции надо на десять минут раньше, то есть, в 12:00. В 12:10 станут доступны задания, которые надо  загрузить по ссылке https://www.dropbox.com/s/ualljvsdkp2mg35/exam22-06-2020.pdf?dl=0 (сейчас по этой ссылке находятся прошлогодние задания). Студенты решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com.  Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.
 
−
 
−
2.  Экзамен длится 90 минут. Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций: https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0 https://www.dropbox.com/s/4eakm5abultga7x/DecisionTrees.pdf?dl=0, https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.
 
−
 
−
3.  Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.
 
−
 
−
====19 июня====
 
−
Выложен
 
−
[https://www.dropbox.com/s/185mhm4yq9279gq/exam_train.pdf?dl=0 тренировочный вариант] экзамена. Задачи на самом экзамене могут сильно отличаться.
 
−
 
−
====14 июня====
 
−
Коллоквиум будет проходить по следующей ссылке
 
−
https://zoom.us/j/92034518702
 
−
 
−
====4 июня====
 
−
Перенос лекции на субботу ОТМЕНЯЕТСЯ. А коллоквиум переносится на 15 июня 10:00.
 
−
Последняя лекция и семинар состоятся 9 июня с 15:10 по обычному расписанию.
 
−
 
−
====2 июня====
 
−
По просьбе студентов, последняя лекциия и семинар переносятся со вторника 9 июня на субботу 6 июня. Лекция 10-11:20, семинар 11:30-12:50.
 
−
Коллоквиум можно будет сдавать, как 6 июня с 13:00, так и 9 июня с 15:10, предварительно записавшись на некоторый слот
 
−
в таблицу [https://docs.google.com/spreadsheets/d/1Ehpo-1t8jbEjVx4oqQ29CCVwB7IG2zoSvzYCR6ZKmss/edit?usp=sharing Таблица времени прихода на коллоквиум]
 
−
 
−
====1 июня====
 
−
Выложена
 
−
[https://docs.google.com/spreadsheets/d/1Ehpo-1t8jbEjVx4oqQ29CCVwB7IG2zoSvzYCR6ZKmss/edit?usp=sharing Таблица времени прихода на коллоквиум]
 
−
 
−
====26 мая====
 
−
Выложена программа коллоквиума 6 июня. [https://www.dropbox.com/s/gm3ezn8ygyk54te/colloq2020.pdf?dl=0 Программа.]
 
−
 
−
====20 мая====
 
−
Коллоквиум состоится 6 июня в 10.00.
 
−
 
−
Письменный экзамен состоится 22 июня в 12.10.
 
−
 
−
====21 апреля====
 
−
Платформа webinar.ru оказалась неудобной для наших лекций. Начиная со следующего вторника мы возвращаемся в Zoom https://zoom.us/j/461361055
 
−
Но теперь в конце или середине каждой лекции будет экспресс-тест на 10 минут, проводимый с помощью Гугл-формы. Те, кто заработают за тесты более половины максимально возможного количества баллов, получат 1 бонусный балл к итоговой оценке. Оценки за тесты выставляются в обычную ведомость https://www.dropbox.com/s/akpdy4oyflgd6zi/results_2020.xlsx?dl=0
 
−
Сссылка на лекции и семинары: https://zoom.us/j/461361055
 
−
 
−
====28 марта====
 
−
Согласно приказу ректора, все занятия 31 марта отменяются!
 
−
 
−
====21 марта====
 
−
Лекция 24 марта (вторник) в 15:10-16:30 состоится в виде  вебинара. Вот ссылка на вебинар: https://zoom.us/j/912901893
 
−
Преимущество вебинара перед Ютуб трансляцией в том, что удобнее задавать вопросы по ходу лекции (это можно делать и устно, и письменно).
 
−
 
−
====20 марта====
 
−
Весенняя сессия отменяется, поэтому лекция и семинар 31 марта состоятся.
 
−
 
−
====16 марта====
 
−
C 17 марта 2020 года ВШЭ  перешла на дистанционное обучение (карантинная мера, вызванная распостранением коронавируса). Лекции курса будут транслироваться и записываться в обычное время (по вторникам с 15:10 до 16:30) на Ютуб канале https://www.youtube.com/channel/UCQpMy-jk_5qdi91U9NsBVdQ?view_as=subscriber
 
−
 
−
Во время трансляции можно задавать вопросы в чате, на которые лектор сможет отвечать примерно с полминутной задержкой. Очередная трансляция состоится 17 марта.
 
−
 
−
[https://www.youtube.com/watch?v=UisbwObZ1QY Лекция 17 марта]
 
  
 
==Лектор==  
 
==Лектор==  
Строка 76: Строка 14:
  
 
Милованов Алексей Сергеевич almas239@gmail.com
 
Милованов Алексей Сергеевич almas239@gmail.com
−
 
−
Консультации (защиты): по вторникам 14-15, 18-19 и по средам 15.10-16 в S832.
 
  
 
==Краткое описание==
 
==Краткое описание==
  
−
Экспандеры и их применения:теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти, экспандерные коды.
+
Экспандеры и их применения: теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти, построение генераторов псевдослучайных чисел, экспандерные коды.
  
 
Коды с исправлением ошибок для компьютерных наук.
 
Коды с исправлением ошибок для компьютерных наук.
Строка 87: Строка 23:
 
Представление булевых функций деревьями разрешения и многочленами.  
 
Представление булевых функций деревьями разрешения и многочленами.  
  
−
Разрешимость элементарных теорий упорядоченного поля действительных чисел (теорема Тарского-Зайденберга и
 
−
поля комплексных чисел.
 
  
 
==Отчётность по курсу и критерии оценки==
 
==Отчётность по курсу и критерии оценки==
  
−
4 домашних задания, коллоквиум и экзамен.
+
Итоговая оценка складывается из оценок за домашние задания, оценок за тесты, и оценки за коллоквиум и экзамен. Оценки за колллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.3, а оценки за домашние задания и тесты - с коэффициентом 0.2.
  
−
Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. Кроме этого в домашних задания могут бонусные задачи, за решение которых даются дополнительные баллы на коллоквиуме или экзамене (1 задача= 1 балл).  На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать семинаристу до начала семинара.
+
=== Тесты ===
−
Сдача домашних заданий после их срока невозможна.
+
В конце каждой лекции будет предлагаться десятиминутный тест с простыми задачами. Целью тестов является контроль за тем, чтобы студенты
 +
внимательно слушали лекцию. К написанию теста допускаются только присутствовавшие на лекции (разрешается десятиминутное опоздание к началу лекции). За каждый тест
 +
выставляется оценка, равная доле правильных ответов, умноженной на 10.
 +
Общая оценка за тесты равняется среднему арифметическому оценок за все тесты.
  
−
Каждое ДЗ будет проверено в течение 10 дней после дедлайна. Домашнее задание должно быть защищено в течение 3 недель после дедлайна. Для защиты студент должен прийти на консультацию и убедить преподавателя, что он понимает, что у него написано, и тем самым работа не списана.
+
=== Домашние заданийя===
 +
В течение двух модулей студентам будет дано 4 домашних заданий.  
 +
Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается 14 дней, решение ДЗ нужно сдавать '''семинаристу или лектору''' устно (онлайн). Сдача домашних заданий после их срока невозможна.
  
−
Коллоквиум (устный) и экзамен (письменный) оцениваются по десятибалльной системе. На коллоквиуме  не разрешается пользоваться никакими записями. На экзамене можно пользоваться любыми бумажными источниками и нельзя никакими электронными.
+
===Коллоквиум и письменный экзамен===
 +
Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе.
  
−
Оценки за коллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценка за домашние задания - с коэффициентом 0.2.
+
Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один  раз). Это же относится и к тем, кто не смог прийти на экзамен. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.  
−
 
+
−
Те, кто не смог прийти на экзамен или коллоквиум по болезни, могут его сдать их отдельно. Не набравшие в конце второго модуля нужное количество баллов (4) могут пересдать экзамен, а если и это не поможет, то сдавать экзамен комиссии. В последнем случае накопленная оценка аннулируется и оценка, полученная на экзамене, и является окончательной.  
+
−
 
+
−
====Правила округления====
+
  
 +
===Правила округления===
 
В вычислениях текущие оценки и промежуточные величины не округляются. Результат
 
В вычислениях текущие оценки и промежуточные величины не округляются. Результат
 
вычисляется точно и округляется (арифметически) только в момент выставления итоговой оценок.
 
вычисляется точно и округляется (арифметически) только в момент выставления итоговой оценок.
Строка 112: Строка 49:
 
====Коллоквиум====
 
====Коллоквиум====
  
−
Коллоквиум состоится 15 июня в 10:00.  
+
Коллоквиум состоится ...  
−
Записываться в таблицу: [https://docs.google.com/spreadsheets/d/1Ehpo-1t8jbEjVx4oqQ29CCVwB7IG2zoSvzYCR6ZKmss/edit?usp=sharing Таблица времени прихода на коллоквиум]
+
Записываться в таблицу: ...
  
−
[https://www.dropbox.com/s/gm3ezn8ygyk54te/colloq2020.pdf?dl=0 Программа коллоквиума.]
+
[ Программа коллоквиума.]
−
Ссылка на Зум конференцию для тех, кто оказался записанным к лектору: https://us02web.zoom.us/j/82787088715
+
  
 
====Экзамен====
 
====Экзамен====
  
−
Экзамен состоится 22 июня в 12.10 и будет продолжаться 90 минут. Более подробная инструкция тут:
+
Экзамен состоится ...
  
−
1.  Экзамен письменный и проходит с прокторингом через Зум в двух конференциях:
+
Экзамен проходит с прокторингом. Студенты загружают задание по ссылке ... , решают на бумаге, в конце экзамена делают фотографии/сканы решений, сшивают в один PDF файл и загружают по следующей ссылке ... . Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.
−
https://zoom.us/j/91507546088
+
 
−
https://zoom.us/j/94570444864
+
Экзамен длится 90 минут. Во время экзамена студенты должны включить камеры. Во время экзамена разрешено смотреть на  любые материалы, загруженные на компьютер до начала экзамена, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать загруженные материалы и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ. 
−
(распределение по конференциям [https://docs.google.com/spreadsheets/d/1mrsKOieGXr-98mUCnjiJFAgPKH9RlvFvybqQmocLQB8/edit#gid=0 здесь)].https://zoom.us/j/94570444864. Присоединиться к конференции надо на десять минут раньше, то есть, в 12:00. В 12:10 станут доступны задания, которые надо  загрузить по ссылке https://www.dropbox.com/s/ualljvsdkp2mg35/exam22-06-2020.pdf?dl=0 (сейчас по этой ссылке находятся прошлогодние задания). Студенты решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.
+
 
 +
Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется).  Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.
  
−
2.  Экзамен длится 90 минут. Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций: https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0 https://www.dropbox.com/s/4eakm5abultga7x/DecisionTrees.pdf?dl=0, https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.
 
  
−
3.  Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.
 
  
 
====Пересдачи====
 
====Пересдачи====
Строка 135: Строка 70:
 
==Примерные сроки контрольных мероприятий==
 
==Примерные сроки контрольных мероприятий==
  
−
Первое домашнее будет выложено 29.1.2020, срок сдачи 11.2.2020.
+
Первое домашнее будет выложено , срок сдачи .
  
−
Второе домашнее будет выложено 3.3.2020, срок сдачи 31.3.2020.
+
Второе домашнее будет выложено , срок сдачи .
  
−
Третье домашнее будет выложено 24.4.2020, срок сдачи 19.5.2020.
+
Третье домашнее будет выложено , срок сдачи .
  
−
Четвертое домашнее будет выложено 14.5.2020, срок сдачи 9.6.2020.
+
Четвертое домашнее будет выложено , срок сдачи .
  
 
==Домашние задания  ==
 
==Домашние задания  ==
Строка 148: Строка 83:
  
  
−
[https://www.dropbox.com/s/wcevcspilg63qep/hw1_expanders.pdf?dl=0 Домашнее задание 1]. Cрок сдачи 12.2.2020 в 12:10 MSK.
+
[Домашнее задание 1]. Cрок сдачи .
  
−
[https://www.dropbox.com/s/oksggnm5e2pm7rh/hw2_expanders.pdf?dl=0 Домашнее задание 2] Срок сдачи 7.4.2020 в 16.40 MSK.
 
  
−
[https://www.dropbox.com/s/p8y52xy7dg50u5y/CCTI_3.pdf?dl=0 Домашнее задание 3] Срок сдачи 19.5.2020 в 16.40 MSK.
 
−
 
−
[https://www.dropbox.com/s/dd98kswtswqubmf/CCTI_4.pdf?dl=0 Домашнее задание 4] Срок сдачи 16.6.2020 в 16.40 MSK.
 
  
 
==Результаты ==
 
==Результаты ==
−
[https://www.dropbox.com/s/j6vnaesx569p4cv/results_2020.xlsx?dl=0 Общая ведомость оценок]
+
[ Общая ведомость оценок]
−
 
+
−
[https://www.dropbox.com/s/8hm8r0z8bdxtmx0/test1.xlsx?dl=0  Результаты теста 1]
+
−
 
+
−
[https://docs.google.com/spreadsheets/d/11jWr5fzwdTRnD2UH3u8oRMkW6VomdH3fiwmLoNz2-Jc/edit?usp=sharing  Результаты теста 2]
+
−
 
+
−
[https://docs.google.com/spreadsheets/d/1-2JQgSmIafNuwJkyn5EcYlGY94MNgyyzue25F2NI5qw Результаты теста 3.]
+
  
−
[https://docs.google.com/spreadsheets/d/1pL7eabfoztAlA8iLps9x_oyW4zuPbU7YMRFmLfc_-qY Результаты теста 4]
+
[ Результаты теста 1]
  
−
[https://docs.google.com/spreadsheets/d/1m3-9zWvk3MhApp6Di0KfK0qSYlPdcDykOsEIiCnZ5-s Результаты теста 5]
 
  
−
[https://docs.google.com/spreadsheets/d/1l2UfO8t68lIjt98LaibTY80KNl1edWY1MF1Ypmn7AhU Результаты теста 6 ]
 
  
−
==Прочитанные лекции==
+
==Планируемые лекции==
  
 
====Лекция 1 (21 января).  ====
 
====Лекция 1 (21 января).  ====
Строка 221: Строка 144:
 
====Лекция 12 (14 апреля). ====
 
====Лекция 12 (14 апреля). ====
 
[https://youtu.be/OfQgPjzH97Q Коды с исправлением ошибок и их параметры. Линейные коды. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время.]
 
[https://youtu.be/OfQgPjzH97Q Коды с исправлением ошибок и их параметры. Линейные коды. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время.]
−
 
−
====Лекция 13 (21 апреля).  ====
 
−
[https://eve
 

Версия 17:09, 11 января 2021

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

Лекции проходят по пятицам 13:00-14:20, семинары также по пятницам 14:40-16:00 через Zoom по ссылке

Первая лекция и семинар 15 января.

Новости

Лектор

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

Семинарист

Милованов Алексей Сергеевич almas239@gmail.com

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

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

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

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


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

Итоговая оценка складывается из оценок за домашние задания, оценок за тесты, и оценки за коллоквиум и экзамен. Оценки за колллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.3, а оценки за домашние задания и тесты - с коэффициентом 0.2.

Тесты

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

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

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

Коллоквиум и письменный экзамен

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

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

Правила округления

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

Коллоквиум

Коллоквиум состоится ... Записываться в таблицу: ...

[ Программа коллоквиума.]

Экзамен

Экзамен состоится ...

Экзамен проходит с прокторингом. Студенты загружают задание по ссылке ... , решают на бумаге, в конце экзамена делают фотографии/сканы решений, сшивают в один PDF файл и загружают по следующей ссылке ... . Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.

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

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


Пересдачи

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

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

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

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

Четвертое домашнее будет выложено , срок сдачи .

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

[Домашнее задание 1]. Cрок сдачи .


Результаты

[ Общая ведомость оценок]

[ Результаты теста 1]


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

Лекция 1 (21 января).

Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство). Реберное расширение и его связь с вершинным расширением. Матрица графа и ее собственные числа.

Лекция 2 (28 января).

Максимальное по абсолютной величине собственное число регулярного графа. От чего зависит кратность собственного числа d. Второе по абсолютной величине собственное число двудольного графа.

Лемма о перемешивании. От спектрального экспандера к комбинаторному.

Лекция 3 (4 февраля).

Вторая лемма о перемешивании. Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа.

Лекция 4 (11 февраля).

Формула для числа Каталана. Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами.

Лекция 5 (18 февраля).

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

Лекция 6 (25 февраля).

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

Лекция 7 (3 марта).

Второе собственное число связного недвудольного графа.

Алгоритм Рейнгольда.

Лекция 8 (10 марта).

Применение экспандеров для дерандомизации.

Лекция 9 (17 марта).

Экспандер Маргулиса.

Лекция 10 (24 марта).

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

Лекция 11 (7 апреля).

Экспандер Варди - Парвареша.

Лекция 12 (14 апреля).

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

Источник — «http://wiki.cs.hse.ru/index.php?title=Комбинаторные_конструкции_в_теоретической_информатике&oldid=49446»