Агата Сомова · старший инспектор, Седьмой отдел
Двадцать показаний, двадцать атомов. Таблица на миллион строк мне не нужна. Мне нужна одна строка, где выполнены все требования, или твёрдая уверенность, что такой строки нет. Найдёшь её до утра?
В таблице с двадцатью атомами строк. Если проверять по строке в минуту, уйдёт два года. Компьютер справится быстрее, но добавь ещё двадцать атомов, и строк станет в миллион раз больше. Таблица хороша для учебных карточек, а для настоящего дела нужен другой способ.
Сегодня ты научишься искать подходящую строку так, как ищет её хороший следователь: делать предположение, сразу выводить из него всё, что можно, и откатываться, как только упёрся в противоречие. Этот способ называется DPLL, и на нём стоят программы, которые каждый день решают такие задачи с сотнями тысяч переменных.
урок из курса
Урок из курса «Логика и типы». Курс покупается один раз и остаётся навсегда: 500 ₽.
Оплата пока не подключена: премиум и курсы открываются промокодом.