Головна

Проектування повно переборних алгоритмів

  1.  II. Достатність і максимально можлива конкретизація повноважень поліції
  2.  II. повноваження
  3.  II. повноваження
  4.  II. повноваження
  5.  III. повноваження міністерства
  6.  IV. Формула повної ймовірності. формули Байєса
  7.  Агентства повного циклу

Сформулювати завдання, згідно варіантами, зазначеними викладачем, (див. Нижче варіанти завдань) на мові теорії множин або теорії графів.

Визначити, що для даних задач є траєкторіями, функціоналами і оптимальними значеннями функціоналів.

Розробити алгоритми вирішення задач. Для цього звести перебір траєкторій до генерації тих чи інших комбінаторних об'єктів і, якщо необхідно, організувати відбір траєкторій, що відповідають оптимальному значенню функціоналів [10]. Приклад рішення одним із завдань дивись нижче.

Реалізувати алгоритми вирішення задач.

Підготувати відповіді на наступні контрольні питання:

Поняття завдання вибору. Що характерно для задач вибору?

Поняття траєкторії і функціоналу.

Основні поняття теорії графів.

Матричне завдання графів.

варіанти завдань

підмножина V вершин графа G називається незалежним (або внутрішньо стійким), якщо ніякі дві вершини з V не суміжні. Знайти найбільше за потужністю незалежне безліч вершин заданого графа.

підмножина V вершин графа G називається домінуючим (або зовні стійким), якщо кожна вершина з VG\V суміжно з деякою вершиною з V. Знайти найменше за потужністю домінуюче безліч вершин заданого графа.

Потрібно розставити на шахівниці найбільше число ферзів так, щоб вони не атакували один одного.

вказівка: Зведіть завдання до завданню пошуку незалежного безлічі вершин графа максимальної потужності (завдання №1).

Потрібно розставити на шахівниці найменше число ферзів так, щоб кожна клітина була під боєм.

вказівка: Зведете задачу до задачі пошуку домінуючого безлічі вершин графа меншої потужності (завдання №2).

заданий граф G, Все ваги ребер рівні 1. Знайти найменше підмножина вершин VIVG, Таке, що кожна вершина графа повинна знаходитися на відстані не більше 1 від будь-якої вершини з V.

вказівка: Встановіть зв'язок між цим завданням і завданням № 2.

підмножина VIVG називається покриттям (верховим покриттям, опорою) графа G, Якщо кожне ребро з ЕG інцидентне хоча б одній вершині з V. Знайти покриття мінімальній потужності заданого графа.

вказівка: Встановіть зв'язок між цим завданням і завданням пошуку незалежного безлічі вершин графа максимальної потужності (завдання №1).

підмножина V вершин графа G називається клікою, якщо будь-які дві входять до нього вершини суміжні, тобто поняття кліки є антиподом поняття незалежного безлічі (див. задачу №1). Знайти кліку максимальної потужності для заданого графа.

підмножина ребер ЕIЕG називається ребровим покриттям графа G, Якщо кожна вершина з VG инцидентна хоча б одному ребру з Е. Знайти всі реберні покриття заданого графа G.

Підмножина попарно несуміжних ребер графа називається паросочетание (або незалежним безліччю ребер). Знайти всі паросполучення заданого графа.

Паросочетание (див. Задачу №9) називається досконалим (або 1-фактором), якщо воно одночасно є реберним покриттям (див. Задачу №8). Знайти всі вчинені паросполучення заданого графа.

Є кінцеве безліч виконавців {х1, ...,хn}, Кожен з яких може виконувати деякі з робіт {у1, ...,уn}. Для кожного виконавця наведено списку робіт, які він може виконувати. Потрібно розподілити виконавців по роботах, тобто призначити по одному виконавцю на кожну роботу, так, щоб виконати всі роботи. Знайти всі можливі розподілу виконавців по роботах.

вказівка: Звести задачу до задачі №10.

Те ж, що і завдання №11, тільки задана вартість виконання роботи уi виконавцем хi, І потрібно розподілити виконавців по роботах, мінімізуючи витрати.

