P=NP

novako · 21.03.2011

Мне удалось найти алгоритм точного решения NP-полных задач за полиномиальное время. Результаты описаны

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

Гість 3253 · 21.03.2011

novako сказав(ла):
Мне удалось найти алгоритм точного решения NP-полных задач за полиномиальное время. Результаты описаны

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

Заинтересовала фраза в абзаце про возможное применение:

Удешевить и повысить эффективность проектирования
электроники, как и улучить качество самой продукции.

Как именно Вы видите применение такого решения в проектировании электронных устройств? Ну и в качестве продукции - тоже интересно как.
Я, как раз, электроник и это вопросы для меня профессиональные.
С уважением.

novako · 21.03.2011

Как именно Вы видите применение такого решения в проектировании электронных устройств?

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

Что касается проектирования, то решая различные задачи на графах можно сделать схемы (имею ввиду прежде всего внутри микросхем) более эффективными.

Гість 3253 · 21.03.2011

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

Что касается проектирования, то решая различные задачи на графах можно сделать схемы (имею ввиду прежде всего внутри микросхем) более эффективными.

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

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

Эффективность схемы - интересное словосочетание, но слишком общее. Как именно?

novako · 21.03.2011

# В задаче трассировки межсоединений печатных плат или микросхем необходимо разбиение исходной схемы на слои (каждый из которых представляет собой планарный граф). Критерии оптимальности — минимальное число слоев и межсоединений (фактически, себестоимость производства), ограничения — габаритные размеры и требования термической и электромагнитной совместимости электронных компонентов.

# В задаче разбиения граф-схемы алгоритма на блоки с целью реализации на многопроцессорной системе или логическом мультиконтроллере. Критерии оптимальности — минимальное число блоков, минимальные степени дублирования сигналов микроопераций и логических условий, минимальное число межмодульных передач управления, минимальный трафик межмодульных передач управления и данных; ограничения диктуются используемой элементной базой.

Гість 3253 · 21.03.2011

novako сказав(ла):
# В задаче трассировки межсоединений печатных плат или микросхем необходимо разбиение исходной схемы на слои (каждый из которых представляет собой планарный граф). Критерии оптимальности — минимальное число слоев и межсоединений (фактически, себестоимость производства), ограничения — габаритные размеры и требования термической и электромагнитной совместимости электронных компонентов.

# В задаче разбиения граф-схемы алгоритма на блоки с целью реализации на многопроцессорной системе или логическом мультиконтроллере. Критерии оптимальности — минимальное число блоков, минимальные степени дублирования сигналов микроопераций и логических условий, минимальное число межмодульных передач управления, минимальный трафик межмодульных передач управления и данных; ограничения диктуются используемой элементной базой.

Ага, понял о чем речь.
Ну на счет трасс печатной платы - сейчас автотрассировщики уже достаточно быстрые, не знаю даст ли эффект оптимизация именно этим методом - возможно и незначительный получится, но там проблемы, как раз, не в оптимизации, а в большом количестве условий, которые прид1тся ввести, чтобы трассировщик ещё и электромагнитную совместимость учитывал. посему большинство склоняется к ручной трассировке, используя автотрассировщики в качестве не автоматизации, а в качестве механизации процесса - когда, к примеру, шину в несколько проводников надо тянуть от одного корпуса к другому - трассировщик быстрее, чем руками.

На счет оптимизации внутренней архитектуры алгоритма - с картами карно как-то можно сравнить?

novako · 21.03.2011

На счет оптимизации внутренней архитектуры алгоритма - с картами карно как-то можно сравнить?

Самое близкое, что приходит в голову это задача выполнимости булевых формул (ВЫП). Только в отличии карт карно задача более универсальная и NP-полная. т.е. решение получится известными но не мне способами не возможно в актуальное время.

Гість 3253 · 21.03.2011

novako сказав(ла):
Самое близкое, что приходит в голову это задача выполнимости булевых формул (ВЫП). Только в отличии карт карно задача более универсальная и NP-полная. т.е. решение получится известными но не мне способами не возможно в актуальное время.

Карно допустим для решения до 6ти операндов. Тем не менее - именно карно используется в проектировании логики на ПЛМ и ПЛИС. Собствено там я вижу основное применение.

Burnash · 28.03.2011

Интересно, но без рассмотрения самого алгоритма не ясно.