P=NP

Статус: Offline
Реєстрація: 09.09.2005
Повідом.: 20748
Адреса: м. Харків
  • 🟢 06:46 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #1
Мне удалось найти алгоритм точного решения NP-полных задач за полиномиальное время. Результаты описаны
⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.
 
  • 🟢 06:46 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #2

Заинтересовала фраза в абзаце про возможное применение:
Как именно Вы видите применение такого решения в проектировании электронных устройств? Ну и в качестве продукции - тоже интересно как.
Я, как раз, электроник и это вопросы для меня профессиональные.
С уважением.
 
  • 🟢 06:46 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #3

Например имея решатель задачи точного покрытия множествами можно отключать минимальное количество строк и столбцов сбойных ячеек памяти обнаруженных в результате диагностики при производстве.

Что касается проектирования, то решая различные задачи на графах можно сделать схемы (имею ввиду прежде всего внутри микросхем) более эффективными.
 
  • 🟢 06:46 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #4

Ну так вот не сказал бы сразу.

Зачем отключать сбойные ячейки памяти? У цифровых устройств есть всего один критерий качества - работает/не работает. Если в странице (а организация памяти чаще всего страничная) есть хотя бы одна сбойная ячейка - страницу можно и нужно смело браковать. Это при наличии некоего аналога SMART, как у винтов. Зачастую в ИМС такого нет и лучшее, что можно сделать - из Пенька - Целерон - это, как раз и есть продукт выбраковки и отключения модулей со сбоями

Эффективность схемы - интересное словосочетание, но слишком общее. Как именно?
 
  • 🟢 06:46 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #5
# В задаче трассировки межсоединений печатных плат или микросхем необходимо разбиение исходной схемы на слои (каждый из которых представляет собой планарный граф). Критерии оптимальности — минимальное число слоев и межсоединений (фактически, себестоимость производства), ограничения — габаритные размеры и требования термической и электромагнитной совместимости электронных компонентов.

# В задаче разбиения граф-схемы алгоритма на блоки с целью реализации на многопроцессорной системе или логическом мультиконтроллере. Критерии оптимальности — минимальное число блоков, минимальные степени дублирования сигналов микроопераций и логических условий, минимальное число межмодульных передач управления, минимальный трафик межмодульных передач управления и данных; ограничения диктуются используемой элементной базой.
 
  • 🟢 06:46 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #6
Ага, понял о чем речь.
Ну на счет трасс печатной платы - сейчас автотрассировщики уже достаточно быстрые, не знаю даст ли эффект оптимизация именно этим методом - возможно и незначительный получится, но там проблемы, как раз, не в оптимизации, а в большом количестве условий, которые прид1тся ввести, чтобы трассировщик ещё и электромагнитную совместимость учитывал. посему большинство склоняется к ручной трассировке, используя автотрассировщики в качестве не автоматизации, а в качестве механизации процесса - когда, к примеру, шину в несколько проводников надо тянуть от одного корпуса к другому - трассировщик быстрее, чем руками.

На счет оптимизации внутренней архитектуры алгоритма - с картами карно как-то можно сравнить?
 
  • 🟢 06:46 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #7
Самое близкое, что приходит в голову это задача выполнимости булевых формул (ВЫП). Только в отличии карт карно задача более универсальная и NP-полная. т.е. решение получится известными но не мне способами не возможно в актуальное время.
 
  • 🟢 06:46 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #8

Карно допустим для решения до 6ти операндов. Тем не менее - именно карно используется в проектировании логики на ПЛМ и ПЛИС. Собствено там я вижу основное применение.
 
  • 🟢 06:46 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #9
Интересно, но без рассмотрения самого алгоритма не ясно.