Задача: Проанализировать задачи о рюкзаке и 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.
Оно показывает динамику системы — как она работает, а не из чего состоит. Это особенно важно для сложных процессов, где важна последовательность действий и принятие решений.
Блок-схемы — для алгоритмов, последовательностей действий. DFD (Data Flow Diagram) — для систем, где важно движение данных между процессами. Для нашего поиска информации больше подходит блок-схема.
Полностью автоматически — сложно. Но можно проверить базовые ошибки: все ли блоки соединены, есть ли начало и конец, нет ли "тупиков". Лучшая проверка — мысленно пройти по схеме как по инструкции.