Третий курс. I.N.S.E.(СТ)/22--

1. Остальное
2. Обещанное
3. Лекции
1. 2021.02.08: лекция #1
2. 2021.02.15: лекция #2
3. 2021.02.22: лекция #3
4. 2021.03.01: лекция #4
4. Вопросы

Курс читается по понедельникам, 16:00—19:00, аудитория 27.

В конце курса — зачёт. Вопросы — будут (заранее), можно будет выбрать (заранее). Что не исключает знания всего расказанного и моего желания об этом поговорить.

Рассказать о DWDM/CWDM.

Было общефилософское введение «про это»: как лучше программировать, как лучше не программировать, чем можно заниматься, как можно заниматься, ….

Кратко обсудили вопросы обычной (коммутативной и ассоциативной) алгебры и отношений порядка/эквивалентности. Поговорили про целые числа: их представление в разных системах счисления (с фиксированным основанием p), про важность единственности представления и возможные условия на коэффициенты разложения (нуля). Доказали единственность стандартного представления. Вопросами существования не занимались.

Хотел рассказать анекдот, но забыл, какой именно.

Чуть-чуть поговорили о конструктивном доказательстве существования канонического разложения целого числа по системе степеней основания p и том, откуда у нас берётся остаток от деления на p, да что именно его существование/единственность означают.

Слегка отвлёкся на разговоры про ОС Plan 9, парадигму «всё суть файл», devfs/mknod и абстрактность понятия «файл устройства», просьбу Максима Храмцова рассказать людям об IPC посредством общей памяти, семафоры, mutex-ы и условные переменные. Также — про пути от sockets к MPI и pthreads ⇒ OpenMP да возможном слиянии этих понятий в Plan 9. Ну и о Rob Pike, AT&T, Nokia, Microsoft да реализацию конвейера в MS-DOS.

После этого начали обсуждать сумматор двоичных чисел. Построили модель его поведения, поняли про входы-выходы, нарисовали таблицу деятельности. При обсуждении цепочки сумматоров неожиданно поговорили о time-division multiplexing, space-division multiplexing и их смешанной версии. Обещал в некий момент курса рассказать о DWDM/CWDM.

Поняли, что суммирование у нас — в ℤ_2^N+1. Объяснил, что умножение будет ничуть не лучше, так что очень интересно, у, скажем, какого первого N! вычисляемое значение будет чистым нулём. И кто, таким образом, будет его делителями. Легонько (не больно пока, то есть) пояснил за факторизацию и дискретный логарифм. Обещал, что будут гражданам читать криптографию. Хм, а если не будут? Придётся за базар ответить и самому читать? OK, подумаю под/над этим и над/под базаром.

Помянул тензор электромагнитного поля, F_μν = ∂_μA_ν - ∂_νA_μ в контексте «а чего это у нас везде сейчас последовательная шина SATA/SAS, если параллельные шины на первый взгляд быстрее». Вспомнил о геометрическом смысле d² = 0: «у границы нет границы».

Обсудили что же такое вычисление условий (как отображение несчётного множества условий в пространство T/F ≡ Bool), операции «И» «ИЛИ», «XOR» и «НЕ» как отображения  Bool²→Bool и  Bool→Bool соответственно. Поговорили про композицию этих отображений, отрицание сложных условий и связь таких бинарных и унарных операций с операциями над множествами.

Поговорили про побитовые операции AND, OR, XOR и NOT. Обсудили действие (или не действие) на различные биты масок посредством трёх упомянутых бинарных операций.

Стали собирать сумматор на основе AND, OR, XOR и NOT. Продвинулись до понимания, как из a_k, b_k, c_k полностью получить R_k, но с C_k продвинулись только до случая получения его при c_k = 0. Разобрав, впрочем, популярные, но неправильные пути формирования общего ответа. Договорились, что граждане потренируются дома, а в начале новой лекции обсудим полученное и построим ответ.

Следующая лекция продолжится конструированием XOR посредством трёх других (основных?) побитовых/логических операторов, а дальше — как пойдёт.

Пояснил семантическое ядро XOR примером «или трусы надеть, или крестик снять».

Снимали на видео. Ощущаю себя звездой. Лечу.

Обсудили, что знание того, как с точки зрения алгебры и арифметики действуют XOR и AND, помогает построить правильный сумматор. Обсудили, что может быть хорошего из факта, что для формирования одного из элементов сумматора можно брать хоть XOR, хоть OR.

Поговорили об алгоритме быстрого умножения, предварив его обсуждением простой реализации умножения двух чисел (с помощью сложения числа с собой известное количество раз); «ловил» обучающихся на логичные, но не всегда правильные оптимизации. Получили логарифмическую оценку скорости работы.

Немного начали обсуждать, что умножаемые объекты могут иметь неодинаковую природу: вспомнил про умножение в векторных полях, помянул бесконечномерную версию ЛВП, в котором длины векторов нормируются (в конце вычислений) на какую-то заданную величину. Чуть-чуть попенял, что квантовые компьютеры — «уже тут», а квантовую механику знают почему-то не все. На том и разошлись.

Поговорил об оценке быстродействия алгоритма умножения, посчитали полное время его работы (когда известны времена выполнения сдвигов, ветвлений и сложений). Напомнил, что такое O-нотация и чем могут быть плохи асимптотические оценки, когда не попадаешь в интервал, который асимптотикой описывается.

Отвлёкся на неаналитическое поведение алгоритмов (приводил в пример NAG, объяснял, как интегро-дифференциальные уравнения преобразуются в матричный вид и что из этого следует в плане линейной алгебры). Про ряды Тейлора и аналитичность функций комплексного переменного поговорили.

Ещё раз напомнил, что такое концевая рекурсия (tail recursion) и как она преобразовывается в циклы. Поговорил про операции с побочными эффектами (side effects) на примере (a <<= 1; a >>= 1) и (a >>= 1; a <<= 1)

Обсудили, что можно сделать с возведением в степень, если знаешь алгоритм быстрого умножения. Более абстрактно сформулировал требования на оба операнда (a и b).

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

В начале лекции относительно грязно ругался. В конце был анекдот про «ровно в 19:00, а с тобой или без — это сам решай».

У матросов они уже есть?