Участник:StasFomin/AA — различия между версиями

Версия 22:01, 20 мая 2025 (просмотреть исходный код) StasFomin (обсуждение | вклад) ← Предыдущая правка		Версия 22:02, 20 мая 2025 (просмотреть исходный код) StasFomin (обсуждение | вклад) Следующая правка →
Строка 8:		Строка 8:
	----		----
		+
		+	----
		+
	<templatedpagelist>		<templatedpagelist>
	showtotal=yes		showtotal=yes
	namespace=Main		namespace=Main
−	limit=1	+	limit=4
	order=lastedit desc,pagename		order=lastedit desc,pagename
	output=template		output=template

---

Версия 22:02, 20 мая 2025

• Граф G=(V,E).
• Найти разбиение V на непересекающиеся множества V₁ и V₂.
• Максимизировать размер разреза, т.е. число ребер, в которых один конец в множестве V₁, а другой конец в V₂.

---

Код в «aa.ipynb» на гитлаб или живьем в лабе

• — есть тестовые данные и визуализация.
• — есть Pyomo-формулировка для ЦЛП. 📺видео📺

---

• Задача в базе NP-полных задач Вигго Кана
• Код задачи в книге «ГД» → «ND16»

---

Maximum D-Vector Covering

---

---

---

Всего страниц найдено: 4.

---

Задача «Minimum Test Collection»^©

---

• Коллекция C подмножеств конечного множества S.
• Найти подколлекцию C'⊆ C, такую, что для каждой пары различных элементов (и для каждого элемента этой пары) , есть некоторое подмножество , которое содержит точно один элемент из этой пары.
• Минимизировать мощность этой подколлекции |C'|.

Для понимания названия задачи, представим, что S — это множество возможных болезней, а подмножества — это симптомы (или «тесты»), которые могут быть характерны для нескольких болезней. И мы должны выбрать такой набор симптомов-тестов, чтобы имея результаты, мы могли отличить у пациента любые пары болезней.

---

Код в «minimum-test-collection.ipynb» на гитлаб или живьем в лабе

• — есть тестовые данные и визуализация.
• — есть Pyomo-формулировка для ЦЛП.
• — есть сведение на Python NP-полной задачи к данной.
  • Вроде как все есть, но надо бы прорефакторить решение студента

---

• Задача в базе NP-полных задач Вигго Кана
• Код задачи в книге «ГД» → «SP6»

---

---

---

Задача «Minimum Sum Of Squares»^©

---

• Конечное множество A, задан размер для каждого a ∈ A, и целое K ≥ 2 .
• Найти разбиение A на множество из K непересекающихся множеств A₁, A₂, …, A_K.
• Минимизировать сумму квадратов их размеров

---

Код в «minimum-sum-of-squares.ipynb» на гитлаб или живьем в лабе

• — есть тестовые данные и визуализация.
• — есть Pyomo-формулировка для ЦЛП.
  • Но надо проверять и рефакторить.

---

Задача зарезервирована: StasFomin 20:22, 21 мая 2025 (UTC)

• Задача в базе NP-полных задач Вигго Кана
• Код задачи в книге «ГД» → «SP19»

---

---

---

Задача «Minimum Metric Traveling Salesperson Problem»^©

---

• Набор C из m городов с заданными расстояниями между ними для каждой пары городов. Расстояния удовлетворяют неравенству треугольника!
• Найти тур C, т.е. перестановка .
• Минимизировать длину этого тура

---

Код в «minimum-metric-traveling-salesperson-problem.ipynb» на гитлаб или живьем в лабе

• — есть тестовые данные и визуализация.
• — есть Pyomo-формулировка для ЦЛП.
  • StasFomin 17:00, 21 мая 2025 (UTC): но надо бы прорефакторить все.

---

• Задача в базе NP-полных задач Вигго Кана

---

---

---

Задача «Minimum Local Register Allocation»^©

---

• Набор инструкций, формирующих некий блок без переходов,
  • N доступных регистров,
  • стоимость чтения и записи в регистр i.
• Порядок резервирования регистров для этой последовательности инструкций.
• Минимизировать полную стоимость чтения-записи в регистры.

---

Код в «minimum-local-register-allocation.ipynb» на гитлаб или живьем в лабе

• — есть тестовые данные и визуализация.
• — есть Pyomo-формулировка для ЦЛП.
  • Правда там две, студента и моя, надо прорефакторить и слить.

---

• Задача в базе NP-полных задач Вигго Кана

---

---