10 питань — комбінаторика, теорія графів, RSA, ланцюги Маркова
Питання 1 / 10Комбінаторика
Скільки способів вибрати 2 предмeti з 6 (без повторень, без урахування порядку)?
C(n, k) = n! / (k!(n−k)!)
C(6, 2) = ?
C(6,2) = 6!/(2!·4!) = (6·5)/(2·1) = 15. Комбінація — вибір без урахування порядку. Якщо б порядок мав значення: P(6,2) = 30.
Питання 2 / 10Функція Ейлера
Функція Ейлера φ(12) = ? (кількість натуральних чисел ≤ 12, взаємно простих з 12)
12 = 2² · 3
φ(n) = n · ∏(1 − 1/p) для простих p | n
φ(12) = 12·(1−1/2)·(1−1/3) = 12·½·⅔ = 4. Числа {1, 5, 7, 11} — взаємно прості з 12. Це 4 числа ✓.
Питання 3 / 10Безлади (деранжементи)
Яка частка перестановок є деранжементами (безладами) при великих n?
D(n) = n! · Σₖ₌₀ⁿ (−1)ᵏ/k!
D(n)/n! → ? при n → ∞
D(n)/n! = Σₖ₌₀ⁿ (−1)ᵏ/k! → e⁻¹ ≈ 0.3679 при n→∞. Це розклад e⁻¹ у ряд Маклорена. Приклад: D(3) = 2; 2/6 = 1/3 ≈ e⁻¹ для n=3.
Питання 4 / 10Теорема Рамсея
Яке мінімальне N таке, що в будь-якому двохрозфарбуванні ребер K_N завжди є монохромний трикутник (K₃)?
R(s, t) — число Рамсея: мінімальне N,
де будь-який граф N вершин містить
або K_s, або незалежні t вершини.
R(3, 3) = ?
R(3,3) = 6. Доведення: для K₅ існує 2-розфарбування без монохромного K₃. Але для K₆ будь-яке 2-розфарбування (червоний/синій) містить монохромний K₃. Принцип: серед 5 ребер з однієї вершини — 3 одного кольору → трикутник.
Питання 5 / 10Теорія графів — Ейлерів цикл
За якої умови зв'язний граф має Ейлерів цикл (проходження ВСІХ ребер по одному разу і повернення на початок)?
Граф G = (V, E), зв'язний.
Ейлерів цикл існує тоді і тільки тоді, коли...
Теорема Ейлера (1736): ейлерів цикл ↔ всі вершини мають парний ступінь. Якщо рівно 2 вершини непарного ступеня — існує ейлерів шлях (не цикл). Задача Кенігсберзьких мостів: 4 вершини непарного ступеня → немає ейлерового шляху.
Питання 6 / 10Формула Ейлера
Для зв'язного планарного графа з V вершинами, E ребрами і F гранями (включно з зовнішньою): яка формула?
Теорема Ейлера (1758):
V − E + F = ?
V−E+F = 2 для зв'язних планарних графів (ейлерова характеристика = 2 для сфери). Приклад: куб: V=8, E=12, F=6; 8−12+6=2 ✓. Тераедр: 4−6+4=2 ✓. Для g-ручкового тора: V−E+F = 2−2g.
Питання 7 / 10Формула Кейлі
Скільки розмічених остовних дерев (spanning trees) має повний граф K_n?
Теорема Кейлі (1889):
τ(Kₙ) = ?
Формула Кейлі: τ(Kₙ) = nⁿ⁻². Для K₃: 3¹=3 дерева ✓ (три різних прямі). Для K₄: 4²=16 дерев. Доводиться через код Прюфера або матрицю Кірхгофа (теорема про матричне дерево).
Питання 8 / 10Алгоритми
Яка часова складність алгоритму Дейкстри (найкоротший шлях) при реалізації через бінарну купу на графі з V вершинами і E ребрами?
Граф G = (V, E), ваги невід'ємні.
Реалізація: бінарна купа (binary heap).
Дейкстра: T(V, E) = ?
O((V+E) log V) — стандартна відповідь з бінарною купою. Іноді спрощують до O(E log V) для зв'язних графів (E ≥ V−1). З купою Фібоначчі: O(E + V log V). Без купи (матриця): O(V²).
Питання 9 / 10Криптографія (RSA)
В RSA відкритий ключ (e, n), закритий ключ d. Шифрування повідомлення M і дешифрування C:
Mᵉ mod n = C ← шифрування
C^d mod n = ? ← дешифрування
де d·e ≡ 1 (mod φ(n))
C^d mod n = M — вихідне повідомлення. Чому: (Mᵉ)^d = M^(ed) ≡ M^(1+k·φ(n)) ≡ M·(Mᶠ⁽ⁿ⁾)^k ≡ M·1^k = M (mod n) за теоремою Ейлера. Безпека: важко факторизувати n = p·q.
Питання 10 / 10Ланцюги Маркова
Стаціонарний розподіл π ланцюга Маркова з матрицею переходу P визначається рівнянням:
πP = π (для рядкового вектора). Для стовпцевого: Pᵀπ = π, або P∙π = π якщо у проблемі транспонованa матриця. Це власний вектор матриці P' при власному значенні λ=1. При ергодичному ланцюгу: Pⁿ → {π,π,...,π} при n→∞.
0/10
Про цей тест
Цей тест перевіряє розуміння ключових концепцій теми. Питання складені так, щоб виявити прогалини у знаннях і спрямувати вас до матеріалів для повторення.
Алгоритми та структури даних — ядро комп'ютерних наук та практичного програмування.
Як підготуватися до тесту
Пройдіть тест до вивчення теми — щоб зрозуміти, що ви вже знаєте. Потім повторіть матеріал і пройдіть знову. Порівняйте результати — це покаже ефективність підготовки.
Часті запитання (FAQ)
Який матеріал перевіряє тест з тест?
Тест охоплює ключові концепції теми 'Тест': означення, теореми, методи обчислень та вміння застосовувати знання до конкретних задач. Питання вибрані так, щоб виявити як теоретичне розуміння, так і практичні навички.
Скільки питань у тесті з тест і яка структура?
Тест з 'Тест' включає питання різного типу: одиночний вибір, множинний вибір та числові відповіді. Структура відповідає стандартним університетським тестам, що робить підготовку максимально реалістичною.
Як підготуватися до тесту з тест?
Оптимальна підготовка до тесту з 'Тест': вивчіть теоретичний матеріал за шпаргалкою → пройдіть тренажер вправ → ознайомтеся з розв'язаними задачами → пройдіть пробний тест → проаналізуйте помилки → повторіть слабкі місця.
Чи можна пройти тест з тест кілька разів?
Так, тест з 'Тест' можна проходити необмежену кількість разів. Рекомендуємо: пройдіть до вивчення теми (базовий рівень), потім після — щоб виміряти прогрес. Порівняння результатів мотивує та показує ефективність навчання.
Де можна попрактикуватися перед тестом з тест?
Перед тестом з 'Тест' рекомендуємо: тренажер вправ (інтерактивні задачі з поясненнями), розв'язані задачі (показують метод вирішення) та шпаргалку (швидкий довідник формул) — все доступно безкоштовно на calculator.party.