Основы матричных вычислений 2023/24 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Создана страница ОМВ24)
 
(пдз4)
 
(не показаны 32 промежуточные версии 6 участников)
Строка 12: Строка 12:
 
! Группа !! Преподаватель !! Учебные ассистенты || Чат в телеграм
 
! Группа !! Преподаватель !! Учебные ассистенты || Чат в телеграм
 
|-
 
|-
−
| 1 || Рахуба Максим Владимирович || ? || ?
+
| 1 || Рахуба Максим Владимирович || [https://t.me/mac_mvak Максим Васильев], [https://t.me/rey_arzhan Андрей Аржанцев] || [https://t.me/+iOX1w7ZasIMwZThi tg]
 
|-
 
|-
−
| 2 || Самсонов Сергей Владимирович || ? || ?
+
| 2 || Самсонов Сергей Владимирович || [https://t.me/theydontknowwho Никита Козлов], [https://t.me/armalko Артем Малько] || [https://t.me/+RbUyveDdcVwwMjQy tg]
 
|-
 
|-
−
| 3 || Пешехонов Иван Дмитриевич || ? || ?
+
| 3 || Ваня Пешехонов || [https://t.me/sidorenko_ivan Иван Сидоренко], [https://t.me/timofon Тимофей Сенин] || [https://t.me/+BSjXz1Vu6WA4ZDRi tg]
 
|-
 
|-
−
| 4 || Кухарчук Иван Андреевич || ? || ?
+
| 4 || Кухарчук Иван Андреевич || [https://t.me/epbugaev Егор Бугаев], [https://t.me/timofon Тимофей Сенин] || ?
 
|-
 
|-
−
| 5 || Сендерович Александра Леонидовна || ? || [https://t.me/+5P_wclH9XFU5MDQy tg]
+
| 5 || Сендерович Александра Леонидовна || [https://t.me/KingOfTheFlies Алмасбек Стамбеков], [https://t.me/n00t_noot Максим Захарченко] || [https://t.me/+5P_wclH9XFU5MDQy tg]
 
|-
 
|-
−
| 6 || Медведь Никита Юрьевич || ? || ?
+
| 6 || Медведь Никита Юрьевич || [https://t.me/free001style Илья Дробышевский], [https://t.me/StarCityDragon Виктория Шварева], [https://t.me/n00t_noot Максим Захарченко] || [https://t.me/+zNPLF5jE13JlZjI6 tg]
 
|-
 
|-
−
| 7 || Левин Илья Валерьевич || ? || ?
+
| 7 || Левин Илья Валерьевич || [https://t.me/Alexander_Gaponov Александр Гапонов], [https://t.me/armalko Артем Малько] || ?
 
|}
 
|}
  
 
=== Полезные ссылки ===
 
=== Полезные ссылки ===
−
[https://t.me/+yA9jnmI6bq5hMzMy Телеграм-канал курса]
+
[https://docs.google.com/spreadsheets/d/1QXpBe29rJEnhQj3QbYK390Ud23zhEVJU6xwB2uDQv0Q/edit#gid=296628577 Ведомость]
 +
 
 +
[https://docs.google.com/spreadsheets/d/1Z_FU0eMxx0sw7DcRbJ5UqDsNBxQ6arqyvO5kbVkFWKg/edit#gid=1240942164 Разбиение по группам]
 +
 
 +
[https://t.me/+dwtHumakasQ5YjFi Телеграм-канал курса]
  
 
[https://t.me/+l-V9fCJoPWJlNGEy Телеграм-чат курса]
 
[https://t.me/+l-V9fCJoPWJlNGEy Телеграм-чат курса]
 +
 +
[https://disk.yandex.ru/d/JloPfHSUb5fWew Папка с материалами]
  
 
[https://yadi.sk/i/9yxtvKpGnAhC0g Неофициальный конспект лекций 2021-2022 от студента (могут быть ошибки)]
 
[https://yadi.sk/i/9yxtvKpGnAhC0g Неофициальный конспект лекций 2021-2022 от студента (могут быть ошибки)]
Строка 37: Строка 43:
  
 
== План курса ==
 
== План курса ==
−
Если какие-то лекции не выложены или найдены ошибки на вики-странице - пишите @strange_guest
+
Если какие-то лекции не выложены или найдены ошибки на вики-странице - пишите @strange_guest.
 +
 
 +
# '''Основы матричного анализа''' (19.01.2024). Векторные и матричные нормы. Скалярное произведение и ортогональность. Разложение Шура. [https://disk.yandex.ru/i/i__2DfF1h4IvdQ Слайды] [https://disk.yandex.ru/d/kcf1XRIZqHWncQ/%D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_19.01.mp4 Запись] [https://disk.yandex.ru/i/wB5Dw7WzAvjzzw Конспект (TeX)]
 +
# '''Малоранговое приближение матриц – 1''' (26.01.2024). Нормальные матрицы. Знакоопределённые матрицы. Сингулярное разложение (SVD): доказательство существования, наивный алгоритм, связь с матричными нормами. Теорема Эккарта-Янга-Мирского. [https://disk.yandex.ru/i/t9D31fx4TJsKJw Слайды] [https://disk.yandex.ru/d/kcf1XRIZqHWncQ/Лекция%202024-01-26T08-02-21Z.mp4 Запись] [https://disk.yandex.ru/i/TgSoS_2J891zig Конспект (TeX)]
 +
# '''Малоранговое приближение матриц – 2''' (02.02.2024). Скелетное разложение: разделение переменных и ранг, CUR-разложение и интерполяционная формула. Малоранговая арифметика: QR-разложение, преобразование скелетного разложения в SVD. [https://docs.yandex.ru/docs/view?url=ya-disk-public%3A%2F%2Fca2iSjNkF84qhKovSZ7mzgmROUBDyuJh3z0YmGcvj%2FSctff0pb9ch0udBlbVKM9Rq%2FJ6bpmRyOJonT3VoXnDag%3D%3D%3A%2Flectures%2Flecture3_fmatcomp24.pdf&name=lecture3_fmatcomp24.pdf&nosw=1 Слайды] [https://disk.yandex.ru/d/kcf1XRIZqHWncQ/Лекция%202024-02-02T08-04-01Z.mp4 Видео]
 +
# '''Малоранговое приближение матриц – 3''' (09.02.2024). Ортопроекторы. Приближение образа матрицы. Простейший рандомизированный алгоритм поиска усечённого SVD. [https://docs.yandex.ru/docs/view?url=ya-disk-public%3A%2F%2Fca2iSjNkF84qhKovSZ7mzgmROUBDyuJh3z0YmGcvj%2FSctff0pb9ch0udBlbVKM9Rq%2FJ6bpmRyOJonT3VoXnDag%3D%3D%3A%2Flectures%2Flecture4_fmatcomp24.pdf&name=lecture4_fmatcomp24.pdf&nosw=1 Доска] [https://disk.yandex.ru/d/kcf1XRIZqHWncQ/Лекция%202024-02-09T08-04-34Z.mp4 Видео]
 +
# '''Малоранговое приближение матриц – 4''' (16.02.2024). Alternating least squares (ALS). Матрично-векторное дифференцирование. Кронекерово произведение. [https://docs.yandex.ru/docs/view?url=ya-disk-public%3A%2F%2Fca2iSjNkF84qhKovSZ7mzgmROUBDyuJh3z0YmGcvj%2FSctff0pb9ch0udBlbVKM9Rq%2FJ6bpmRyOJonT3VoXnDag%3D%3D%3A%2Flectures%2Flecture5_fmatcomp24.pdf&name=lecture5_fmatcomp24.pdf&nosw=1 Доска] [https://disk.yandex.ru/d/kcf1XRIZqHWncQ/Лекция%202024-02-16T06-24-04Z.mp4 Видео]
 +
# '''Малоранговое приближение многомерных массивов''' (26.02.2024). Каноническое тензорное разложение. Разложение Таккера. Higher-order SVD. [https://docviewer.yandex.ru/?url=ya-disk-public%3A%2F%2Fca2iSjNkF84qhKovSZ7mzgmROUBDyuJh3z0YmGcvj%2FSctff0pb9ch0udBlbVKM9Rq%2FJ6bpmRyOJonT3VoXnDag%3D%3D%3A%2Flectures%2Flecture6_fmatcomp24.pdf&name=lecture6_fmatcomp24.pdf Доска] [https://disk.yandex.ru/d/kcf1XRIZqHWncQ/Лекция%202024-02-26T13-10-43Z.mp4 Видео] [https://docviewer.yandex.ru/?url=ya-disk-public%3A%2F%2Fca2iSjNkF84qhKovSZ7mzgmROUBDyuJh3z0YmGcvj%2FSctff0pb9ch0udBlbVKM9Rq%2FJ6bpmRyOJonT3VoXnDag%3D%3D%3A%2Flectures%2Flectures_tex%2Flecture6_fmatcomp24_tex.pdf&name=lecture6_fmatcomp24_tex.pdf Конспект (TeX)]
 +
# '''Вычисление QR-разложения''' (01.03.2024). Отражения Хаусхолдера. Вращения Гивенса. Rank-revealing QR (RRQR). [https://docviewer.yandex.ru/?url=ya-disk-public%3A%2F%2Fca2iSjNkF84qhKovSZ7mzgmROUBDyuJh3z0YmGcvj%2FSctff0pb9ch0udBlbVKM9Rq%2FJ6bpmRyOJonT3VoXnDag%3D%3D%3A%2Flectures%2Flecture7.pdf&name=lecture7.pdf Доска] [https://disk.yandex.ru/d/kcf1XRIZqHWncQ/Лекция%202024-03-01T15-08-42Z.mp4 Видео]
 +
# '''Метод наименьших квадратов и псевдообратные матрицы''' (11.03.2024). Полноранговый случай. Общий случай. Регуляризация. [https://docs.yandex.ru/docs/view?url=ya-disk-public%3A%2F%2Fca2iSjNkF84qhKovSZ7mzgmROUBDyuJh3z0YmGcvj%2FSctff0pb9ch0udBlbVKM9Rq%2FJ6bpmRyOJonT3VoXnDag%3D%3D%3A%2Flectures%2Flecture8.pdf&name=lecture8.pdf&nosw=1 Доска] [https://disk.yandex.ru/d/kcf1XRIZqHWncQ/Лекция%202024-03-11T13-20-41Z.mp4 Видео]
 +
# '''FFT и структурированные матрицы''' (15.03.2024). Быстрое преобразование Фурье (FFT). Циркулянты. Тёплицевы матрицы. [https://docs.yandex.ru/docs/view?url=ya-disk-public%3A%2F%2Fca2iSjNkF84qhKovSZ7mzgmROUBDyuJh3z0YmGcvj%2FSctff0pb9ch0udBlbVKM9Rq%2FJ6bpmRyOJonT3VoXnDag%3D%3D%3A%2Flectures%2Flecture9.pdf&name=lecture9.pdf Доска] [https://disk.yandex.ru/d/kcf1XRIZqHWncQ/Лекция%202024-03-15T08-10-11Z.mp4 Видео]
 +
# '''FFT и структурированные матрицы – 2''' (22.03.2024). FFT для произвольных n. Дискретная свёртка. FFT, тёплицевы матрицы, циркулянты в 2D. Дискретное косинус-преобразование (DCT). [https://docs.yandex.ru/docs/view?url=ya-disk-public%3A%2F%2Fca2iSjNkF84qhKovSZ7mzgmROUBDyuJh3z0YmGcvj%2FSctff0pb9ch0udBlbVKM9Rq%2FJ6bpmRyOJonT3VoXnDag%3D%3D%3A%2Flectures%2Flecture10.pdf&name=lecture10.pdf&nosw=1 Доска] [https://disk.yandex.ru/d/kcf1XRIZqHWncQ/Лекция%202024-03-22%20T08-10-11Z.mp4 Видео]
 +
# '''Умножение матриц, вычислительная устойчивость, обусловленность''' (05.04.2023). Метод Штрассена. BLAS. Машинные числа. Вычислительная устойчивость. Обусловленность. [https://docs.yandex.ru/docs/view?url=ya-disk-public%3A%2F%2Fca2iSjNkF84qhKovSZ7mzgmROUBDyuJh3z0YmGcvj%2FSctff0pb9ch0udBlbVKM9Rq%2FJ6bpmRyOJonT3VoXnDag%3D%3D%3A%2Flectures%2Flecture11_fmatcomp24.pdf&name=lecture11_fmatcomp24.pdf Презентация] [https://disk.yandex.ru/d/kcf1XRIZqHWncQ/Лекция%202024-04-05T08-09-12Z.mp4 Видео]
 +
# '''Матричные ряды''' (12.04.2024). Определение, критерий Коши. Ряд Неймана. Теория возмущений для линейных систем. Матричная экспонента. Матричные функции. [https://docs.yandex.ru/docs/view?url=ya-disk-public%3A%2F%2Fca2iSjNkF84qhKovSZ7mzgmROUBDyuJh3z0YmGcvj%2FSctff0pb9ch0udBlbVKM9Rq%2FJ6bpmRyOJonT3VoXnDag%3D%3D%3A%2Flectures%2Flecture12.pdf&name=lecture12.pdf&nosw=1 Доска] [https://disk.yandex.ru/d/kcf1XRIZqHWncQ/Лекция%202024-04-12T08-08-56Z.mp4 Видео]
 +
# '''Прямые методы решения линейных систем с плотными матрицами''' (15.04.2024). LU-разложение, LDL-разложение. Связь с методом Гаусса. Выбор ведущего элемента (pivoting). Разложение Холецкого. [https://docviewer.yandex.ru/?url=ya-disk-public%3A%2F%2Fca2iSjNkF84qhKovSZ7mzgmROUBDyuJh3z0YmGcvj%2FSctff0pb9ch0udBlbVKM9Rq%2FJ6bpmRyOJonT3VoXnDag%3D%3D%3A%2Flectures%2Flecture13.pdf&name=lecture13.pdf Доска] [https://disk.yandex.ru/d/kcf1XRIZqHWncQ/Лекция%2BСеминар%202024-04-15T13-21-20Z.mp4 Видео]
 +
 
  
 
=== Проверочные работы на семинарах ===  
 
=== Проверочные работы на семинарах ===  
Строка 45: Строка 66:
 
=== Домашние задания ===
 
=== Домашние задания ===
  
−
На курсе предусмотрены теоретические домашние задания и практические домашние задания на языке Python. Выдаются каждые 2-3 недели.
+
На курсе предусмотрены теоретические домашние задания и практические домашние задания на языке Python. Выдаются каждые 1-3 недели.
  
 
Каждый студент 2 раза за семестр может просрочить дедлайн ДЗ на 1 сутки. Чтобы использовать эту возможность, достаточно просто загрузить работу после дедлайна.
 
Каждый студент 2 раза за семестр может просрочить дедлайн ДЗ на 1 сутки. Чтобы использовать эту возможность, достаточно просто загрузить работу после дедлайна.
 +
 +
* '''Теоретическое ДЗ-1'''. Дедлайн: 10.02.24 в 23:59. [https://disk.yandex.ru/i/THEDq4XYLO6W5w Условие] [https://disk.yandex.ru/d/deGc7x2vxAeCXQ TeX]
 +
 +
* '''Практическое ДЗ-1'''. Дедлайн: 24.02.24 в 23:59. [https://disk.yandex.ru/d/BaNapyAyL2DZ8Q Условие]
 +
 +
* '''Теоретическое ДЗ-2'''. Дедлайн: 07.03.24 в 23:59. [https://disk.yandex.ru/i/12G1qx2DnPZsyg Условие] [https://disk.yandex.ru/d/nAGv0R87JdsiEA TeX]
 +
 +
* '''Практическое ДЗ-2'''. Дедлайн: 18.03.24 в 23:59. [https://disk.yandex.ru/d/nx4aOxDkM5BRqA Условие]
 +
 +
* '''Теоретическое ДЗ-3'''. Дедлайн: 03.04.24 в 23:59. [https://disk.yandex.ru/i/-j0SlXg5cY44cg Условие]
 +
 +
* '''Практическое ДЗ-3'''. Дедлайн: 10.04.24 в 23:59. [https://disk.yandex.ru/d/A0DehGVmWFBzkw Условие]
 +
 +
* '''Теоретическое ДЗ-4'''. Дедлайн: 29.04.24 в 23:59. [https://disk.yandex.ru/i/tYlh5mUMgcuU6g Условие] [https://disk.yandex.ru/d/PY7K5pbi5ESWXg TeX]
 +
 +
* '''Практическое ДЗ-4'''. Дедлайн: 16.05.24 в 23:59. [https://disk.yandex.ru/d/PspuCktG7WhgCg Условие]
 +
 +
=== Итоговая оценка за курс ===
 +
 +
Итог = Округление(min(10, 0.2 * ТДЗ + 0.15 * ПДЗ + 0.1 * БДЗ + 0.1 * ПР + 0.25 * К + 0.3 * Э))
 +
 +
Обратите внимание, что в 4-м модуле ТДЗ, ПДЗ, ПР являются средними оценками ''за оба модуля''.
 +
 +
* ТДЗ – средняя оценка за теоретические домашние задания.
 +
* ПДЗ – средняя оценка за практические домашние задания в Python.
 +
* БДЗ – средняя оценка за бонусные задачи.
 +
* ПР – средняя оценка за проверочные работы на семинарах.
 +
* К – оценка за коллоквиум.
 +
* Э – оценка за письменный экзамен, проводимый в конце 4-го модуля.
 +
 +
Округление арифметическое.
 +
 +
'''Автоматов не предусмотрено'''.
  
 
== Литература ==
 
== Литература ==

Текущая версия на 18:14, 30 апреля 2024

О курсе

Курс для студентов 2 курса в 3-4 модулях.

Первые лекция и семинары состоятся 19.01

Лектор: Рахуба Максим Владимирович

Семинаристы:

Группа Преподаватель Учебные ассистенты Чат в телеграм
1 Рахуба Максим Владимирович Максим Васильев, Андрей Аржанцев tg
2 Самсонов Сергей Владимирович Никита Козлов, Артем Малько tg
3 Ваня Пешехонов Иван Сидоренко, Тимофей Сенин tg
4 Кухарчук Иван Андреевич Егор Бугаев, Тимофей Сенин  ?
5 Сендерович Александра Леонидовна Алмасбек Стамбеков, Максим Захарченко tg
6 Медведь Никита Юрьевич Илья Дробышевский, Виктория Шварева, Максим Захарченко tg
7 Левин Илья Валерьевич Александр Гапонов, Артем Малько  ?

Полезные ссылки

Ведомость

Разбиение по группам

Телеграм-канал курса

Телеграм-чат курса

Папка с материалами

Неофициальный конспект лекций 2021-2022 от студента (могут быть ошибки)

Подготовленные билеты к коллоквиуму 2022-2023 от студентов (могут быть ошибки)

План курса

Если какие-то лекции не выложены или найдены ошибки на вики-странице - пишите @strange_guest.

  1. Основы матричного анализа (19.01.2024). Векторные и матричные нормы. Скалярное произведение и ортогональность. Разложение Шура. Слайды Запись Конспект (TeX)
  2. Малоранговое приближение матриц – 1 (26.01.2024). Нормальные матрицы. Знакоопределённые матрицы. Сингулярное разложение (SVD): доказательство существования, наивный алгоритм, связь с матричными нормами. Теорема Эккарта-Янга-Мирского. Слайды Запись Конспект (TeX)
  3. Малоранговое приближение матриц – 2 (02.02.2024). Скелетное разложение: разделение переменных и ранг, CUR-разложение и интерполяционная формула. Малоранговая арифметика: QR-разложение, преобразование скелетного разложения в SVD. Слайды Видео
  4. Малоранговое приближение матриц – 3 (09.02.2024). Ортопроекторы. Приближение образа матрицы. Простейший рандомизированный алгоритм поиска усечённого SVD. Доска Видео
  5. Малоранговое приближение матриц – 4 (16.02.2024). Alternating least squares (ALS). Матрично-векторное дифференцирование. Кронекерово произведение. Доска Видео
  6. Малоранговое приближение многомерных массивов (26.02.2024). Каноническое тензорное разложение. Разложение Таккера. Higher-order SVD. Доска Видео Конспект (TeX)
  7. Вычисление QR-разложения (01.03.2024). Отражения Хаусхолдера. Вращения Гивенса. Rank-revealing QR (RRQR). Доска Видео
  8. Метод наименьших квадратов и псевдообратные матрицы (11.03.2024). Полноранговый случай. Общий случай. Регуляризация. Доска Видео
  9. FFT и структурированные матрицы (15.03.2024). Быстрое преобразование Фурье (FFT). Циркулянты. Тёплицевы матрицы. Доска Видео
  10. FFT и структурированные матрицы – 2 (22.03.2024). FFT для произвольных n. Дискретная свёртка. FFT, тёплицевы матрицы, циркулянты в 2D. Дискретное косинус-преобразование (DCT). Доска Видео
  11. Умножение матриц, вычислительная устойчивость, обусловленность (05.04.2023). Метод Штрассена. BLAS. Машинные числа. Вычислительная устойчивость. Обусловленность. Презентация Видео
  12. Матричные ряды (12.04.2024). Определение, критерий Коши. Ряд Неймана. Теория возмущений для линейных систем. Матричная экспонента. Матричные функции. Доска Видео
  13. Прямые методы решения линейных систем с плотными матрицами (15.04.2024). LU-разложение, LDL-разложение. Связь с методом Гаусса. Выбор ведущего элемента (pivoting). Разложение Холецкого. Доска Видео


Проверочные работы на семинарах

На семинарах будут проходить короткие тесты (проверочные работы) по теме лекции и семинара с предыдущей недели.

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

На курсе предусмотрены теоретические домашние задания и практические домашние задания на языке Python. Выдаются каждые 1-3 недели.

Каждый студент 2 раза за семестр может просрочить дедлайн ДЗ на 1 сутки. Чтобы использовать эту возможность, достаточно просто загрузить работу после дедлайна.

  • Теоретическое ДЗ-1. Дедлайн: 10.02.24 в 23:59. Условие TeX
  • Практическое ДЗ-1. Дедлайн: 24.02.24 в 23:59. Условие
  • Теоретическое ДЗ-2. Дедлайн: 07.03.24 в 23:59. Условие TeX
  • Практическое ДЗ-2. Дедлайн: 18.03.24 в 23:59. Условие
  • Теоретическое ДЗ-3. Дедлайн: 03.04.24 в 23:59. Условие
  • Практическое ДЗ-3. Дедлайн: 10.04.24 в 23:59. Условие
  • Теоретическое ДЗ-4. Дедлайн: 29.04.24 в 23:59. Условие TeX
  • Практическое ДЗ-4. Дедлайн: 16.05.24 в 23:59. Условие

Итоговая оценка за курс

Итог = Округление(min(10, 0.2 * ТДЗ + 0.15 * ПДЗ + 0.1 * БДЗ + 0.1 * ПР + 0.25 * К + 0.3 * Э))

Обратите внимание, что в 4-м модуле ТДЗ, ПДЗ, ПР являются средними оценками за оба модуля.

  • ТДЗ – средняя оценка за теоретические домашние задания.
  • ПДЗ – средняя оценка за практические домашние задания в Python.
  • БДЗ – средняя оценка за бонусные задачи.
  • ПР – средняя оценка за проверочные работы на семинарах.
  • К – оценка за коллоквиум.
  • Э – оценка за письменный экзамен, проводимый в конце 4-го модуля.

Округление арифметическое.

Автоматов не предусмотрено.

Литература

1) Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations 4th Edition. The Johns Hopkins University Press. Baltimore.

2) Тыртышников, Е. Е. (2007). Методы численного анализа. Академия, Москва.

3) Trefethen, L. N., & Bau III, D. (1997). Numerical linear algebra. (Vol. 50). Siam. Philadelphia.

4) Demmel, James W. Applied numerical linear algebra. Society for Industrial and Applied Mathematics, 1997.

Источник — «http://wiki.cs.hse.ru/index.php?title=Основы_матричных_вычислений_2023/24&oldid=84909»