ReSQL.ru
     
powered by simpleCommunicator - 2.0.29     © 2024 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Map
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Найдите д.н.ф. и к.н.ф. для :
13 сообщений из 88, страница 4 из 4
  4  все
Найдите д.н.ф. и к.н.ф. для :
    #40118490
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Давайте в пятницу автоматизируем Квайна. Надо только удачную форму представления формул придумать.

Мне кажется что строки тут - не вариант. Нужны списки. Или еще какие-то структуры.
...
Рейтинг: 0 / 0
08.12.2021, 18:17
| Ответить | Цитировать | Написать  
Найдите д.н.ф. и к.н.ф. для :
    #40118500
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Квайн это кто или что? Топик целиком не читал.

И с картами Карно не все варианты охватываете, есть варианты с UB или пофиг что на выходе.
Например отображение десятичного знака на индикаторе: на входе 4 бита, а на выходе интересны только первые 10 состояний (0-9), что покажут значения 10-15 неинтересно, т.к. это за пределами предметной области. На этом предположении выводится наиболее простая ДНФ или КНФ, что упрощает разработку железного девайса решающего эту задачу.

ДНФ и КНФ это в первую очередь для проектирования цифровой электроники надо. После вывода оптимальных формул оно легко в железе реализуется с минимальным оверхэдом.
...
Рейтинг: 0 / 0
08.12.2021, 18:37
| Ответить | Цитировать | Написать  
Найдите д.н.ф. и к.н.ф. для :
    #40118518
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
У нас нет UB. Вся таблица заполнена. UB приколен тем что в значении карты ставим звездочку и далее
по ситуации можем брать либо 0 либо 1 что нам выгоднее. Обычно ставят 1 чтобы для СДНФ на Карно
можно было-бы обводить прямоугольником области единиц как можно более крупно.

Под Квайном я имел в виду https://ru.wikipedia.org/wiki/Метод_Куайна_—_Мак-Класки
...
Рейтинг: 0 / 0
08.12.2021, 19:48
| Ответить | Цитировать | Написать  
Найдите д.н.ф. и к.н.ф. для :
    #40118673
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Безотносительно к конкретному алгоритму.
О списках/не списках не рано ли с типа данных начинать?
Мой мнений в том, что работа с КНФ/ДНФ то же, что с деревьями. Это подбор комбинаций под заданную таблицу.
Сначала парсинг в дерево.
Преобразования состоят из перемещений, удалений, вставок шаблонных кусков.

Можно идти в одну сторону - в сторону упрощения.
Можно обратным выводом: от базовых формул логики и наращивать усложнения.
Случайный метод: от простого к сложному отжигом, роевым, генетическим ... пока таблица не станет хэммингово близкой к нужной. Затем доработать напильником, мож что и получится. Эффективность этого способа мне не известна.
...
Рейтинг: 0 / 0
09.12.2021, 17:03
| Ответить | Цитировать | Написать  
Найдите д.н.ф. и к.н.ф. для :
    #40118684
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
exp98
Безотносительно к конкретному алгоритму.
О списках/не списках не рано ли с типа данных начинать?
Мой мнений в том, что работа с КНФ/ДНФ то же, что с деревьями. Это подбор комбинаций под заданную таблицу.
Сначала парсинг в дерево.

Ну... если ты знаток компилляторов и AST или Lisp-а то тебе наверное будет интересно декомпозировать
любую задачу в деревья и бегать по ним.

Но в топике сидят обычные разрабы которые могут и в SQL что-то сделать или в JavaScript.

Если данная задача решается в строках (вспоминаем кстати нормальные алгоритмы Маркова..) - то
это просто прекрасно.

Если данная задача требует двух-уровнего массива или списка - тоже хорошо. С пивом пойдет.

Деревья - это too much дружище. Что нужно для Квайна-Мак-класски?

Нужно такую колбасу

Код: sql
1.
x1*x2*!x3*x4 | !x1*!x2*!x3*x4 | .....



привести к минимальной форме.
...
Рейтинг: 0 / 0
09.12.2021, 17:25
| Ответить | Цитировать | Написать  
Найдите д.н.ф. и к.н.ф. для :
    #40118701
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
mayton
Деревья - это too much дружище. Что нужно для Квайна-Мак-класски?
Нужно такую колбасу
Код: sql
1.
 x1*x2*!x3*x4 | !x1*!x2*!x3*x4 | .....

привести к минимальной форме.
Никак нет, дружище, M... Эту колбасу приводят любым методом, если он танцует от СДНФ.
Конечно можно запулить тупой подбор
x1*x1*!x1*x1
x1*x1*!x1*x2
x1*x1*!x1*x3 ..., но я писал не об таком. Написано же было "шаблоны" для краткости, подразумевались различныи знании априорных свойств предметки. В частности, ассоциативности/дистрибутивности, тождествы, всякии исключении переменных и т.п. Манипуляция шаблонами предметки эквивалентна (или почти) оной с отрезками деревьев (можно называть их "определяющими соотношениями" или правилами вывода). Она - аденоквантное воплощение хода мыслей. Я писал об этом. О быстродействии или памяти речи не было совсем. Ну и вообще, это всё было очень общими набросками вариантов.
Почему нужен именно "Квайн-Мак", мне неведомо.