два графа G1 и G2 називаються ізоморфними, якщо існує взаємно однозначна відповідність f:VG1®VG2, Таке, що (v,w) IEG2, Тоді і тільки тоді, коли (f(v),f(w)) IEG, Тобто існує відповідність між вершинами графа G1 і вершинами графа G2, Що зберігає відношення суміжності (графи G1 и G2 відрізняються тільки нумерацією вершин). Визначити, чи є два заданих графа ізоморфними.

Задані два графа G1 и G2. Потрібно визначити, чи існує в G2 породжений підграф, ізоморфний графу G1.

задані безліч А і безліч В, Причому елементами останнього служать деякі підмножини з першого, і В є покриттям безлічі А, Що означає наступне: об'єднання всіх елементів з В, Тобто відповідних підмножин з А, Так само безлічі А. Потрібно знайти всі покриття безлічі А, Складені з елементів безлічі В.

є n верстатів. Кожен з верстатів робить різні операції (які задано). При обробці деталі необхідно виконати k заданих операцій. Знайти мінімальне безліч верстатів, необхідних для обробки деталі.

Визначити, чи має заданий неорієнтовані граф гамільтонів цикл.

всього n робітників. У виїзній бригаді повинні знаходитися робочі, які всі разом володіють не менш ніж k заданими спеціальностями. Для кожного робочого наведено списку його спеціальностей. Сформувати бригаду з мінімального числа робочих.

Чи існує рішення в (0,1) - числах наступного рівняння: , и b задані.

необхідно перевести n тонн вантажу. є k літаків вантажопідйомністю s1,s2, ...,sk тонн,  . вартість рейсу c1,c2, ...,ck руб. не залежить від маси вантажу, що перевозиться літаком. Знайти оптимальне безліч літаків для перевезення вантажу.

Те ж, що і завдання №21, тільки c1,c2, ...,ck залежать від маси вантажу.

Отримати всі можливі бінарні відносини між елементами кінцевого n-елементного безлічі, що задовольняють умовам симетричності і антирефлексивне.

Отримати всі можливі бінарні відносини між елементами кінцевого n-елементного безлічі, що задовольняють умовам антисиметричність.

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

 
 

 Знайти всі матриці розміру n?n з елементами з множини {0,1}, що задовольняють наступним умовам:

Місто розділене вулицями на квадрати зі стороною рівною 1 од. Таких квадратів в напрямку з півночі на південь n, а в напрямку із заходу на схід - m. Перерахувати всі найкоротші шляхи з крайньої північно-західної точки міста в крайню південно-східну точку. Кожен шлях видавати на екран. Вимоги до графічного представлення шляху не висуваються. Шлях може бути зображений за допомогою символів "|" і "_".

Приклад представлений на рис 6.

 
 


Перерахувати всі способи розстановки n-тур на «шахової» дошці розміру n'n. Причому ніякі дві тури не повинні стояти на одній вертикалі або горизонталі (тури не повинні атакувати один одного). Вимоги до графічного представлення тур і шахівниці не висуваються. Для зображення розташування тури можна використовувати будь-який символ.

Задано безліч предметів. Для кожного предмета відомий його вага. Чи можна розділити предмети на дві рівні за вагою частини.

Розробити алгоритм генерації всіх логічних функцій n-змінного. Функції видати в СДНФ.

Розробити алгоритм генерації всіх самодвоїстих логічних функцій n-змінного. Функції видавати в СДНФ.

Розробити алгоритм генерації всіх лінійних логічних функцій n-змінного. Функції видавати у вигляді полінома.

Перевірити, чи не містить рядок символів представляє логічну функцію в ДНФ синтаксичних помилок, і обчислити таблицю істинності цієї функції.

Наприклад, логічна функція  може бути представлена ??наступним рядком ^ x1 & x2Vx2 & ^ x3 & x4Vx3 & x5. Цей рядок не містить синтаксичних помилок. Рядок ^ x1 & x2Vx2 & ^ x3 & x4V & x5 містить синтаксичну помилку в 17-ій позиції.

