{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Моделирование без циклов\n", "\n", "Сто тысяч экспериментов одной таблицей — сумма двух кубиков, число π методом Монте-Карло, парадокс дней рождения. Вероятность — доля удачных строк.\n", "\n", "Курс NumPy · урок `np-simulation` · [урок на сайте](https://ds-edu-trainer.vercel.app/courses/numpy/simulation).\n", "\n", "Выполняйте ячейки по порядку (Shift+Enter), начиная с первой — она готовит урок. После каждого упражнения идёт\n", "ячейка проверки: она печатает ✓ / ✗ и итог." ], "id": "intro" }, { "cell_type": "code", "metadata": { "cellView": "form", "jupyter": { "source_hidden": true } }, "source": [ "# @title Подготовка урока — выполните эту ячейку первой\n", "# Проверяет версии пакетов, записывает файлы данных в папку data/ и определяет _check — проверку упражнений.\n", "import base64, os, zlib\n", "\n", "for _name, _min in {\"numpy\":\"2.0\"}.items():\n", " try:\n", " _have = __import__(_name).__version__\n", " except ImportError:\n", " print(f\"Нет пакета {_name}: выполните %pip install {_name} и перезапустите ядро\")\n", " continue\n", " if tuple(int(x) for x in _have.split(\".\")[:2]) < tuple(int(x) for x in _min.split(\".\")):\n", " print(f\"Урок написан для {_name} {_min} и новее, у вас {_have}: выполните %pip install -U {_name} и перезапустите ядро\")\n", "\n", "# ─── Проверка упражнений: тот же раннер, что у задач на сайте ───\n", "# ─── Запуск тестов ───────────────────────────────────────────────────────────\n", "\n", "_TIMEOUT = 2.0 # секунд на тест; отдельный тест может задать свой: test_x.timeout = 10\n", "\n", "\n", "def _call_with_timeout(target, seconds: float) -> bool:\n", " \"\"\"Запускает target() в отдельном потоке. Возвращает False, если за seconds он не завершился.\"\"\"\n", " import sys\n", " import threading\n", "\n", " if sys.platform == \"emscripten\": # Python в браузере: потоков нет, таймаут обеспечивает страница\n", " target()\n", " return True\n", " # Большой стек нужен, чтобы глубокая рекурсия давала RecursionError, а не аварийное завершение Python.\n", " for megabytes in (256, 64, 0):\n", " try:\n", " threading.stack_size(megabytes * 1024 * 1024)\n", " worker = threading.Thread(target=target, daemon=True)\n", " worker.start()\n", " except (ValueError, RuntimeError, MemoryError):\n", " continue\n", " worker.join(seconds)\n", " return not worker.is_alive()\n", " target() # потоки недоступны — запускаем без таймаута\n", " return True\n", "\n", "\n", "def _test_info(fn) -> dict:\n", " \"\"\"Описание теста, его лимит времени и сообщение на случай зависания.\"\"\"\n", " limit = getattr(fn, \"timeout\", _TIMEOUT)\n", " hint = getattr(fn, \"timeout_hint\", \"\")\n", " message = (\n", " f\"тест не завершился за {limit:g} с — возможно, бесконечный цикл или рекурсия: \"\n", " \"проверьте, что границы/аргументы изменяются на каждом шаге\" + (f\". {hint}\" if hint else \"\")\n", " )\n", " return {\"title\": (fn.__doc__ or fn.__name__).strip(), \"timeout\": limit, \"timeout_message\": message}\n", "\n", "\n", "def _error_result(title: str, error: BaseException, user_file: str | None) -> dict:\n", " \"\"\"Результат упавшего теста: статус, сообщение, тип исключения и строка в коде решения.\"\"\"\n", " line = None\n", " if user_file: # самый глубокий кадр в коде решения; ошибка внутри самих тестов — без номера строки\n", " tb = error.__traceback__\n", " while tb is not None:\n", " if tb.tb_frame.f_code.co_filename == user_file:\n", " line = tb.tb_lineno\n", " tb = tb.tb_next\n", " status, message = \"error\", f\"{type(error).__name__}: {error}\"\n", " if isinstance(error, NotImplementedError):\n", " status, message, line = \"not_written\", \"функция ещё не написана\", None\n", " elif isinstance(error, AssertionError):\n", " status, message = \"failed\", str(error) or \"проверка не прошла\"\n", " elif isinstance(error, RecursionError):\n", " message = \"RecursionError: слишком глубокая рекурсия — проверьте базовый случай и то, что задача уменьшается\"\n", " elif isinstance(error, MemoryError) or (isinstance(error, OverflowError) and \"index-sized\" in str(error)):\n", " message = f\"{type(error).__name__}: не хватило памяти — возможно, создаётся слишком большая структура данных\"\n", " return {\"title\": title, \"status\": status, \"message\": message, \"error_type\": type(error).__name__, \"line\": line}\n", "\n", "\n", "def _run_tests(verbose: bool = True, on_start=None, on_result=None, user_file: str | None = None) -> list[dict]:\n", " \"\"\"Запускает тесты задачи (_TESTS — функции из tests.py) по порядку, каждый — с таймаутом.\n", "\n", " Возвращает список результатов: {\"title\", \"status\", \"message\", \"error_type\", \"line\"}, где status —\n", " passed · failed · error · not_written · timeout · not_run. Если тест завис, при verbose=True печатает\n", " итог и завершает процесс: зависший поток остановить нельзя. on_start(i) и on_result(i, результат)\n", " вызываются по мере выполнения; user_file — имя файла с кодом решения для номеров строк в ошибках.\n", " \"\"\"\n", " import os\n", " import sys\n", "\n", " if verbose:\n", " try: # ✓ и кириллица в консоли Windows со старой кодировкой\n", " sys.stdout.reconfigure(encoding=\"utf-8\")\n", " except Exception: # noqa: BLE001 — reconfigure может не быть (перенаправленный вывод, браузер)\n", " pass\n", "\n", " tests = list(_TESTS)\n", " results: list[dict] = []\n", " not_written = hung = False\n", " for index, fn in enumerate(tests):\n", " info = _test_info(fn)\n", " outcome: dict = {}\n", "\n", " def target(fn=fn, outcome=outcome):\n", " try:\n", " fn()\n", " except BaseException as e:\n", " outcome[\"error\"] = e\n", "\n", " if on_start:\n", " on_start(index)\n", " if not _call_with_timeout(target, info[\"timeout\"]):\n", " results.append({\"title\": info[\"title\"], \"status\": \"timeout\", \"message\": info[\"timeout_message\"], \"error_type\": None, \"line\": None})\n", " for other in tests[index + 1:]:\n", " results.append({\"title\": _test_info(other)[\"title\"], \"status\": \"not_run\", \"message\": \"не запускался: предыдущий тест завис\", \"error_type\": None, \"line\": None})\n", " hung = True\n", " break\n", " error = outcome.get(\"error\")\n", " if error is None:\n", " result = {\"title\": info[\"title\"], \"status\": \"passed\", \"message\": \"\", \"error_type\": None, \"line\": None}\n", " else:\n", " result = _error_result(info[\"title\"], error, user_file)\n", " not_written = not_written or result[\"status\"] == \"not_written\"\n", " results.append(result)\n", " if on_result:\n", " on_result(index, result)\n", "\n", " if not_written: # пока функция не написана, «даром» пройденные тесты не засчитываются\n", " for r in results:\n", " if r[\"status\"] == \"passed\":\n", " r.update(status=\"not_written\", message=\"не засчитан, пока функция не написана\")\n", " for r in results:\n", " if len(r[\"message\"]) > 300:\n", " r[\"message\"] = r[\"message\"][:300] + \"…\"\n", "\n", " if verbose:\n", " if not_written:\n", " print(\"Функция ещё не написана — замените raise NotImplementedError своим кодом.\\n\")\n", " for r in results:\n", " mark = {\"passed\": \"✓\", \"not_run\": \"–\"}.get(r[\"status\"], \"✗\")\n", " print(f\"{mark} {r['title']}\")\n", " if r[\"message\"]:\n", " print(f\" {r['message']}\")\n", " passed = sum(r[\"status\"] == \"passed\" for r in results)\n", " print(\"─\" * 40)\n", " print(f\"Прошло {passed} из {len(results)}\" + (\" — всё верно!\" if passed == len(results) else \"\"))\n", " if hung:\n", " print(\"Выполнение остановлено: один из тестов завис.\")\n", " sys.stdout.flush()\n", " os._exit(1)\n", " return results\n", "\n", "\n", "def _check(*tests, names=()):\n", " \"\"\"Запускает проверки упражнения и печатает ✓ / ✗ и итог — как на сайте.\"\"\"\n", " for name in names:\n", " if \".\" in name: # «Класс.метод» из заготовки: класс должен быть объявлен\n", " if not isinstance(globals().get(name.split(\".\")[0]), type):\n", " print(f\"✗ класс {name.split('.')[0]} не объявлен — выполните ячейку упражнения\")\n", " return\n", " continue\n", " if name not in globals():\n", " print(f\"✗ переменная {name} не создана — выполните ячейку упражнения\")\n", " return\n", " if globals()[name] is Ellipsis:\n", " print(f\"✗ {name} пока равна ... — замените многоточие своим кодом\")\n", " return\n", " globals()[\"_TESTS\"] = list(tests)\n", " _run_tests()" ], "execution_count": null, "outputs": [], "id": "setup" }, { "cell_type": "markdown", "metadata": {}, "source": [ "Какова вероятность выбросить 7 на двух кубиках? Можно посчитать на бумаге, а можно **смоделировать**: бросить\n", "кубики много раз и посмотреть на долю удачных бросков. Метод, который отвечает на вопросы о вероятностях\n", "повторением случайных экспериментов, называют **методом Монте-Карло** — в честь Монте-Карло, города казино.\n", "\n", "Приём, который делает моделирование на NumPy быстрым: один эксперимент — одна **строка** таблицы. Генератор\n", "сразу выдаёт таблицу `size=(экспериментов, бросков)`, итог каждого эксперимента — агрегат по `axis=1`, а\n", "вероятность — среднее маски по всем строкам. Ни одного цикла.\n", "\n", "## Два кубика" ], "id": "text-9" }, { "cell_type": "code", "metadata": {}, "source": [ "# Сто тысяч бросков двух кубиков\n", "import numpy as np\n", "\n", "rng = np.random.default_rng(1)\n", "throws = rng.integers(1, 7, size=(100000, 2)) # строка — один бросок двух кубиков\n", "print(throws[:3])\n", "sums = throws.sum(axis=1)\n", "print((sums == 7).mean())" ], "execution_count": null, "outputs": [], "id": "two-dice" }, { "cell_type": "markdown", "metadata": {}, "source": [ "Точный ответ — 6 из 36 = 0.1667: из 36 равновероятных пар ровно 6 дают семь. Моделирование попало почти в точку." ], "id": "text-21" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Упражнение 1. Дубль\n", "\n", "Создайте генератор с seed 12 и бросьте два кубика 100 000 раз (таблица 100 000 × 2). Сохраните в `doubles`\n", "долю бросков, где на кубиках выпало **одно и то же** число.\n", "\n", "
Подсказка 1\n", "\n", "Броски — `rng.integers(1, 7, size=(100000, 2))`.\n", "\n", "
\n", "
Подсказка 2\n", "\n", "Одинаковые — сравните столбцы: `pairs[:, 0] == pairs[:, 1]`; доля — среднее маски.\n", "\n", "
" ], "id": "doubles-task" }, { "cell_type": "code", "metadata": {}, "source": [ "rng = ...\n", "doubles = ..." ], "execution_count": null, "outputs": [], "id": "doubles" }, { "cell_type": "code", "metadata": {}, "source": [ "# Проверка упражнения 1 — выполните после своего решения\n", "def test_doubles():\n", " \"doubles — доля дублей\"\n", " assert not isinstance(doubles, np.ndarray), \"doubles — массив, а нужна одна доля: среднее маски\"\n", " assert 0 < doubles < 1, f\"doubles = {doubles}: доля должна быть между 0 и 1\"\n", " assert abs(doubles - 1 / 6) < 0.01, f\"doubles = {doubles:.4f}, а должно быть около 1/6 ≈ 0.167: дубль — когда числа в двух столбцах равны\"\n", " assert abs(doubles - 0.16459) < 1e-9, f\"doubles = {doubles}: создайте генератор с seed 12 и бросьте кубики 100000 × 2\"\n", "\n", "_check(test_doubles, names=[\"rng\",\"doubles\"])" ], "execution_count": null, "outputs": [], "id": "doubles-check" }, { "cell_type": "markdown", "metadata": {}, "source": [ "
Решение\n", "\n", "```python\n", "rng = np.random.default_rng(12)\n", "pairs = rng.integers(1, 7, size=(100000, 2))\n", "doubles = (pairs[:, 0] == pairs[:, 1]).mean()\n", "```\n", "\n", "
" ], "id": "doubles-solution" }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Вопрос.** Какова точная вероятность дубля на двух кубиках?\n", "\n", "- 1/36\n", "- 1/6\n", "- 1/12\n", "\n", "
Ответ\n", "\n", "1/6\n", "\n", "Дублей шесть (1–1, 2–2, …, 6–6) из 36 равновероятных пар: 6/36 = 1/6 ≈ 0.167. Первый кубик может быть любым, второй должен совпасть с ним — вероятность 1/6.\n", "\n", "
" ], "id": "quiz-32" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Сколько орлов" ], "id": "text-41" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Упражнение 2. Три орла из пяти\n", "\n", "Создайте генератор с seed 5 и смоделируйте 50 000 серий по 5 бросков монеты (таблица 50 000 × 5 из маски\n", "`< 0.5`). Сохраните в `at_least_3` долю серий, где орлов было **не меньше трёх**.\n", "\n", "
Подсказка 1\n", "\n", "Маска бросков — `rng.random((50000, 5)) < 0.5`; `True` — орёл.\n", "\n", "
\n", "
Подсказка 2\n", "\n", "Число орлов в серии — сумма строки, `axis=1`; дальше — доля серий, где она не меньше 3.\n", "\n", "
" ], "id": "heads-task" }, { "cell_type": "code", "metadata": {}, "source": [ "rng = ...\n", "at_least_3 = ..." ], "execution_count": null, "outputs": [], "id": "heads" }, { "cell_type": "code", "metadata": {}, "source": [ "# Проверка упражнения 2 — выполните после своего решения\n", "def test_share():\n", " \"at_least_3 — доля серий с тремя и больше орлами\"\n", " assert not isinstance(at_least_3, np.ndarray), \"at_least_3 — массив, а нужна одна доля\"\n", " assert abs(at_least_3 - 0.5) < 0.02, f\"at_least_3 = {at_least_3:.4f}, а должно быть около 0.5: орлов в серии — сумма по строке, условие — три и больше\"\n", " assert abs(at_least_3 - 0.50136) < 1e-9, f\"at_least_3 = {at_least_3}: seed 5, таблица 50000 × 5\"\n", "\n", "_check(test_share, names=[\"rng\",\"at_least_3\"])" ], "execution_count": null, "outputs": [], "id": "heads-check" }, { "cell_type": "markdown", "metadata": {}, "source": [ "
Решение\n", "\n", "```python\n", "rng = np.random.default_rng(5)\n", "flips = rng.random((50000, 5)) < 0.5\n", "at_least_3 = (flips.sum(axis=1) >= 3).mean()\n", "```\n", "\n", "
" ], "id": "heads-solution" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Число π\n", "\n", "Бросим точки в квадрат со стороной 1. Четверть круга радиусом 1 занимает π/4 площади квадрата — значит, доля\n", "точек, попавших в круг (x² + y² ≤ 1), примерно равна π/4:" ], "id": "text-51" }, { "cell_type": "code", "metadata": {}, "source": [ "# π методом Монте-Карло\n", "rng = np.random.default_rng(1)\n", "points = rng.random((100000, 2))\n", "inside = (points[:, 0] ** 2 + points[:, 1] ** 2) <= 1\n", "print(inside.mean() * 4)" ], "execution_count": null, "outputs": [], "id": "pi" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Упражнение 3. Оценить π\n", "\n", "Создайте генератор с seed 3, бросьте 100 000 точек (таблица 100 000 × 2 из `rng.random`) и сохраните в\n", "`pi_est` оценку числа π: доля точек внутри четверти круга, умноженная на 4.\n", "\n", "
Подсказка 1\n", "\n", "Точки — `rng.random((100000, 2))`, столбец 0 — x, столбец 1 — y.\n", "\n", "
\n", "
Подсказка 2\n", "\n", "Внутри круга — `x**2 + y**2 <= 1`; доля — среднее маски.\n", "\n", "
" ], "id": "pi-est-task" }, { "cell_type": "code", "metadata": {}, "source": [ "rng = ...\n", "pi_est = ..." ], "execution_count": null, "outputs": [], "id": "pi-est" }, { "cell_type": "code", "metadata": {}, "source": [ "# Проверка упражнения 3 — выполните после своего решения\n", "def test_pi():\n", " \"pi_est — оценка числа π\"\n", " assert not isinstance(pi_est, np.ndarray), \"pi_est — массив, а нужно одно число\"\n", " assert abs(pi_est - 0.78378) > 0.1, \"это доля точек внутри круга, а она равна π/4\"\n", " assert abs(pi_est - 3.14159) < 0.05, f\"pi_est = {pi_est:.4f}, а должно быть близко к 3.14\"\n", " assert abs(pi_est - 3.13512) < 1e-9, f\"pi_est = {pi_est}: seed 3, 100000 точек, таблица 100000 × 2\"\n", "\n", "_check(test_pi, names=[\"rng\",\"pi_est\"])" ], "execution_count": null, "outputs": [], "id": "pi-est-check" }, { "cell_type": "markdown", "metadata": {}, "source": [ "
Решение\n", "\n", "```python\n", "rng = np.random.default_rng(3)\n", "pts = rng.random((100000, 2))\n", "pi_est = ((pts[:, 0] ** 2 + pts[:, 1] ** 2) <= 1).mean() * 4\n", "```\n", "\n", "
" ], "id": "pi-est-solution" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Парадокс дней рождения\n", "\n", "Сколько человек нужно собрать, чтобы у двоих совпал день рождения с вероятностью около 50 %? Интуиция говорит\n", "«человек 180», а ответ — 23. Проверим: строка — группа из 23 человек, дни — случайные числа от 1 до 365.\n", "Совпадение в группе легко найти, если отсортировать строку: тогда одинаковые дни окажутся **соседями**." ], "id": "text-66" }, { "cell_type": "code", "metadata": {}, "source": [ "# Сортировка ставит одинаковые дни рядом\n", "group = np.sort(np.random.default_rng(6).integers(1, 366, size=23))\n", "print(group)\n", "print(group[1:] == group[:-1])\n", "print((group[1:] == group[:-1]).any())" ], "execution_count": null, "outputs": [], "id": "birthday-idea" }, { "cell_type": "markdown", "metadata": {}, "source": [ "`group[1:] == group[:-1]` сравнивает каждый элемент с предыдущим — два среза одной строки, сдвинутые на один.\n", "В этой группе два человека родились в 165-й день года — рядом после сортировки, и в маске появился `True`." ], "id": "text-74" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Упражнение 4. 23 человека\n", "\n", "Создайте генератор с seed 23, смоделируйте 10 000 групп по 23 человека и сохраните в `same_bday` долю групп,\n", "где хотя бы у двоих совпал день рождения.\n", "\n", "
Подсказка 1\n", "\n", "Группы — `rng.integers(1, 366, size=(10000, 23))`, отсортированные по строкам: `np.sort(…, axis=1)` сортирует каждую строку отдельно.\n", "\n", "
\n", "
Подсказка 2\n", "\n", "Соседи в каждой строке: `days[:, 1:] == days[:, :-1]`; «есть совпадение» — `.any(axis=1)`.\n", "\n", "
" ], "id": "birthday-task" }, { "cell_type": "code", "metadata": {}, "source": [ "rng = ...\n", "same_bday = ..." ], "execution_count": null, "outputs": [], "id": "birthday" }, { "cell_type": "code", "metadata": {}, "source": [ "# Проверка упражнения 4 — выполните после своего решения\n", "def test_bday():\n", " \"same_bday — доля групп с совпавшим днём рождения\"\n", " assert not isinstance(same_bday, np.ndarray), \"same_bday — массив, а нужна одна доля\"\n", " assert abs(same_bday - 0.507) < 0.03, (\n", " f\"same_bday = {same_bday:.4f}, а должно быть около 0.5. Не забыли отсортировать каждую строку и искать совпадения соседей внутри строки?\"\n", " )\n", " assert abs(same_bday - 0.4995) < 1e-9, f\"same_bday = {same_bday}: seed 23, таблица 10000 × 23\"\n", "\n", "_check(test_bday, names=[\"rng\",\"same_bday\"])" ], "execution_count": null, "outputs": [], "id": "birthday-check" }, { "cell_type": "markdown", "metadata": {}, "source": [ "
Решение\n", "\n", "```python\n", "rng = np.random.default_rng(23)\n", "days = np.sort(rng.integers(1, 366, size=(10000, 23)), axis=1)\n", "same_bday = (days[:, 1:] == days[:, :-1]).any(axis=1).mean()\n", "```\n", "\n", "
" ], "id": "birthday-solution" }, { "cell_type": "code", "metadata": {}, "source": [ "# Миллион бросков — одной строкой\n", "rng = np.random.default_rng(0)\n", "big = rng.integers(1, 7, size=(1000000, 2)).sum(axis=1)\n", "print(len(big), (big == 7).mean())" ], "execution_count": null, "outputs": [], "id": "speed" }, { "cell_type": "markdown", "metadata": {}, "source": [ "> **Типичная ошибка: цикл по экспериментам.**\n", ">\n", "> Моделирование легко написать циклом: миллион раз бросить кубики и сравнить. Это работает, но в десятки раз\n", "> медленнее (для простой арифметики — и в сотни): каждый шаг цикла — это медленный Python, а операция над таблицей — один быстрый проход внутри NumPy.\n", "> Думайте таблицей: эксперимент — строка." ], "id": "component-88" }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Итоги\n", "\n", "- Метод Монте-Карло: вероятность ≈ доля удачных исходов в большом числе случайных экспериментов.\n", "- Эксперимент — строка таблицы `size=(n, k)`; итог эксперимента — агрегат по `axis=1`.\n", "- `.any(axis=1)`, `.sum(axis=1)` и сравнения столбцов отвечают на «было ли» и «сколько» в каждой строке.\n", "- Чем больше экспериментов, тем точнее оценка." ], "id": "text-93" }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Подробнее в справочнике:** [numpy/random](https://ds-edu-trainer.vercel.app/reference/numpy/random) · [numpy/vectorization](https://ds-edu-trainer.vercel.app/reference/numpy/vectorization)" ], "id": "more" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "name": "python" }, "colab": { "provenance": [] } }, "nbformat": 4, "nbformat_minor": 5 }