Основы матричных вычислений 2021/2022 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
м |
Esquerte (обсуждение | вклад) |
||
| (не показаны 54 промежуточные версии 6 участников) | |||
| Строка 4: | Строка 4: | ||
'''Лектор:''' Рахуба Максим Владимирович | '''Лектор:''' Рахуба Максим Владимирович | ||
| − | |||
| − | |||
'''Семинаристы:''' | '''Семинаристы:''' | ||
| Строка 12: | Строка 10: | ||
! Группа !! Преподаватель !! Учебный ассистент || Время начала семинара || Инвайт в anytask || Чат в телеграм || Консультации | ! Группа !! Преподаватель !! Учебный ассистент || Время начала семинара || Инвайт в anytask || Чат в телеграм || Консультации | ||
|- | |- | ||
| − | | 1 || Высоцкий Лев Игоревич || | + | | 1 || Высоцкий Лев Игоревич || Илья Анищенко || Пт, 11:10 || ecpmalC || [https://t.me/+G-elYeMh-q5iNjYy tg] || |
|- | |- | ||
| 2 || Рахуба Максим Владимирович || Михаил Петров || Пт, 09:30 || WaheRR2 || [https://t.me/+3c6szNe8E9E4NmQy tg] || | | 2 || Рахуба Максим Владимирович || Михаил Петров || Пт, 09:30 || WaheRR2 || [https://t.me/+3c6szNe8E9E4NmQy tg] || | ||
|- | |- | ||
| − | | 3 || Сушникова Дарья Алексеевна || Александр Демин || Пт, 11:10 || || [https://t.me/+9bx9m8279vAyYWYy tg] || | + | | 3 || Сушникова Дарья Алексеевна || Александр Демин || Пт, 11:10 || ZIeqosn || [https://t.me/+9bx9m8279vAyYWYy tg] || |
|- | |- | ||
| − | | 4 || Сушникова Дарья Алексеевна || Влад Княжевский || Пт, 09:30 || || [https://t.me/+4fUPIKLCPlVmMTky tg] || | + | | 4 || Сушникова Дарья Алексеевна || Влад Княжевский || Пт, 09:30 || yYBADOt || [https://t.me/+4fUPIKLCPlVmMTky tg] || |
|- | |- | ||
| − | | 5 || Медведь Никита Юрьевич || Дмитрий Лишуди || Вт, 11:10 || || [https://t.me/+xjDuK64sj_s5ODcy tg] || ? | + | | 5 || Медведь Никита Юрьевич || Дмитрий Лишуди || Вт, 11:10 || 6T48c6J || [https://t.me/+xjDuK64sj_s5ODcy tg] || ? |
|- | |- | ||
| 6 || Зароднюк Алёна Владимировна || Ира Голобородько || Вт, 11:10 || BjKRP6u || [https://t.me/+TEbCCgNqktU3ZjRi tg] || | | 6 || Зароднюк Алёна Владимировна || Ира Голобородько || Вт, 11:10 || BjKRP6u || [https://t.me/+TEbCCgNqktU3ZjRi tg] || | ||
| Строка 27: | Строка 25: | ||
=== Полезные ссылки === | === Полезные ссылки === | ||
| − | Телеграм-канал курса: [https://t.me/+u0U2pqXT4WE0NGEy | + | Телеграм-канал курса: [https://t.me/+u0U2pqXT4WE0NGEy t.me] |
| − | Телеграм-чат курса: [https://t.me/+eCqsF6E-UzI5MjVi | + | Телеграм-чат курса: [https://t.me/+eCqsF6E-UzI5MjVi t.me] |
| + | |||
| + | Таблица с оценками: [https://docs.google.com/spreadsheets/d/1zuBkOv1TLd5FK9LfyfnuirwON9Js4AoW2gn0grrvdcc/edit#gid=833242058 docs.google.com] | ||
Материалы курса: [https://disk.yandex.ru/d/rylf3xk13J4ztA disk.yandex.ru] | Материалы курса: [https://disk.yandex.ru/d/rylf3xk13J4ztA disk.yandex.ru] | ||
| − | Плейлист с | + | Плейлист с лекциями: [https://www.youtube.com/playlist?list=PLEwK9wdS5g0rSn5GRkyUBLw5FurjVy0yp youtube.com] |
| + | |||
| + | Плейлист с семинарами 2-й группы: [https://www.youtube.com/playlist?list=PLEwK9wdS5g0ooOooUYyzbhTu_6N7ycXvF youtube.com] | ||
| + | |||
| + | Неофициальный конспект лекций от Артёма: [https://nextcloud.codereptile.ru/index.php/s/Tn7DxZFDzwRQPDm nextcloud.codereptile.ru] | ||
== План курса == | == План курса == | ||
| Строка 39: | Строка 43: | ||
=== Лекции === | === Лекции === | ||
| − | + | # '''Основы матричного анализа''' (14.01.2022). Векторные и матричные нормы. Скалярное произведение и ортогональность. Разложение Шура. [https://disk.yandex.ru/i/IIvxT83Zl6ntpw Конспект] [https://youtu.be/Ko6r7Q4Jnz8 Видео (youtube)] [https://disk.yandex.ru/i/90mmYWp4Sy4JcQ Конспект (TeX)] | |
| − | + | # '''Малоранговое приближение матриц – 1''' (21.01.2022). Нормальные матрицы. Знакоопределённые матрицы. Сингулярное разложение (SVD): доказательство существования, наивный алгоритм, связь с матричными нормами. Теорема Эккарта-Янга-Мирского. [https://disk.yandex.ru/i/9VWiLWGimcQbzg Конспект] [https://www.youtube.com/watch?v=vXxADPKz_b0 Видео (youtube)] [https://disk.yandex.ru/i/tiW02SnyGxH__A Конспект (TeX)] | |
| − | + | # '''Малоранговое приближение матриц – 2''' (28.01.2022). Скелетное разложение: разделение переменных и ранг, CUR-разложение и интерполяционная формула. Малоранговая арифметика: QR-разложение, преобразование скелетного разложения в SVD. [https://disk.yandex.ru/i/orYYoneNleFQLQ Конспект] [https://zoom.us/rec/share/l6q8M4L682rKx5aVcidQEQAq3JMEv67yYK320PlNBBWFK_IUPZri05La0nPLxDlF.5k5bznR6401JqaSW Видео (zoom.us)] [https://youtu.be/UfTXNY7i8Ek Видео (youtube)] | |
| + | # '''Малоранговое приближение матриц – 3''' (04.02.2022). Ортопроекторы. Приближение образа матрицы. Простейший рандомизированный алгоритм поиска усечённого SVD. [https://disk.yandex.ru/i/5C2N3FXvMMZExQ Конспект] [https://zoom.us/rec/share/ZfW8cMQbLzqHt0NkEEMF95HtS3tcKO2FnJn4psz6tq5WI_e-eeVobyuR_S5jN4v8.2MfNKPJA2oJB1E0v?startTime=1643967927000 Видео (zoom.us)] [https://youtu.be/G-EGHRZXImI Видео (youtube)] | ||
| + | # '''Малоранговое приближение матриц – 4''' (11.02.2022). Alternating least squares (ALS). Матрично-векторное дифференцирование. Кронекерово произведение. [https://disk.yandex.ru/i/SO5hvmLd-AID-A Конспект] [https://zoom.us/rec/play/hBNoyzwFwD_cY7lnDQ95XqDulDoVXnzkGeyLl5GDLBJIxe90Wubix8Dk5wP-V4cOkHBYzeAZFYcRMN-I.QT_JGe_6sKYizBe6?startTime=1644572731000 Видео (zoom.us)] [https://youtu.be/gYQp_xuLppk Видео (youtube)] | ||
| + | # '''Малоранговое приближение многомерных массивов''' (18.02.2022). Каноническое тензорное разложение. Разложение Таккера. Higher-order SVD. [https://disk.yandex.ru/i/mh9PyT_QEqn7sg Конспект] [https://zoom.us/rec/play/gLtwlrvbPIcZ_ykNJe_Ehmx6ubIo4of_x2kBchDuPRVLAGYFIsQ20f_yABwi8iqfHfpzhEZy495s-JT5.6TDQuJvrLjcusUTP Видео (zoom.us)] [https://youtu.be/nnqVzdUopko Видео (youtube)] | ||
| + | # '''Вычисление QR-разложения''' (25.02.2022). Отражения Хаусхолдера. Вращения Гивенса. Rank-revealing QR (RRQR). [https://disk.yandex.ru/i/VGGPHM8Gs7QnQg Конспект] [https://zoom.us/rec/play/ePZWHHNY9WeKV09YTNg6OeojRlYDU3fe7nsKz92texsTighD2es7d7ZCPy6RFizQ6fRTLlcBmjCuk9uh.aSw0CzKfOnwQD9fs Видео (zoom.us)] [https://youtu.be/gG5D0ZkLCTk Видео (youtube)] | ||
| + | # '''Метод наименьших квадратов и псевдообратные матрицы''' (04.03.2022). Полноранговый случай. Общий случай. Регуляризация. [https://disk.yandex.ru/i/7WnRgjPjDb3nrQ Конспект] [https://zoom.us/rec/share/jpqczk61nIXYdqXbDvblwQRW_oI8Nra6WLVWcuXzcYGgTtReInr1fBAX_T2inpia.QOImTcwLuWi86lfo?startTime=1646387105000 Видео (zoom.us)] [https://youtu.be/T11F_C8wGkQ Видео (youtube)] | ||
| + | # '''FFT и структурированные матрицы''' (11.03.2022). Быстрое преобразование Фурье (FFT). Циркулянты. Тёплицевы матрицы. [https://disk.yandex.ru/i/mowg4aJpB2H4Bw Конспект] [https://youtu.be/906JLb3aAkQ Видео (youtube)] | ||
| + | # '''FFT и структурированные матрицы – 2''' (18.03.2022). FFT для произвольных n. Дискретная свёртка. FFT, тёплицевы матрицы, циркулянты в 2D. Дискретное косинус-преобразование (DCT). [https://disk.yandex.ru/i/mmX6VFAqFcOGAA Конспект] [https://zoom.us/rec/share/Hv4RBdR46AeWmZi2WsDCWsnykosEWeTzttI9jFF8-a1YEVx8_YMODSiCqZMuMxE.pZ2W9hph7dIIs2Xp?startTime=1647596739000 Видео (zoom.us)] [https://youtu.be/b2JFHqCbm74 Видео (youtube)] | ||
| + | # '''Умножение матриц и вычислительная устойчивость''' (06.04.2022). Метод Штрассена. BLAS. Машинные числа. Вычислительная устойчивость. Обусловленность. [https://disk.yandex.ru/i/e3OE5EEhi7gbyw Презентация] [https://us06web.zoom.us/rec/share/LiIqMsR0llK1Eg_l9G6J2wJ4-va-IzOClY8G-Jz-_UrDd5HYnsLuW9UX5rAqno1z.PkknvV_pR3eLOQq0 Видео (zoom.us)] [https://youtu.be/4BnDSccgc8U Видео (youtube)] | ||
| + | # '''Матричные ряды''' (08.04.2022). Определение, критерий Коши. Ряд Неймана. Теория возмущений для линейных систем. Матричная экспонента. Матричные функции. [https://disk.yandex.ru/i/6T_-bxlyGRU7Vg Конспект] [https://us06web.zoom.us/rec/share/i-3aGrTq1ZlJI86Qov1yc7uhtx29pLs2mhdW37IfKPCvTZ-TPeNMElZblHrIJ7Z3.7lotWfgDT3axI4zi?startTime=1649411827000 Видео (zoom.us)] [https://youtu.be/8zPPowwCRuw Видео (youtube)] | ||
| + | # '''Прямые методы решения линейных систем с плотными матрицами''' (15.04.2022). LU-разложение, LDL-разложение. Связь с методом Гаусса. Выбор ведущего элемента (pivoting). Разложение Холецкого. [https://disk.yandex.ru/i/cURgrFOjTndTNA Конспект] [https://us06web.zoom.us/rec/share/YNY0UQw-AFYLJ6wVJ1cRU7HpL83QmMS6R56jT-9kdXMzIublTngoHm8HOMYmst9X.MUMLDmpyumpcyhBp?startTime=1650016192000 Видео (zoom.us)] [https://youtu.be/FMtci0ypU60 Видео (youtube)] | ||
| + | # '''Прямые методы решения линейных систем с разреженными матрицами''' (22.04.2022). Формула Шермана-Моррисона, тождество Вудберри. Разреженные матрицы: заполнения в L и U. Алгоритмы поиска P (матрицы перестановки). [https://disk.yandex.ru/i/c1OqWHy6bA18yw Конспект] [https://us06web.zoom.us/rec/play/1iUsmRSIo5pPTzrxDB4iB9lFOJ01YShamrJdKnDFFL0BdXApechwwcGbjfCPx-outLjhXX3OFpSfNhSn.u3fDzyujeCrSdqiz?startTime=1650620725000 Видео (zoom.us)] [https://youtu.be/Y0Cwm4Vgdi4 Видео (youtube)] | ||
| + | # '''Итерационные методы решения линейных систем''' (29.04.2022). Одношаговые методы: метод простой итерации, градиентный спуск, метод Чебышёва. [https://disk.yandex.ru/i/EGC5Fj5H8WYucg Презентация] [https://us06web.zoom.us/rec/play/iDEj9La4JYiz0vdyom11cn3rcdGixY3CnlVSdKT2bJR6fROwqPZXo-_oQmDMTJln3lUuk1wuJFOWf3zp.rsJLYIL1mb52wIDE?startTime=1651226019000 Видео (zoom.us)] [https://youtu.be/Okssj7JBXlI Видео (youtube)] | ||
| + | # '''Итерационные методы решения линейных систем – 2''' (13.05.2022). Оптимизация на подпространствах Крылова. Метод сопряжённых градиентов. [https://disk.yandex.ru/i/Pz1HtTqA8L3SMg Конспект] [https://us06web.zoom.us/rec/share/bpi0bue_WXpSB25dGGqRKJ6Q4vdedPHiz3RcyB9yGAqup_1Brz__GyTIbL-6JyIJ.TpJAYyxf543IYaq3?startTime=1652435713000 Видео (zoom.us, часть 1)] [https://us06web.zoom.us/rec/share/bpi0bue_WXpSB25dGGqRKJ6Q4vdedPHiz3RcyB9yGAqup_1Brz__GyTIbL-6JyIJ.TpJAYyxf543IYaq3?startTime=1652441204000 Видео (zoom.us, часть 2)] [https://youtu.be/-Wok-D7rtUU Видео (youtube)] | ||
| + | # '''Итерационные методы решения линейных систем – 3''' (20.05.2022). Сходимость CG. GMRES. Предобуславливание. [https://disk.yandex.ru/i/ik0sVFqiLAYtyQ Презентация] [https://us06web.zoom.us/rec/share/xMb0jzGdAHPSPYEfsoTtSK9D5z39M4sC-9g-CYdkXKggLj_4jQMDZwYiicQhZA2B.DOo-SWkw3c0kqHQW?startTime=1653040598000 Видео (zoom.us)] [https://youtu.be/aC6z_gfX0j0 Видео (youtube)] | ||
| + | # '''Методы решения частичной задачи на собственные значения''' (27.05.2022). Eigenvalue problem как задача оптимизации. Степенной метод. Метод Релея-Ритца. Методы Ланцоша и Арнольди. [https://disk.yandex.ru/d/RlNCY-fZMHDqHw Конспект] [https://us06web.zoom.us/rec/share/g5anJURAqh1jgSZUmUfhr0YUo7NLbug4Yd1dpUmqVa-QvLe1H1YwTeiWzjqRII1r.b0e8fd0dBykxh20z?startTime=1653644726000 Видео (zoom.us)] [https://youtu.be/bqezn9wzA7I Видео (youtube)] | ||
| + | # '''Методы решения частичной и полной задач на собственные значения''' (03.06.2022). Числа Ритца в методе Ланцоша. QR-алгоритм. [https://disk.yandex.ru/i/0l4uzDHVatjxdA Конспект] [https://us06web.zoom.us/rec/share/SakkSQ6kB6vJ7nTd4kG98_gTHKRH8U7RKxCJ0CXO-P9Y6YlAlribNedH35MFHPj4.Uqzlpx048JLSCiL6?startTime=1654250018000 Видео (zoom.us)] [https://youtu.be/_-hhhxmaKmo Видео (youtube)] | ||
| + | # '''Теория возмущений''' (10.06.2022). Алгоритм для SVD. 1-я и 2-я теоремы Гершгорина. Теорема Бауэра-Файка. Число обусловленности для отдельный собственных значений. [https://disk.yandex.ru/i/MQO2hoeNUyEV0A Конспект] [https://us06web.zoom.us/rec/share/bU3q29d6lZXhGl0lky9OWMeOERO2kIJV34vSigUHlbVvegSMhfILboGk06UdlI88.w6P2QX1nnBB4QHeB?startTime=1654854320000 Видео (zoom.us)] [https://youtu.be/tiLPidM4bME Видео (youtube)] | ||
| + | # '''Сингулярные числа свёрточных слоёв''' (доп. лекция, 17.06.2022). Константа Липшица для нейронных сетей. Неточные методы поиска. Точные методы и оценки. [https://disk.yandex.ru/i/AcRDCPT6Bc_3xg Конспект] [https://us06web.zoom.us/rec/share/VLB43uFMZu-o8dYzdltddhAMrA5otPOe23m5HpmvPGlINm6Re_oX2VqwmSmMxnji.lCAJKjhjBkST_XUf Видео (zoom.us)] | ||
=== Проверочные работы на семинарах === | === Проверочные работы на семинарах === | ||
| − | Каждые 1-2 недели на семинарах | + | Каждые 1-2 недели на семинарах будут проходить короткие тесты по теме лекции и семинара с предыдущей недели. |
На первом семинаре пройдет пробный тест, за который не будет выставляться баллов. | На первом семинаре пройдет пробный тест, за который не будет выставляться баллов. | ||
Подробнее о правилах проведения будет рассказано на первом семинаре. | Подробнее о правилах проведения будет рассказано на первом семинаре. | ||
| Строка 53: | Строка 75: | ||
На курсе предусмотрены теоретические домашние задания и практические домашние задания на языке Python. Выдаются каждые 2-3 недели. | На курсе предусмотрены теоретические домашние задания и практические домашние задания на языке Python. Выдаются каждые 2-3 недели. | ||
| − | У каждого студента есть | + | У каждого студента есть трое суток суммарно, на которые можно продлить срок сдачи любых заданий. Чтобы использовать эту возможность, достаточно просто загрузить работу в anytask после дедлайна. |
* '''Теоретическое ДЗ-1'''. Дедлайн: 06.02.22 в 23:59. [https://disk.yandex.ru/i/maDXz7-lSb1zYw Условие] [https://disk.yandex.ru/d/pdhDZE2SHTxKGQ TeX] | * '''Теоретическое ДЗ-1'''. Дедлайн: 06.02.22 в 23:59. [https://disk.yandex.ru/i/maDXz7-lSb1zYw Условие] [https://disk.yandex.ru/d/pdhDZE2SHTxKGQ TeX] | ||
* '''Практическое ДЗ-1'''. Дедлайн: 17.02.22 в 23:59. [https://disk.yandex.ru/d/V0gba6JQ7DpxSQ Условие] | * '''Практическое ДЗ-1'''. Дедлайн: 17.02.22 в 23:59. [https://disk.yandex.ru/d/V0gba6JQ7DpxSQ Условие] | ||
| + | |||
| + | * '''Теоретическое ДЗ-2'''. Дедлайн: 28.02.22 в 23:59. [https://disk.yandex.ru/i/PoaniM3ijMrH6w Условие] [https://disk.yandex.ru/d/tvC0Onp2HVv2RA TeX] | ||
| + | |||
| + | * '''Практическое ДЗ-2'''. Дедлайн: 13.03.22 в 23:59. [https://disk.yandex.ru/d/Wu7xqOagVGGwMg Условие] | ||
| + | |||
| + | * '''Теоретическое ДЗ-3'''. Дедлайн: 21.03.22 в 23:59. [https://disk.yandex.ru/i/9YNdA48go0CXAw Условие] [https://disk.yandex.ru/d/b3UiChRvQWUTWA TeX] | ||
| + | |||
| + | * '''Практическое ДЗ-3'''. Дедлайн: 13.04.22 в 23:59. [https://disk.yandex.ru/d/yashQooHlZeO4A Условие] [https://disk.yandex.ru/d/VDSLkN3aMt2GmQ Папка с данными] | ||
| + | |||
| + | * '''Теоретическое ДЗ-4'''. Дедлайн: 30.04.22 в 23:59. [https://disk.yandex.ru/i/FulZ-y_WG1bc_Q Условие] [https://disk.yandex.ru/d/mz0ozvPNf-3_iA TeX] | ||
| + | |||
| + | * '''Практическое ДЗ-4'''. Дедлайн: 18.05.22 в 23:59. [https://disk.yandex.ru/d/1v-Rzg7MQn8mWQ Условие] [https://disk.yandex.ru/d/gpCqVZeZh5q_lg Папка с данными] | ||
| + | |||
| + | * '''Теоретическое ДЗ-5'''. Дедлайн: 26.05.22 в 23:59. [https://disk.yandex.ru/i/4preghNbmnWaPQ Условие] [https://disk.yandex.ru/d/n-aRnL4uViN_Gw TeX] | ||
| + | |||
| + | * '''Практическое ДЗ-5'''. Дедлайн: 09.06.22 в 23:59. [https://disk.yandex.ru/d/ZF31ISNhCqYq2w Условие] | ||
| + | |||
| + | * '''Теоретическое ДЗ-6'''. Дедлайн: 18.06.22 в 23:59. [https://disk.yandex.ru/i/ybpwV_2aR4-WNw Условие] [https://disk.yandex.ru/d/Dm9-smgcWbkfFg TeX] | ||
=== Контрольная работа === | === Контрольная работа === | ||
| + | Контрольная работа пройдет очно 25 апреля, начало: 18:10, время написания: 120 минут. О разбиении по аудиториям мы сообщим отдельно. Для студентов на дистанте мы предусмотрим написание в онлайн формате. [https://t.me/c/1668317399/53 Подробности] | ||
=== Экзамен === | === Экзамен === | ||
| − | + | Экзамен пройдет очно 28 июня (вторник), начало: 11:00, время написания: 150 минут. О разбиении по аудиториям мы сообщим отдельно. Для студентов на официальном дистанте мы предусмотрим написание в онлайн формате. [https://t.me/c/1668317399/81 Подробности] | |
=== Итоговая оценка за курс === | === Итоговая оценка за курс === | ||
| − | 3 модуль | + | '''3 модуль''': |
| − | + | ||
Итог = Округление(min(10, 0.4 * ТДЗ + 0.3 * ПДЗ + 0.2 * ПР + 0.1 * ФПР + 0.1 * БДЗ)) | Итог = Округление(min(10, 0.4 * ТДЗ + 0.3 * ПДЗ + 0.2 * ПР + 0.1 * ФПР + 0.1 * БДЗ)) | ||
| − | 4 модуль | + | '''4 модуль''': |
| − | + | ||
Итог = Округление(min(10, 0.2 * ТДЗ + 0.15 * ПДЗ + 0.1 * ПР + 0.05 * ФПР + 0.2 * КР + 0.3 * Э + 0.1 * БДЗ)) | Итог = Округление(min(10, 0.2 * ТДЗ + 0.15 * ПДЗ + 0.1 * ПР + 0.05 * ФПР + 0.2 * КР + 0.3 * Э + 0.1 * БДЗ)) | ||
| − | Обратите внимание, что в 4-м модуле ТДЗ, ПДЗ, ПР являются средними оценками за оба модуля | + | Обратите внимание, что в 4-м модуле ТДЗ, ПДЗ, ПР являются средними оценками ''за оба модуля''. |
| − | ТДЗ – средняя оценка за теоретические домашние задания | + | * ТДЗ – средняя оценка за теоретические домашние задания |
| − | ПДЗ – средняя оценка за практические домашние задания в Python | + | * ПДЗ – средняя оценка за практические домашние задания в Python |
| − | БДЗ – средняя оценка за бонусные задачи | + | * БДЗ – средняя оценка за бонусные задачи |
| − | ПР – средняя оценка за проверочные работы (до 10 минут), проводимые каждые 1-2 недели на семинарах | + | * ПР – средняя оценка за проверочные работы (до 10 минут), проводимые каждые 1-2 недели на семинарах |
| − | ФПР – оценка за финальную проверочную работу, которая проводится в конце 3-го модуля | + | * ФПР – оценка за финальную проверочную работу, которая проводится в конце 3-го модуля |
| − | КР – оценка за письменную контрольную работу, включающую теоретические вопросы и задачи | + | * КР – оценка за письменную контрольную работу, включающую теоретические вопросы и задачи |
| − | Э – оценка за письменный экзамен, проводимый в конце 4-го модуля | + | * Э – оценка за письменный экзамен, проводимый в конце 4-го модуля |
Округление арифметическое. | Округление арифметическое. | ||
| − | Автоматов не предусмотрено | + | '''Автоматов не предусмотрено'''. |
== Литература == | == Литература == | ||
Текущая версия на 11:45, 25 июня 2022
Содержание
О курсе
Курс для студентов 2 курса в 3-4 модулях.
Лектор: Рахуба Максим Владимирович
Семинаристы:
| Группа | Преподаватель | Учебный ассистент | Время начала семинара | Инвайт в anytask | Чат в телеграм | Консультации |
|---|---|---|---|---|---|---|
| 1 | Высоцкий Лев Игоревич | Илья Анищенко | Пт, 11:10 | ecpmalC | tg | |
| 2 | Рахуба Максим Владимирович | Михаил Петров | Пт, 09:30 | WaheRR2 | tg | |
| 3 | Сушникова Дарья Алексеевна | Александр Демин | Пт, 11:10 | ZIeqosn | tg | |
| 4 | Сушникова Дарья Алексеевна | Влад Княжевский | Пт, 09:30 | yYBADOt | tg | |
| 5 | Медведь Никита Юрьевич | Дмитрий Лишуди | Вт, 11:10 | 6T48c6J | tg | ? |
| 6 | Зароднюк Алёна Владимировна | Ира Голобородько | Вт, 11:10 | BjKRP6u | tg |
Полезные ссылки
Телеграм-канал курса: t.me
Телеграм-чат курса: t.me
Таблица с оценками: docs.google.com
Материалы курса: disk.yandex.ru
Плейлист с лекциями: youtube.com
Плейлист с семинарами 2-й группы: youtube.com
Неофициальный конспект лекций от Артёма: nextcloud.codereptile.ru
План курса
Лекции
- Основы матричного анализа (14.01.2022). Векторные и матричные нормы. Скалярное произведение и ортогональность. Разложение Шура. Конспект Видео (youtube) Конспект (TeX)
- Малоранговое приближение матриц – 1 (21.01.2022). Нормальные матрицы. Знакоопределённые матрицы. Сингулярное разложение (SVD): доказательство существования, наивный алгоритм, связь с матричными нормами. Теорема Эккарта-Янга-Мирского. Конспект Видео (youtube) Конспект (TeX)
- Малоранговое приближение матриц – 2 (28.01.2022). Скелетное разложение: разделение переменных и ранг, CUR-разложение и интерполяционная формула. Малоранговая арифметика: QR-разложение, преобразование скелетного разложения в SVD. Конспект Видео (zoom.us) Видео (youtube)
- Малоранговое приближение матриц – 3 (04.02.2022). Ортопроекторы. Приближение образа матрицы. Простейший рандомизированный алгоритм поиска усечённого SVD. Конспект Видео (zoom.us) Видео (youtube)
- Малоранговое приближение матриц – 4 (11.02.2022). Alternating least squares (ALS). Матрично-векторное дифференцирование. Кронекерово произведение. Конспект Видео (zoom.us) Видео (youtube)
- Малоранговое приближение многомерных массивов (18.02.2022). Каноническое тензорное разложение. Разложение Таккера. Higher-order SVD. Конспект Видео (zoom.us) Видео (youtube)
- Вычисление QR-разложения (25.02.2022). Отражения Хаусхолдера. Вращения Гивенса. Rank-revealing QR (RRQR). Конспект Видео (zoom.us) Видео (youtube)
- Метод наименьших квадратов и псевдообратные матрицы (04.03.2022). Полноранговый случай. Общий случай. Регуляризация. Конспект Видео (zoom.us) Видео (youtube)
- FFT и структурированные матрицы (11.03.2022). Быстрое преобразование Фурье (FFT). Циркулянты. Тёплицевы матрицы. Конспект Видео (youtube)
- FFT и структурированные матрицы – 2 (18.03.2022). FFT для произвольных n. Дискретная свёртка. FFT, тёплицевы матрицы, циркулянты в 2D. Дискретное косинус-преобразование (DCT). Конспект Видео (zoom.us) Видео (youtube)
- Умножение матриц и вычислительная устойчивость (06.04.2022). Метод Штрассена. BLAS. Машинные числа. Вычислительная устойчивость. Обусловленность. Презентация Видео (zoom.us) Видео (youtube)
- Матричные ряды (08.04.2022). Определение, критерий Коши. Ряд Неймана. Теория возмущений для линейных систем. Матричная экспонента. Матричные функции. Конспект Видео (zoom.us) Видео (youtube)
- Прямые методы решения линейных систем с плотными матрицами (15.04.2022). LU-разложение, LDL-разложение. Связь с методом Гаусса. Выбор ведущего элемента (pivoting). Разложение Холецкого. Конспект Видео (zoom.us) Видео (youtube)
- Прямые методы решения линейных систем с разреженными матрицами (22.04.2022). Формула Шермана-Моррисона, тождество Вудберри. Разреженные матрицы: заполнения в L и U. Алгоритмы поиска P (матрицы перестановки). Конспект Видео (zoom.us) Видео (youtube)
- Итерационные методы решения линейных систем (29.04.2022). Одношаговые методы: метод простой итерации, градиентный спуск, метод Чебышёва. Презентация Видео (zoom.us) Видео (youtube)
- Итерационные методы решения линейных систем – 2 (13.05.2022). Оптимизация на подпространствах Крылова. Метод сопряжённых градиентов. Конспект Видео (zoom.us, часть 1) Видео (zoom.us, часть 2) Видео (youtube)
- Итерационные методы решения линейных систем – 3 (20.05.2022). Сходимость CG. GMRES. Предобуславливание. Презентация Видео (zoom.us) Видео (youtube)
- Методы решения частичной задачи на собственные значения (27.05.2022). Eigenvalue problem как задача оптимизации. Степенной метод. Метод Релея-Ритца. Методы Ланцоша и Арнольди. Конспект Видео (zoom.us) Видео (youtube)
- Методы решения частичной и полной задач на собственные значения (03.06.2022). Числа Ритца в методе Ланцоша. QR-алгоритм. Конспект Видео (zoom.us) Видео (youtube)
- Теория возмущений (10.06.2022). Алгоритм для SVD. 1-я и 2-я теоремы Гершгорина. Теорема Бауэра-Файка. Число обусловленности для отдельный собственных значений. Конспект Видео (zoom.us) Видео (youtube)
- Сингулярные числа свёрточных слоёв (доп. лекция, 17.06.2022). Константа Липшица для нейронных сетей. Неточные методы поиска. Точные методы и оценки. Конспект Видео (zoom.us)
Проверочные работы на семинарах
Каждые 1-2 недели на семинарах будут проходить короткие тесты по теме лекции и семинара с предыдущей недели. На первом семинаре пройдет пробный тест, за который не будет выставляться баллов. Подробнее о правилах проведения будет рассказано на первом семинаре.
Домашние задания
На курсе предусмотрены теоретические домашние задания и практические домашние задания на языке Python. Выдаются каждые 2-3 недели.
У каждого студента есть трое суток суммарно, на которые можно продлить срок сдачи любых заданий. Чтобы использовать эту возможность, достаточно просто загрузить работу в anytask после дедлайна.
- Практическое ДЗ-1. Дедлайн: 17.02.22 в 23:59. Условие
- Практическое ДЗ-2. Дедлайн: 13.03.22 в 23:59. Условие
- Практическое ДЗ-3. Дедлайн: 13.04.22 в 23:59. Условие Папка с данными
- Практическое ДЗ-4. Дедлайн: 18.05.22 в 23:59. Условие Папка с данными
- Практическое ДЗ-5. Дедлайн: 09.06.22 в 23:59. Условие
Контрольная работа
Контрольная работа пройдет очно 25 апреля, начало: 18:10, время написания: 120 минут. О разбиении по аудиториям мы сообщим отдельно. Для студентов на дистанте мы предусмотрим написание в онлайн формате. Подробности
Экзамен
Экзамен пройдет очно 28 июня (вторник), начало: 11:00, время написания: 150 минут. О разбиении по аудиториям мы сообщим отдельно. Для студентов на официальном дистанте мы предусмотрим написание в онлайн формате. Подробности
Итоговая оценка за курс
3 модуль: Итог = Округление(min(10, 0.4 * ТДЗ + 0.3 * ПДЗ + 0.2 * ПР + 0.1 * ФПР + 0.1 * БДЗ))
4 модуль: Итог = Округление(min(10, 0.2 * ТДЗ + 0.15 * ПДЗ + 0.1 * ПР + 0.05 * ФПР + 0.2 * КР + 0.3 * Э + 0.1 * БДЗ))
Обратите внимание, что в 4-м модуле ТДЗ, ПДЗ, ПР являются средними оценками за оба модуля.
- ТДЗ – средняя оценка за теоретические домашние задания
- ПДЗ – средняя оценка за практические домашние задания в Python
- БДЗ – средняя оценка за бонусные задачи
- ПР – средняя оценка за проверочные работы (до 10 минут), проводимые каждые 1-2 недели на семинарах
- ФПР – оценка за финальную проверочную работу, которая проводится в конце 3-го модуля
- КР – оценка за письменную контрольную работу, включающую теоретические вопросы и задачи
- Э – оценка за письменный экзамен, проводимый в конце 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.
