Made on
Tilda
Задача: Проанализировать задачи о рюкзаке и TSP как модели
Цель: Понять, как абстрактные задачи становятся математическими моделями реальных ситуаций
Инструкция: 1) Вспомните условия задач. 2) Определите элементы, связи и параметры. 3) Обсудите, какие реальные ситуации они описывают
Элементы: рюкзак (контейнер), предметы для упаковки
Связи: предметы конкурируют за место в рюкзаке; выбор одного предмета влияет на доступную ёмкость для других
Параметры: вместимость рюкзака, вес/объём каждого предмета, ценность каждого предмета
Ограничения: суммарный вес выбранных предметов не должен превышать вместимость рюкзака; максимизировать суммарную ценность
Реальные ситуации: загрузка контейнера, формирование инвестиционного портфеля, планирование раскроя материалов
Пример разбора "Задачи коммивояжера (TSP)":Элементы: города (точки), которые нужно посетить
Связи: дороги между городами, образующие полный граф; последовательность посещения
Параметры: расстояния/стоимости между городами, количество городов
Ограничения: посетить каждый город ровно один раз; вернуться в исходный город; минимизировать общую длину маршрута
Реальные ситуации: планирование маршрутов доставки, сверление отверстий в платах, составление расписаний
Цель задания: Научиться находить и анализировать модели в повседневной жизни, понимать их структуру и классификацию
Модель всегда проще оригинала, она содержит только те свойства, которые важны для решения конкретной задачи. Например, глобус — модель Земли, но на нём нет всех городов, дорог, людей.
Нет, более того — она не может быть точной копией. Суть моделирования как раз в упрощении. Иногда намеренное искажение (идеализация) помогает лучше понять суть явления.
Выбор зависит от цели: если нужно испытать прочность — материальная модель; если рассчитать траекторию — математическая; если объяснить принцип работы — графическая.
Процесс моделирования представляет собой структурированную последовательность этапов, направленную на преобразование неформализованной проблемы в рабочую модель, пригодную для анализа и получения обоснованных выводов.
Содержательная постановка: Купить все необходимые продукты, потратив как можно меньше времени.
Итог: Задача сведена к классической задаче коммивояжера (TSP) на множестве отделов S с добавленной точкой E. Мы ищем самый короткий замкнутый маршрут, проходящий через все нужные отделы и возвращающийся к выходу.
Исследование точных решений демонстрирует фундаментальную проблему вычислительной сложности. Количество возможных гамильтоновых циклов растет факториально (n-1)!/2, что делает полный перебор неосуществимым для практически значимого числа вершин n.
Вопрос для анализа: Рассмотрим формализацию задачи «Оптимизировать поход в магазин». Какие типовые проблемы моделирования могут быть выявлены при критическом рассмотрении предложенной формализации?
1. Проблема исходных данных
Каков источник и точность данных для параметров модели, в частности, расстояний d(Mₐ, M₆)? Какие факторы (разная проходимость проходов, этажность) могут сделать понятие «расстояние» недостаточным для оценки временных затрат?
Модель оперирует идеализированными данными. На практике расстояния носят оценочный характер, а ключевым параметром является время перемещения, которое зависит от непредсказуемых факторов (очереди, пробки в проходах). Это приводит к погрешности в работе модели.
2. Проблема адекватности критерия
Является ли минимизация геометрического пути эквивалентной минимизации времени, затрачиваемого на поход? Какие дополнительные факторы (плотность потока покупателей, время ожидания в очереди) не отражены в текущей целевой функции?
Исходная цель «потратить меньше времени» была неполно формализована через минимизацию пути. Для повышения адекватности требуется либо усложнение модели (введение весовых коэффициентов, отражающих пропускную способность отделов), либо замена критерия (прямая минимизация расчетного времени с учетом дополнительных факторов).
3. Проблема полноты модели
Какие содержательные ограничения реальной задачи были опущены в предложенной формализации? Например, необходимость сохранять температурный режим для отдельных товаров или логистику распределения веса покупок.
Модель игнорирует семантику товаров (скоропортящиеся, хрупкие, тяжелые) и связанные с этим практические ограничения на порядок их приобретения. Это классическая ошибка, когда формальная строгость достигается за счет потери существенных содержательных деталей.
4. Проблема применимости точных методов
Для магазина среднего размера (|S| ≈ 20-30) точное решение TSP может оставаться вычислительно затратным. Какой компромисс между оптимальностью маршрута и скоростью его расчета является приемлемым в данном контексте?
Для решения бытовой задачи нет необходимости в абсолютно оптимальном маршруте. Достаточным является нахождение субоптимального, но логичного решения. Следовательно, применение точных алгоритмов для TSP избыточно; эффективнее использовать эвристические методы (правило ближайшего соседа) или аппроксимационные алгоритмы, дающие приемлемое решение за полиномиальное время.
Разбор примера показывает, что даже простая на первый взгляд задача при формализации затрагивает ключевые проблемы моделирования: корректность исходных данных, адекватность выбора и формулировки критерия, баланс между простотой и полнотой модели, учет вычислительной осуществимости методов исследования.
Цель задания: Научиться применять этапы моделирования к реальным процессам, выявлять проблемы формализации.
Текст в формате PDF или DOCX".
Постановка задачи — это содержательное описание "что нужно сделать", а формализация — перевод этого описания на строгий математический или логический язык с определением объектов, параметров и критериев.
Потому что она определяет возможность практического решения задачи. Экспоненциальный рост сложности (как в TSP) делает невозможным точное решение для больших размеров задачи, требуя применения приближённых методов.
Это формальное выражение (функция), которую нужно максимизировать или минимизировать. Критерий количественно определяет, что считать "хорошим" решением (например, минимальное время, максимальная прибыль).
Дата проведения: Следующее занятие (03.02)
Темы: 2.1-2.6 (Этапы моделирования, Формализация, Типы моделей и их свойства)
Формат: 10-15 минут, n вопросов разных типов
Что повторить:
Интерполяция — нахождение промежуточных значений внутри известного диапазона данных.
Пример: Стоимость доставки 10 кг — 500 руб., 20 кг — 900 руб. Найти стоимость 15 кг.
Экстраполяция — прогнозирование значений за пределами известного диапазона данных.
Пример: Средние продажи с января по ноябрь — 100 ед./мес. Спрогнозировать продажи в декабре.
Ключевое: Экстраполяция рискованна! За границами данных могут действовать новые факторы.
| Свойство | Линейная зависимость | Нелинейная зависимость |
|---|---|---|
| Суть | Изменение одной величины прямо пропорционально изменению другой | Изменения непропорциональны |
| График | Прямая линия | Кривая (парабола, экспонента и др.) |
| Формула | y = k × x + b(k и b — константы) | y = x², y = 2ˣ,y = √x, y = 1/x |
| Пример 1 | Стоимость связи: Тариф: 300 руб./мес + 5 руб./минута. Удвоение минут → удвоение доплаты | Тормозной путь: При удвоении скорости путь до остановки увеличивается примерно в 4 раза |
| Пример 2 (TSP) | Расстояние маршрута: Если ВСЕ расстояния на карте увеличить вдвое, то и любой маршрут станет вдвое длиннее | Время маршрута: Из-за пробок время растет быстрее расстояния: 10 км → 1 час, 20 км → не 2, а 5 часов |
Дискретная величина — принимает отдельные, «счетные» значения (часто целые числа).
Интуитивный пример: Лестница — вы на 1-м, 2-м, 3-м этаже, но не «на 2,75 этаже».
В моделях: Количество городов в TSP, количество предметов в рюкзаке.
Непрерывная величина — может принимать любое значение в интервале.
Интуитивный пример: Пандус — вы можете подняться на 1.5 м, 1.501 м, 1.5001 м.
В моделях: Расстояние между городами (15.73 км), вес предмета (2.457 кг).
Детерминированная модель — «Мир без сюрпризов». При одних входных данных результат всегда одинаков.
Пример: Рецепт торта — если четко следовать инструкции, результат предсказуем.
В моделях: Расчет длины маршрута по идеальной карте.
Стохастическая (вероятностная) модель — учитывает случайность, неопределенность.
Пример: Бросок игральных костей — знаем вероятности, но не конкретный результат.
В моделях: Прогноз времени доставки с учетом пробок, погоды, поломок.
Задача: "Прогноз времени доставки пиццы"
Дано:
Обсудите: Почему прогноз может оказаться неверным?
Скорость доставки меняется! Зависимость нелинейная — каждый следующий километр "дороже".
Дискретно:
Непрерывно:
"Время зарядки телефона имеет нелинейную зависимость от уровня заряда: первые 50% заряжаются быстрее, чем последние. Сам уровень заряда — непрерывная величина (может быть 47.3%). Количество полных циклов зарядки — дискретная величина (500 циклов). Время полной зарядки — детерминированная величина при одинаковых условиях."
Устная подготовка + краткие письменные заметки (для себя). Основная задача — быть готовым к тесту 03.02.
При экстраполяции мы выходим за границы известных данных. За этими границами могут начать действовать новые факторы, которые не учитывались в модели (например, сезонность, физические ограничения, изменение тренда).
Расстояния на карте складываются линейно: 10 км + 10 км = 20 км. Но время зависит от скорости, которая может меняться из-за пробок, рельефа, типа дороги. Поэтому время часто имеет нелинейную зависимость от расстояния.
Зависит от контекста! Например, "количество денег" — дискретно в копейках (нельзя заплатить 0.5 копейки), но непрерывно при безналичном расчете (можно списать 100.57 рубля). В модели важно определиться с нужной точностью.
Суть: Система обладает свойствами, которых нет у её отдельных элементов. Целое — больше, чем сумма частей.
Примеры из разных областей:
В задаче TSP: Отдельные города и дороги не "знают" об оптимальном маршруте. Это свойство возникает только при рассмотрении всей системы "маршрут".
Суть: Любая система является частью надсистемы и сама состоит из подсистем.
Матрёшечный принцип: Системы вкладываются друг в друга, образуя уровни.
Задание: Построить иерархическую схему системы «Транспортная сеть города»
Инструкция:
Вопрос для обсуждения: Почему знание иерархии помогает при решении городских проблем? (Например, при планировании ремонта дорог)
Уровень 1: Персональный компьютер (система)
Уровень 2: Аппаратная часть, Программное обеспечение (подсистемы)
Уровень 3: Процессор, Оперативная память, Жёсткий диск (элементы аппаратной части)
Уровень 4: Транзистор процессора, Ячейка памяти, Магнитная пластина (элементы элементов)
Потому что это эффект, который проявляется только на уровне целой системы и исчезает, если систему разобрать на части. Как мелодия исчезает, если играть ноты по отдельности.
Да, в сложных системах часто встречаются сетевые структуры, где элементы могут входить в несколько подсистем одновременно. Например, учитель может вести уроки в разных классах, а программа — работать на разных компьютерах.
Чтобы понимать контекст. Например, чтобы оптимизировать маршрут в городе (система), нужно учитывать пробки (надсистема — транспортная сеть города) и даже погоду (надсистема над надсистемой).
Система может существовать, только если выполняются определённые условия:
Условия выполнены:
Функции (ЧТО делает?):
Структура (ИЗ ЧЕГО состоит?):
Ресурсы (ЧЕМ обеспечивается?):
Условия нарушены:
Нарушены функции:
Нарушена структура:
Недостаточно ресурсов:
Проследим жизненный цикл конкретной системы — смартфона, который вы покупаете и используете.
Что происходит: Появление потребности в новом телефоне
Конкретный пример: Старый телефон тормозит, не хватает памяти, вышел из строя
Системные изменения: Формирование требований к новой системе (камера, память, процессор)
Что происходит: Выбор, покупка, настройка
Конкретный пример: Изучение характеристик, сравнение моделей, заказ в интернет-магазине
Системные изменения: Создание структуры системы (установка приложений, перенос данных)
Что происходит: Ежедневное использование
Конкретный пример: Звонки, сообщения, фото, приложения, интернет — 2-3 года
Системные изменения: Регулярные обновления, установка новых приложений, накопление данных
Что происходит: Износ, устаревание
Конкретный пример: Батарея быстро разряжается, приложения тормозят, не хватает памяти для новых ОС
Системные изменения: Снижение производительности, появление ограничений, уменьшение полезности
Что происходит: Замена, утилизация
Конкретный пример: Продажа на запчасти, сдача на утилизацию, передача младшему брату
Системные изменения: Прекращение выполнения основных функций, распад на элементы (запчасти)
Цель — системообразующий фактор: Именно цель определяет, какие элементы войдут в систему и как они будут связаны.
Задание: Построить дерево целей для одной из предложенных систем
Выпускной, Новый год, День знаний
Для учёбы, планирования, развлечений
Бег, плавание, футбол, шахматы
Повышение успеваемости, экономия времени
Сайт, группа ВК, YouTube-канал
Раздельный сбор мусора, озеленение
Поездка с друзьями или семьёй
Образовательная, стратегическая, весёлая
Инструкция для выбранного варианта:
Что нужно сделать СЕГОДНЯ:
Домашнее задание (до 17.02): Доделать дерево целей: добавить критерии, ограничения, оформить аккуратно.
Вопрос для обсуждения в группах: Как выбор цели влияет на структуру дерева целей? Может ли одна и та же система иметь разные деревья целей?
Вопрос для обсуждения: Что важнее в дереве целей — полнота или простота? Почему?
Главная цель: Подготовиться к ЕГЭ по математике и набрать ≥ 80 баллов
Подцели:
1. Повторить все темы школьной программы
2. Решить не менее 50 типовых задач
3. Пройти 3 пробных тестирования
4. Разобрать сложные задачи с репетитором
Ограничения:
• Время подготовки: 3 месяца
• Бюджет: только бесплатные материалы и школьные учебники
Цель определяет структуру. Сначала мы понимаем, ЧТО хотим получить (цель), а потом решаем, КАК это сделать (структура). Например, цель "быстро добраться до работы" определяет структуру системы: выбор транспорта, маршрута, времени выезда.
Да, и это нормально. Например, сначала цель проекта — создать простой сайт, но в процессе понимаем, что нужен сложный интернет-магазин. Важно вовремя корректировать дерево целей и ресурсы.
Реальное ограничение можно измерить и проверить (бюджет, время, законы физики). Надуманное основано на предположениях или страхах ("я не смогу", "это слишком сложно"). Проверка: "Что произойдёт, если мы проигнорируем это ограничение?"
| Аспект анализа | Структурное описание | Функциональное описание |
|---|---|---|
| Основной вопрос | "КАК устроено?" Из каких частей состоит? | "ЧТО делает?" Какую работу выполняет? |
| Пример: Система "Автомобиль" | Двигатель, колёса, руль, кузов, трансмиссия | Перевозит людей и грузы, двигается по дорогам, обеспечивает комфорт |
| Пример: Система "Оптимальный маршрут" (TSP) | Города (вершины), дороги (рёбра), расстояния, алгоритм поиска | Находит кратчайший путь, минимизирует время в пути, учитывает ограничения и приоритеты |
| Пример: Система "Робот LF" | Датчики, контроллер, моторы, корпус, батарея | Следует по линии, корректирует траекторию, останавливается у метки |
| Формы представления | Схемы, чертежи, списки компонентов, иерархические схемы | Блок-схемы, алгоритмы, сценарии, описания процессов |
| Когда используется | При проектировании, сборке, ремонте, изучении состава | При планировании работы, оптимизации процессов, анализе эффективности |
Задание: Построить функциональную блок-схему для процессов в соответсвии с дреревом целей из дз к этому занятию.
Требования к блок-схеме:
Обратите внимание:
Время выполнения: 15 минут. Работа выполняется индивидуально на листах бумаги.
Сдача: В конце урока сдать лист с блок-схемой. Работы будут проверены и оценены на следующем занятии.
Попробуйте построить функциональную блок-схему для одного из процессов:
Работы, выполненные на уроке, будут проверены 24.02. Оценка будет выставлена в электронный журнал с комментариями. Если вы отсутствовали на занятии, нужно будет выполнить работу самостоятельно и сдать 24.02.
Оно показывает динамику системы — как она работает, а не из чего состоит. Это особенно важно для сложных процессов, где важна последовательность действий и принятие решений.
Блок-схемы — для алгоритмов, последовательностей действий. DFD (Data Flow Diagram) — для систем, где важно движение данных между процессами. Для нашего поиска информации больше подходит блок-схема.
Полностью автоматически — сложно. Но можно проверить базовые ошибки: все ли блоки соединены, есть ли начало и конец, нет ли "тупиков". Лучшая проверка — мысленно пройти по схеме как по инструкции.
На прошлом занятии мы строили блок-схемы — описывали последовательность действий во времени. Но для сложных систем этого недостаточно. Нужно показать не только ЧТО делаем, но и:
IDEF0 (Integration DEFinition for Function Modeling) — методология функционального моделирования, разработанная для описания сложных систем. Стандарт, используемый в системном анализе, бизнес-процессах, проектировании.
То, что преобразуется в процессе. Материалы, данные, объекты, которые поступают на вход и изменяются.
Пример: продукты, исходные данные, заготовкиРезультат выполнения функции. То, что получается после преобразования.
Пример: готовое блюдо, отчет, решениеТо, что регулирует процесс. Правила, инструкции, стандарты, ограничения.
Пример: рецепт, ГОСТ, расписание, бюджетТо, с помощью чего выполняется функция. Исполнители, оборудование, инструменты.
Пример: повар, компьютер, станок, программаКонтекстная диаграмма — это самый верхний уровень описания системы. На ней изображается один функциональный блок, представляющий всю систему целиком, и стрелки, показывающие её взаимодействие с внешней средой.
Задание: Построить контекстную диаграмму A-0 для одного из процессов
Требования:
[УПРАВЛЕНИЕ: правила, инструкции]
↓
[ВХОД] → [НАЗВАНИЕ ПРОЦЕССА] → [ВЫХОД]
(материалы) (глагол) (результат)
↑
[МЕХАНИЗМ: исполнители, инструменты]
Время выполнения: 10 минут. Работа в парах, обсуждение результатов.
Блок-схема показывает последовательность действий во времени. IDEF0 показывает все аспекты процесса: входные данные, результаты, управляющие воздействия и используемые механизмы. Это позволяет увидеть процесс целиком, а не только его шаги.
Да, на диаграмме может быть несколько стрелок входа, выхода, управления и механизма. Их группируют или подписывают отдельно. Главное — чтобы все необходимые связи были отражены.
Контекстная диаграмма (A-0) — это первый шаг. Далее её можно детализировать: разбить главный блок на подпроцессы (диаграмма A0), а затем каждый подпроцесс — ещё детальнее (A1, A2, A3...). Так создаётся иерархия функциональных моделей.
За 20 занятий мы изучили множество понятий. Сегодня соберём их в единую картину и увидим, как они связаны между собой.
Какая модель нужна, чтобы понять, почему одни ученики усваивают материал лучше других?
| Тип модели | Что учитывает | Позволяет выявить |
|---|---|---|
| Статистическая | Оценки, посещаемость | Корреляцию с успеваемостью |
| Графовая | Связи между учениками | Кто влияет на обсуждения |
| Функциональная (IDEF0) | Процесс обучения: входы, выходы, управление, механизмы | Где возникают проблемы |
Задание: Провести полный системный анализ для системы «Групповой чат для подготовки к проекту»
Что нужно сделать:
| Компонент анализа | Что описать |
|---|---|
| 1. Элементы | Кто и что входит в систему? (участники, технические средства) |
| 2. Связи | Какие отношения между элементами? (кто с кем общается, как передаётся информация) |
| 3. Структура | Как организованы связи? (иерархия, сеть, звезда) |
| 4. Внешняя среда | Что влияет на чат, но не входит в него? (дедлайны, другие чаты, погода) |
| 5. Модель для анализа | Предложите модель, которая поможет проанализировать активность в чате (например, кто самый активный, когда пишут чаще) |
Формат сдачи: Заполнить таблицу в тетради или на листе. Можно сделать в виде схемы + описания.
Время выполнения: 15 минут. Работа индивидуальная.
На следующем занятии — итоговый тест по всему курсу. Повторите все ключевые понятия с наших уроков:
Попробуйте самостоятельно провести полный системный анализ для системы «Ваше утро перед школой»:
Модель — это упрощение реальности, которое сохраняет только те свойства, которые важны для конкретной цели анализа. Модель всегда проще, чем реальная система, но позволяет делать прогнозы и принимать решения.
Потому что для разных целей нужны разные аспекты системы. Для анализа успеваемости класса нужна одна модель (статистическая), для расписания — другая (временная), для взаимодействия — третья (сетевая).
Умение увидеть систему целиком: не только её элементы, но и связи между ними, структуру, взаимодействие с внешней средой. А главное — понять, что любая система обладает эмерджентными свойствами, которых нет у её частей по отдельности.
Полный список теоретических вопросов и примеры практических задач для подготовки к экзамену
???? ОТКРЫТЬ ВОПРОСЫ К ЭКЗАМЕНУ20 теоретических вопросов + примеры задач по всем темам курса
Результаты теста будут доступны после проверки. Оценка выставляется по шкале:
Множество — это совокупность объектов, объединённых по какому-либо признаку. Объекты, входящие в множество, называются элементами.
Отношение (R) — это связь между элементами множества. Например: «находится в», «принадлежит», «связан с», «больше чем».
Любую систему можно описать математически через два компонента:
Структура системы — это способ организации связей между элементами, определяемый множеством R.
Состояние системы — это конкретный набор элементов, которые присутствуют в системе в данный момент.
Полное множество состояний — это все возможные комбинации элементов (все подмножества множества A).
Для множества из n элементов полное число состояний равно 2ⁿ.
| № | Подмножество (состояние) | Элементы |
|---|---|---|
| 1 | ∅ | (пустой портфель) |
| 2 | {книга} | книга |
| 3 | {тетрадь} | тетрадь |
| 4 | {ручка} | ручка |
| 5 | {книга, тетрадь} | книга, тетрадь |
| 6 | {книга, ручка} | книга, ручка |
| 7 | {тетрадь, ручка} | тетрадь, ручка |
| 8 | {книга, тетрадь, ручка} | книга, тетрадь, ручка |
Для 3 элементов: 2³ = 8 состояний
Задание: Для системы «Набор напитков в автомате»
Множество элементов: A = {чай, кофе, какао, сок}
Время выполнения: 15 минут. Работа в парах.
Дано множество A = {книга, тетрадь, ручка, карандаш, линейка}
Для A = {a, b, c}:
2³ = 8 состояний: ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}
Подмножество с элементом a: {a}, {a,b}, {a,c}, {a,b,c}
Множество — просто набор элементов. Система — это множество + связи между элементами (S = <A, R>). Без связей это ещё не система.
Для каждого из n элементов есть два варианта: он либо входит в состояние, либо нет. Поэтому 2 × 2 × ... × 2 (n раз) = 2ⁿ.
В реальных системах не все состояния из полного множества достижимы. Система подчиняется ограничениям, которые «вырезают» допустимые состояния.
Ограничения бывают разных типов:
Рассмотрим пример с 3 предметами: A = {книга (к), тетрадь (т), ручка (р)}
Ограничение 1: «нельзя брать книгу и тетрадь одновременно»
| Полное множество (8) | Допустимые (6) |
|---|---|
| ∅, {к}, {т}, {р}, {к,т}, {к,р}, {т,р}, {к,т,р} | ∅, {к}, {т}, {р}, {к,р}, {т,р} |
Ограничение 2: «не более 2 предметов»
| Полное множество (8) | Допустимые (7) |
|---|---|
| ∅, {к}, {т}, {р}, {к,т}, {к,р}, {т,р}, {к,т,р} | ∅, {к}, {т}, {р}, {к,т}, {к,р}, {т,р} |
Ограничение по весу (задача о рюкзаке): предметы весят 3, 1, 0.5 кг, рюкзак ≤ 4 кг
| Состояние | Вес | Допустимо? |
|---|---|---|
| {к} | 3 | ✅ |
| {к, т} | 4 | ✅ |
| {к, р} | 3.5 | ✅ |
| {к, т, р} | 4.5 | ❌ |
Рост числа состояний при увеличении элементов происходит катастрофически быстро.
| n (элементов) | Число состояний (2ⁿ) |
|---|---|
| 3 | 8 |
| 5 | 32 |
| 10 | 1 024 |
| 15 | 32 768 |
| 20 | 1 048 576 |
| 30 | ~1 млрд |
| 50 | ~1 квадриллион |
В задаче TSP: число маршрутов = (n-1)!/2
| n (городов) | Число маршрутов |
|---|---|
| 5 | 12 |
| 10 | 181 440 |
| 12 | 19 958 400 |
| 15 | 43 589 145 600 |
| 20 | ~6.08×10¹⁶ |
Вывод: Полный перебор всех состояний возможен только для очень маленьких систем. Для реальных задач нужны приближённые методы.
Задание: Для множества A = {учебник математики (М), учебник физики (Ф), учебник информатики (И), учебник истории (Ист)}
Время выполнения: 15 минут. Работа в парах.
Для множества из 6 элементов (например, 6 разных книг: A, B, C, D, E, F)
C(6,0) = 1, C(6,1) = 6, C(6,2) = 15, C(6,3) = 20, C(6,4) = 15, C(6,5) = 6, C(6,6) = 1
Число маршрутов ~ (99)!/2 ≈ 10¹⁵⁶, что многократно превышает число атомов во Вселенной (~10⁸⁰) и предел Бремермана (10⁹³ операций). Такой перебор занял бы миллиарды лет.
Ограничения "отсекают" большую часть пространства состояний, оставляя только допустимые варианты. Это может во много раз сократить перебор, но не всегда спасает от комбинаторного взрыва.
Даже самые мощные компьютеры не могут решать задачи любой сложности. Существуют фундаментальные физические ограничения.
Это число огромно, но не бесконечно!
| n (городов) | Число маршрутов | Сравнение с пределом 10⁹³ |
|---|---|---|
| 10 | 181 440 | ≪ 10⁹³ (возможно) |
| 20 | ~6×10¹⁶ | ≪ 10⁹³ (возможно) |
| 30 | ~4×10³⁰ | ≪ 10⁹³ (возможно) |
| 50 | ~6×10⁶² | ≪ 10⁹³ (возможно) |
| 70 | ~10⁹⁹ | > 10⁹³ (невозможно!) |
| 100 | ~10¹⁵⁶ | ≫ 10⁹³ (невозможно!) |
Вывод: Для n ≥ 70 полный перебор всех маршрутов физически невозможен даже для компьютера размером со Вселенную, работающего с начала времён!
Сложность системы можно оценивать разными способами:
| Тип меры | Что оценивает | Пример |
|---|---|---|
| Количество элементов | Просто число компонентов | n = 50 городов |
| Количество связей | Число отношений между элементами | В TSP: n(n-1)/2 дорог |
| Связность | Плотность связей | Полный граф vs разреженный |
| Размер пространства состояний | Число возможных состояний | 2ⁿ для рюкзака, (n-1)!/2 для TSP |
| Алгоритмическая сложность | Число шагов для решения | O(2ⁿ) — экспоненциальная |
Задание: Оценить сложность системы «Расписание одного учебного дня»
Время выполнения: 15 минут. Работа в парах.
Оценить сложность системы «Расписание одного школьного дня в вашей школе»
"В моей школе 30 классов, 50 учителей, 40 кабинетов и 7 уроков в день. Число возможных расписаний огромно (намного больше 10⁹³), поэтому полный перебор невозможен. Составление расписания вручную требует огромного опыта и упрощений, а компьютеры используют эвристики и ограничения, чтобы найти приемлемый вариант."
Это максимальное количество вычислительных операций, которое могла бы выполнить гипотетическая вычислительная машина размером со всю Вселенную, работающая с момента Большого взрыва. Число равно примерно 10⁹³.
Число маршрутов для 70 городов превышает 10⁹⁹, что больше предела Бремермана. Даже теоретически, используя всю энергию и материю Вселенной, невозможно перебрать все варианты.
Мы выяснили, что сложность реальных систем часто превышает возможности полного перебора. Что делать?
Сегодня изучаем декомпозицию.
Декомпозиция — это разделение сложной системы на относительно независимые подсистемы, которые можно анализировать по отдельности.
| Система | Варианты декомпозиции |
|---|---|
| Компьютер | Процессор, память, видеокарта, жёсткий диск, материнская плата, периферия |
| Школа | Администрация, учителя, классы, учебная программа, материально-техническая база |
| Задача TSP | Разбить карту на районы → решать для каждого района отдельно |
| Интернет-магазин | Каталог, корзина, оплата, доставка, отзывы, поддержка |
| Человеческий организм | Нервная система, кровеносная система, пищеварительная система, опорно-двигательный аппарат |
Задание: Выполнить декомпозицию системы «Школьная столовая»
Время выполнения: 15 минут. Работа в парах.
Способ 1 (по отделам): Абонемент, Читальный зал, Книгохранилище, Отдел каталогизации.
Цель: Оптимизация распределения сотрудников по отделам.
Связи: Книги перемещаются между отделами, читатели взаимодействуют с разными отделами.
Нет, иногда чрезмерное разделение разрушает понимание системы как целого. Важно найти баланс и помнить, что подсистемы всё равно связаны, и эти связи нельзя полностью игнорировать.
Способ декомпозиции определяется целью анализа. Если мы хотим улучшить обслуживание читателей — делим по функциям. Если хотим оптимизировать закупки книг — делим по тематикам.
Агрегирование — это объединение группы элементов в один условный элемент для упрощения анализа.
Примеры агрегирования:
| ПЛЮСЫ агрегирования | МИНУСЫ агрегирования |
| ✅ Система становится проще для анализа | ❌ Теряется информация о каждом элементе |
| ✅ Меньше данных для обработки | ❌ Можно пропустить важные детали |
| ✅ Видна общая картина (не видны деревья за лесом) | ❌ Нельзя увидеть отдельные деревья |
| ✅ Можно сравнивать крупные блоки | ❌ Различия внутри группы становятся невидны |
| Исходные элементы | Агрегированная группа | Для чего нужно |
|---|---|---|
| Все ученики 5-х классов | «5-я параллель» | Планирование расписания, закупка учебников |
| Все товары в магазине | «Молочные продукты», «Хлебобулочные» | Анализ продаж по категориям |
| Все остановки в городе | «Транспортные узлы» | Планирование маршрутов |
| Все ошибки в программе | «Критические», «Второстепенные» | Приоритизация исправлений |
| Все покупки пользователя | «Средний чек», «Частота покупок» | Анализ поведения клиентов |
При агрегировании всегда нужно осознавать, что мы теряем, и достаточно ли для наших целей той точности, которая остаётся.
Задание: Агрегирование для системы «Школьная столовая»
Время выполнения: 15 минут. Работа в парах.
Продолжить работу, начатую на уроке, но уже для системы «Библиотека»
Способ 1 (по жанрам): Объединить книги в категории «Художественная литература», «Научная литература», «Учебная литература».
Цель: Анализ, какие жанры наиболее востребованы для закупки.
Потеря: Не видно конкретных авторов, названий книг внутри жанров.
Декомпозиция — разделяем целое на части (идём сверху вниз). Агрегирование — объединяем части в группы (идём снизу вверх). Это противоположные, но взаимодополняющие процессы.
Если мы потеряли слишком много важной информации и наши выводы стали неточными или ошибочными. Например, средняя температура по больнице не помогает лечить конкретного пациента.