Но деревья предметки обрабатывают и чрез SQL тоже - строки эквивалентны веткам, я не против, можно и транспонировать. Но вряд ли у редовых разрабов строки первичны в мышлении при обработке деревьев.
...
Рейтинг: 0 / 0
09.12.2021, 18:12
| Ответить | Цитировать | Написать  
Найдите д.н.ф. и к.н.ф. для :
    #40118708
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я просто предлагаю строку на попробовать. Не выйдет - можно углублять.

Но до того как ты кинешся создавать деревья - подумай что тебе всё равно нужен API
для поиска склеиваний-поглощений.
...
Рейтинг: 0 / 0
09.12.2021, 18:36
| Ответить | Цитировать | Написать  
Найдите д.н.ф. и к.н.ф. для :
    #40118709
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
exp98
SQL тоже - строки эквивалентны веткам,
Но вряд ли у редовых разрабов строки первичны в мышлении при обработке деревьев.
Тем более, если, например, в Оракле матриы задаются вообще не строками таблицы. Тут уж даже строки матрицы - и те приходится представлять мысленно.
...
Рейтинг: 0 / 0
09.12.2021, 18:40
| Ответить | Цитировать | Написать  
Найдите д.н.ф. и к.н.ф. для :
    #40118714
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
exp98

Случайный метод: от простого к сложному отжигом, роевым, генетическим ... пока таблица не станет хэммингово близкой к нужной. Затем доработать напильником, мож что и получится. Эффективность этого способа мне не известна.

Это офигенски интересно но я-бы начал с Квайна чтобы потом уже выйти на те методы
которые способны Квайна побить.
...
Рейтинг: 0 / 0
09.12.2021, 18:48
| Ответить | Цитировать | Написать  
Найдите д.н.ф. и к.н.ф. для :
    #40118720
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
exp98
В начале же ввёл обозначение для краткости А\В= А-В= "А без В" (между прочим тоже широко используется).

Ммм... такое себе. В С-подобных языках бэкслеш всегда имел особое значение. Типа эскейп-символа.
Вобщем его экранировать надо. Будет задвоение слешей. Насчет перегрузки операции - тоже самое
скорее всего.
...
Рейтинг: 0 / 0
09.12.2021, 19:07
| Ответить | Цитировать | Написать  
Найдите д.н.ф. и к.н.ф. для :
    #40118763
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Не навязываю, то было пятничным развлечением, и оно никому не понравилось.
однако насчёт реальности. Она существует и вне Си, и надпись А\В у мне со школьных лет, когда решались примеры для закрепления материала. Если танцевать от множеств:
А\В = A & !B = !(!A | B) = !(A=>B)
A Xor B = А\В + B\A = (A+B) \ (AB), (по последнему видно, почему знак "-" здесь тоже оправдан) след-но А\В = A & (A Xor B)
на выбор или вообще выбросить, мне всё равно.
Кстати Xor для множеств известен как "симметрическая разность" - ещё один аргумент для ограниченного использования минуса.
...
Рейтинг: 0 / 0
09.12.2021, 20:54
| Ответить | Цитировать | Написать  
Найдите д.н.ф. и к.н.ф. для :
    #40118812
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Это самая важная функция в криптографии.
...
Рейтинг: 0 / 0
10.12.2021, 00:14
| Ответить | Цитировать | Написать  
Найдите д.н.ф. и к.н.ф. для :
    #40124507
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Закрываю свой долг по некорректным функциям

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
  def f1(x : XBoolean, y : XBoolean, z : XBoolean) : XBoolean = !x ∪ z == (y ↓ !z)
  def f2(x : XBoolean, y : XBoolean, z : XBoolean) : XBoolean = (!x ⟶ z) | ((y ⟶ !z) | x)
  def f3(x : XBoolean, y : XBoolean, z : XBoolean) : XBoolean = !(z == (x | y)) ∩ (!x ⟶ z)


  def f1min(x : XBoolean, y : XBoolean, z : XBoolean) : XBoolean = (x ∩ !y) ∪ (x ∩ !z) ∪ (!y ∩ z)
  def f2min(x : XBoolean, y : XBoolean, z : XBoolean) : XBoolean = (!z) ∪ (!y ∩ x)
  def f3min(x : XBoolean, y : XBoolean, z : XBoolean) : XBoolean = (x ∩ y ∩ z) ∪ (x ∩ !y ∩ !z)

Метод Карно здесь хорошо работает. Просто я был невнимателен при переписывании объединённых
областей в формулу.
...
Рейтинг: 0 / 0
02.01.2022, 21:22
| Ответить | Цитировать | Написать  
13 сообщений из 88, страница 4 из 4
  4  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Найдите д.н.ф. и к.н.ф. для :
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru, Чат Кролика       Пашэ: Рисунки, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=40124507&tid=1339601]:
 0ms
get settings:
 3ms
get forum list:
 6ms
check forum access:
 1ms
check topic access:
 1ms
track hit:
 60ms
get topic data:
 3ms
get forum data:
 1ms
get page messages:
 237ms
get tp. blocked users:
 1ms
others: 363ms
total:  676ms
созд. / загр.: 676ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]