Перевірити, чи не містить рядок символів представляє логічну функцію в довільній формі синтаксичних помилок, і обчислити таблицю істинності цієї функції.

Наприклад, логічна функція  може бути представлена ??наступним рядком ^ ((^ x1 & x2Vx4) & ^ x3V ^ (x5 & x6)). Цей рядок не містить синтаксичних помилок. Рядок ^ ((^ x1 & x2Vx4) & ^ x3V ^ (x5 & x6) містить синтаксичну помилку в 26-ій позиції - немає закривається дужки.

Задана логічна функція в ДНФ. Кожна елементарна кон'юнкція кодується двома векторами - вектором входження (  ) І вектором звернення (  ). Елементи векторів визначаються наступним чином:

Обчислити таблицю істинності заданої логічної функції.

Наприклад, логічна функція  може бути закодована в масиві з двох елементів. Кожен елемент представляє собою структуру з двох полів - и  (Рис.7). Символ «*» позначає будь-яке значення - 0 або 1. Зазвичай вектора и  зберігають в бітової формі (для зберігання елементів и  використовується 1 біт).

  1   2  
VV
VO * * *
                     
 рис.7

Логічна функція записана в ДНФ з використанням загальноприйнятих угод (знак кон'юнкції опускається; нумерація змінних здійснюється натуральними числами від 1 до n, де n - число змінних). Такий запис закодована в масиві  наступним чином:

Обчислити таблицю істинності заданої логічної функції.

Наприклад, логічна функція  буде закодована в масиві  як показано на рис.8.

1 2 3 4 5 6
 -2  -3  -4
 рис.8

Логічна функція задана в СДНФ. Кожна кон'юнкція кодується вектором входження і вектором звернення, см. Задачу 34. Виконати всі можливі склеювання.

Наприклад, в логічній функції  можна виконати наступні склеювання: и  . Т.ч. в результаті виконання всіх можливих склеювання отримаємо елементарні кон'юнкції и  . Тобто з вихідного масиву A необхідно отримати масив B (Рис.9).

A 1   2   3
 VV
 VO
B 1   2
 VV
 VO * *
 рис.9

Логічна функція задана в СДНФ. Кожна кон'юнкція кодується вектором входження і вектором звернення, см. Задачу 34. Виконати всі можливі склеювання і всі можливі поглинання.

вказівка. Використовувати список, кожна компонента списку зберігає вектор входження і звернення.

для функції  процес формування списку зображений на рис.10.


Дві логічні функції задані в ДНФ. Кожна кон'юнкція кодується вектором входження і вектором звернення, см. Задачу 34. Перевірити функції на еквівалентність.

Дві логічні функції f і g задані в ДНФ. Кожна кон'юнкція кодується вектором входження і вектором звернення, см. Задачу 34. Перевірити чи є функція g импликанте функції f.

Дві логічні функції f і g задані в ДНФ. Кожна кон'юнкція кодується вектором входження і вектором звернення, см. Задачу 34. Перевірити чи є функція g простим импликанте функції f.

Дві логічні функції f і g задані в ДНФ. Кожна кон'юнкція кодується вектором входження і вектором звернення, см. Задачу 34. Перевірити чи є функція g двоїстої до f.

Логічна функція задана в ДНФ. Кожна кон'юнкція кодується вектором входження і вектором звернення, см. Задачу 34. Перевірити чи є задана функція самодвоїстих.

логічна функція f задана таблицею істинності. Знайти поліном Жегалкина функції f.

вказівка. Для знаходження полінома Жегалкина можна використовувати метод невизначених коефіцієнтів, Що складається в наступному. Розглядається поліном у вигляді

і для кожного набору  складається рівняння  . Рішення цих рівнянь дає коефіцієнти  полінома  . Наприклад, задана логічна функція  , Її поліном має вигляд

Складемо систему рівнянь.

знаходимо ,  . Таким чином, .

Логічна функція задана в ДНФ. Кожна кон'юнкція кодується вектором входження і вектором звернення, см. Задачу 34. Знайти поліном Жегалкина заданої функції.

Логічна функція задана в ДНФ. Кожна кон'юнкція кодується вектором входження і вектором звернення, см. Задачу 34. Знайти всі істотні змінні заданої функції.

Логічна функція задана в ДНФ. Кожна кон'юнкція кодується вектором входження і вектором звернення, см. Задачу 34. Знайти всі фіктивні змінні заданої функції.

Логічна функція задана в ДНФ як в завданні 35. Визначити чи є в функції фіктивні змінні.

Розробити і обгрунтувати структури даних для зберігання импликантной матриці (матриці Квайна). За заданою импликантной матриці знайти всі тупикові ДНФ логічної функції.

Визначити таблицю істинності логічної функції заданої бінарним графом.

Використовуючи формулу розкладання логічної функції по змінній будь-яку логічну функцію  можна представити в такий спосіб

Використовуючи цю формулу, можна уявити логічну функцію у вигляді бінарного графа, В якому є тільки одна вершина без входять до неї дуг (початкова); всі вершини по числу виходять дуг діляться на два типи: вершини з двома вихідними дугами (умовні вершини), вершини без вихідних дуг (заключні вершини). Дуги позначаються символами 0 і 1. Умовні вершини позначаються символом змінної, заключні - Комада "  ".

 Приклад бінарного графа, що задає функцію  , Наведено на рис. 11. Тут вершини  - Початкова; , и  - Умовні; и  - Заключні.


Кожному набору значень аргументів в БГ відповідає шлях з початкової вершини в заключну вершину. Таким чином, БГ кожному набору значень аргументів ставить у відповідність значення функції і може служити для її завдання і обчислення. Різним наборам може відповідати один і той же шлях. Наприклад, для графа, зображеного на рис.11, наборам и  відповідає шлях .

Дано два бінарних графа (див. Попередню задачу). Визначити задають ці графи одну і ту ж логічну функцію.

Наприклад, бінарні графи, зображені на рис. 11 і 12 задають одну і ту ж логічну функцію .

 
 


приклад рішення

є n різних предметів, відомі маса кожного предмета і його вартість. Визначити, які предмети треба покласти в рюкзак, щоб загальна маса не перевищувала заданої межі, а загальна вартість була максимальна.

Траєкторією даного завдання є підмножина вибраних предметів (предметів покладених в рюкзак), функціоналом - вартість даних предметів. Таким чином, для вирішення завдання необхідно перебрати всі 2n підмножин предметів і знайти підмножина, що задовольняє умовам завдання.

Нехай маса і вартість предметів зберігаються в масиві записів MS. Кожен запис містить два поля: M - Маса предмета і S - Вартість предмета. В змінної n зберігається число предметів, в змінної MaxSM - Максимальна сумарна маса обраних предметів.

Поточне підмножина предметів будемо зберігати в масиві b, в котрому b[i] = 1, якщо i-й предмет належить підмножині, і b[i] = 0, якщо i-й предмет не належить підмножині. Сумарну вартість і масу предметів складових поточний підмножина будемо зберігати в змінних SS и SM відповідно. Для запам'ятовування підмножини обраних предметів будемо використовувати масив b1 аналогічний масиву b. Сумарну вартість обраних предметів будемо зберігати в змінної MaxSS.

Укрупненная блок-схема алгоритму розв'язання задачі представлена ??на рис.11.

У додатку 3 (варіант 1) представлена ??реалізація алгоритму розв'язання задачі на мові Turbo Pascal. При цьому для організації перебору траєкторій узятий алгоритм породження підмножин в порядку довічного рахунку (алгоритм 1).

Якщо при організації перебору траєкторій за основу взяти алгоритм породження підмножин в порядку мінімального зміни (алгоритм 3), то швидкодія алгоритму може бути підвищено. Це досягається за рахунок більш швидкого підрахунку функціоналу.

Дійсно якщо підмножини породжуються в порядку мінімального зміни, то поточний підмножина відрізняється від попереднього тільки одним елементом. Тому для підрахунку сумарної вартості предметів складових поточний підмножина (змінна SS) Не треба підсумовувати вартість кожного з цих предметів. Досить виконати тільки одну з дій:

- Якщо перехід від попереднього підмножини предметів до поточного подмножеству здійснюється шляхом видалення деякого предмета, то необхідно від вартості предметів складових попереднє підмножина відняти вартість даного предмета;

- Якщо перехід від попереднього підмножини предметів до поточного подмножеству здійснюється шляхом додавання деякого предмета, то необхідно до вартості предметів складових попереднє підмножина додати вартість даного предмета.

Сказане стосується і до підрахунку сумарної маси предметів складових поточний підмножина (змінна SM).

Реалізація алгоритму розв'язання задачі на мові Turbo Pascal з використанням алгоритму породження підмножин в порядку мінімального зміни представлена ??в додатку 3 (варіант 2).



 СПИСОК ЛІТЕРАТУРИ


Айгнер М. Комбінаторна теорія. - М .: Світ, 1982. - 556 с.

Ахо Х., Хопкрофта Дж., Ульман Дж. Побудова і аналіз обчислювальних алгоритмів. - М .: Світ, 1979. - 536 с.

Гаврилов Г. П., Сапоженков А. А. Збірник завдань з дискретної математики. - М .: Наука, 1977. - 368 с.

Горбатов В. А. Основи дискретної математики: Учеб. посібник для студентів вузів. - М .: Вища. шк., 1986. - 311 с.

Гері М., Джонсон Д. Обчислювальні машини і труднорешаемие завдання. - М .: Світ, 1982. - 416 с.

Єжов І. І., Скороход А. В., Ядренко М. І. Елементи комбінаторики: Пер. з укр. - М .: Наука. Гл. ред. фіз.-мат. лит., 1977.-80 с.

Комп'ютер і завдання вибору / Автор предисл. Журавльов Ю. І.-М .: Наука, 1989.-208 с. - (Теорія "Кібернетика - необмежені можливості і можливі обмеження").

Кузнєцов О. П., Адельсон-Бєльський Г. М. Дискретна математика для інженера. - 2-е изд., Перераб. і доп. - М .: Вища школа, 1988. -480с.

Лавров І. А., Максимова Л. Л. Завдання з теорії множин, математичної логіки та теорії алгоритмів. - М .: Наука, 1975. - 240 с.

Лекції з теорії графів / В. А. Емелічев, О. І. Мельников, В. І. Сарванов, Р. І. Тишкевіч.- М .: Наука. Гл. ред. фіз.-мат. лит., I990.-384 с.

Муромцев В. В. Методи синтезу логічних схем: Навчальний посібник. Білгород: Вид-во БелГТАСМ, 1994. - 78 с.

Прикладна теорія цифрових автоматів / К. Г. Самофалов,
 А. М. Романкевич, В. Н. Валуйский і ін. - К .: Вища шк., 19897. - 375 с.

Рейнгольд Е., Нівергельт Ю., Део Н. Комбінаторні алгоритми (теорія і практка): Пер. з англ. - М .: світ, 1980.- 476 с.

Шолом Л. А. Основи теорії дискретних логічних і обчислювальних пристроїв. - М .: Наука, 1980. - 400с.




 Рішення комбінаторних задач |  ГЕНЕРАЦІЯ ВИПАДКОВИХ ЧИСЕЛ

 Вступ |  Загальні підходи до породження комбінаторних об'єктів |  Алгоритми породження підмножин |  Алгоритми породження поєднань |  Алгоритми породження перестановок |  Алгоритм породження розбиття |  Поняття завдання вибору |  Пошук з поверненням |  Використання алгоритмів породження елементарних комбінаторних об'єктів при проектуванні полнопереборних алгоритмів розв'язання задач вибору |  ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ |

© um.co.ua - учбові матеріали та реферати