Complex Analysis на собеседовании

В 1932 году Гарри Найквист в Bell Labs опубликовал *Regeneration Theory* - и принцип аргумента Коши 1855 года стал инженерной нормой для проектирования усилителей. В 1965-м Джеймс Кули и Джон Тьюки за шесть страниц в *Mathematics of Computation* подарили миру FFT, опершись на симметрию корней из единицы $\omega^k$. На технических интервью в Apple Silicon, Qualcomm, Google Speech, Cadence типичный вопрос: 'Полюс IIR-фильтра на $z = 0.9 e^{i\pi/4}$ - устойчив? Какая частота резонанса?'. Кандидат, который умеет читать $z$-плоскость, отвечает за 30 секунд. Кандидат без комплексного анализа теряет offer.

• **Apple Silicon DSP-team:** обязательные вопросы на интервью - устойчивость IIR-биквадратов, ROC, обратное Z-преобразование через вычеты
• **Codeforces Div1 D/E:** задачи на умножение многочленов длины $10^5$ - решаются только через NTT по модулю $998\,244\,353 = 119 \cdot 2^{23} + 1$
• **Cadence Spectre (RF-симулятор):** критерий Найквиста для устойчивости PLL и phase-noise анализа - индустриальный стандарт
• **Google Speech (WaveNet, Lyra):** анализ stability цифровых вокодеров через $z$-плоскость - вопрос на phone screen для DSP-инженеров

Предварительные знания

• Complex Analysis in Computer Science

Аналитические функции в обработке сигналов (DSP-интервью)

На интервью в компании, работающие с DSP (Qualcomm, Texas Instruments, Apple Silicon, Google), часто спрашивают о Z-преобразовании, полюсах передаточной функции и связи с комплексным анализом. Знание базовых концептов отличает кандидата.

**Типичные вопросы DSP-интервью:** 1. "Где должны находиться полюсы H(z) для устойчивости?" → Внутри единичного круга |z| < 1 2. "Что такое ROC и как связан с причинностью?" → ROC: |z| > max|pₖ| для причинного фильтра 3. "Как ОБРАТНОЕ Z-преобразование вычисляется?" → Вычетами: x[n] = Σ Res(H(z)·zⁿ⁻¹, zₖ) 4. "Что такое частотная характеристика?" → H(e^{jω}) = H(z)|_{z=e^{jω}}-Z-transform на единичной окружности

Критерий Найквиста и критерий устойчивости

Критерий устойчивости Найквиста-приложение принципа аргумента комплексного анализа к анализу замкнутых систем управления. Это часто встречается на интервью в robotics, embedded и control systems.

**Принцип аргумента (напоминание):** ∮ f'(z)/f(z) dz = 2πi(N − P) где N-число нулей, P-число полюсов f в контуре. **Критерий Найквиста:** Для замкнутой системы с разомкнутой передаточной функцией L(s) = G(s)H(s): - Строим годограф Найквиста: L(jω), ω ∈ (−∞, +∞) - Считаем обороты вокруг точки −1 (ориентация CCW = +1) - Z = N + P_open → Z нулей 1+L(s) в правой полуплоскости **Для дискретных систем:** вместо правой полуплоскости-внешность единичного круга |z|>1

БПФ в конкурентном программировании

Умножение полиномов через БПФ-стандартная задача в конкурентном программировании. NTT (Number Theoretic Transform)-вариант БПФ над конечными полями, дающий точные целочисленные результаты.

**БПФ-умножение полиномов:** 1. A(x) * B(x) за O(N log N) вместо O(N²) 2. Вычислить FFT(A) и FFT(B)-получаем значения в N корнях из единицы 3. Поточечное умножение: C[k] = A[k] · B[k] 4. Обратное IFFT: получаем коэффициенты C(x) **NTT (Number Theoretic Transform):** - Работает в Z/pZ где p-простое число вида p = c·2^k + 1 - Примитивный корень g порядка 2^k играет роль e^{2πi/N} - Популярные p: 998244353 = 119·2²³ + 1 (примитивный корень g=3) - Преимущество: точные целые результаты, нет погрешностей float

Быстрые выводы для интервью

На интервью иногда просят "вывести на доске" формулу вычета простого полюса, или объяснить почему cos-интеграл = Re∮ e^{iz}/z dz. Набор быстрых выводов-необходимый инструмент.

**Вычет в простом полюсе z₀:** Res(f, z₀) = lim_{z→z₀} (z−z₀)·f(z) **Быстро:** если f = p(z)/q(z) и q(z₀)=0, q'(z₀)≠0: Res(f, z₀) = p(z₀)/q'(z₀) **Коэффициент Лорана aₙ:** aₙ = 1/(2πi) ∮ f(z)/zⁿ⁺¹ dz = Res(f(z)/zⁿ⁺¹, 0) **∫₀^∞ sin(x)/x dx = π/2:** Контур: полуокружность с маленькой выемкой у 0 Res(e^{iz}/z, 0) = 1 → ∮ = πi → Im(...) = π/2 **Типичная "заготовка" на интервью:** Полюс на вещественной оси: ∮ = πi·Res (полукруг, не круг)

Ключевые идеи

• **DSP-интервью:** полюсы H(z) внутри |z|<1 ↔ устойчивость; ROC = кольцо сходимости ряда Лорана
• **Найквист:** принцип аргумента N−P = обороты годографа вокруг −1
• **NTT:** БПФ в Z/pZ; примитивный корень g играет роль e^{2πi/N}; p=998244353
• **Быстрые выводы:** Res = p(z₀)/q'(z₀); ∫sinc = π/2 через полуокружность

Связанные темы

Интервью-паттерны собирают весь пройденный курс:

• Complex Analysis в CS — Z-преобразование, FFT, производящие функции-базис DSP-интервью
• Теория вычетов — Быстрые вычеты-ключевой навык на whiteboard-интервью
• Целые и мероморфные функции — Принцип аргумента и критерий Найквиста-теорема Руше в инженерии

Вопросы для размышления

• Почему NTT даёт точные целые результаты, тогда как FFT накапливает погрешности при умножении больших чисел?
• Как критерий Найквиста связан с теоремой Руше? Можно ли использовать Руше для анализа устойчивости?
• Если полюс H(z) точно на единичной окружности |z|=1-что происходит с откликом системы?

Связанные уроки

• nm-05