Приложение на общите комбинаторни методи за решение на известни екстремални задачи. Задача за търговския пътник. Задача за раницата.


Категория на документа: Математика


ТЕМА 2/6. Приложение на общите комбинаторни методи за решение на известни комбинаторни задачи

Аудиторно упражнение

Някои интересни задачи, допускащи решение чрез метода на изчерпващото търсене или негови модификации са следните:

1. Задача за щастливите билети. Даден билет е щастлив, ако сумата от първите три цифри на шестцифрения му номер му съвпада със сумата на последните три. Да се намерят номерата на всички щастливи билети.

*Потенциалните решения са шестцифрените числа. Генерираме ги последователно и за всяко проверяваме изпълнението на условието.

2. Задача за изпълнимост. За какви стойности на булевите променливи X1, X2, X3 и X4 има стойност "истина" изразът:

(X1  X4)  ( X2)  (X1  )  ( X3  4)  (   )

3. Задача. за дешифриране на кодове. Да се състави математически модел на задачата за отгатване на n - битов код, да се оцени мощността на множеството от потенциални решения и да се предложи алгоритъм за решение чрез изчерпващо търсене.

Санкционирането на достъпът до информация в компютърните мрежи е свързано с използване на ключове. При дължина на ключа n-двоични разряда, "отгатването" на такъв ключ е свързано с генериране и проверка за съвпадение на 2n двоични вектори с дължина n. Задачата е NP-пълна, с временна сложност О(2n).

­ 64 бита: 18 446 744 073 709 551 616 възможни ключа;

­ 128 бита: 340 282 366 920 938 463 463 374 607 431 768 211 456 възможни ключа;

­ 256 бит: 115 792 089 237 316 195 423 570 985 008 687 907 853 269 984 665 640 564 039 457 584 007 913 129 639 936 възможни ключа.

От статистическа гледна точка средно трябва да проверим половината ключове, докато получим правилния. Ако дължината на ключа е 56 бита, средностатистически трябва да изпълним 255 (36028797018963968) итерации. Всеки допълнителен бит удвоява количеството на възложните ключове и съответно времето за реализиране на изчерпващо търсене. Интересен пример за сравнение: на 22 август 1999: число с размеро 155 десетични цифри (512 бита) е факторизирано за шест месеца изчисления. Използвани са около 600 изчислителни машини.

4. Задача. Пресметнете времето за "разбиване" на 64 - битов код, ако компютърът извършва 1 000 000 операции в секунда.

5. Задача за раницата. Оптимизационен вариант: Двама приятели решили да отидат на поход. За целта подготвили и претеглили всички необходими вещи. Как да ги разделят на две части по възможно най- честния начин?

Формално: дадено е множество от натурални числа, някои от които могат да съвпадат. Необходимо е да се раздели на две подмножества по такъв начин, че разликата от сумата на теглата да бъде минимална.

В литературата има и други постановки на задачата за раницата.

Дадено е крайно множество от предмети U. За всеки предмет u  U е зададен размер s(u)  Z+ и цена v(u)  Z+. Освен това, са зададени целите положителни числа B и K.. Съществува ли такова подмножество U'  U, че:

 s(u)  B и  v(u)  K?

u  U' u  U'

Да се предложи математически модел на задачата и алгоритъм за решение чрез изчерпващо търсене.

Задачата е NP - пълна с временна сложност 2n, където n е броят на предметите.

6. Задача на Айнщайн.

Има 5 къщи, оцветени в различен цвят.

Във всяка къща живее един човек - немец, англичанин, швед, датчанин, норвежец.

Всеки от живущите пие точно определена напитка, пуши определена марка цигари и отглежда определено животно.



Сподели линка с приятел:





Яндекс.Метрика
Приложение на общите комбинаторни методи за решение на известни екстремални задачи. Задача за търговския пътник. Задача за раницата. 9 out of 10 based on 2 ratings. 2 user reviews.