Курсова робота на тему: «МЕТОД ГРУБОЇ СИЛИ АБО ПОВНИЙ ПЕРЕБІР»

Зміст

Вступ    3

  1. Загальний опис методу грубої сили    4
  2. Задача сортування вибором та бульбашковим методом    6
  1. Задача про 8 ферзів    14
    1. Задача пошуку пари найближчих точок    23

    Висновки    26

    Література    27

 

Вступ

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

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

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

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

    1. Загальний опис методу грубої сили

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

    “Сила” у визначенні стратегії – сила комп’ютера, а не сила інтелекту, тобто сила з прислів’я “Сила є – розуму не треба”. Перефразовувати визначення даної стратегії можна простіше: “Нічого думати, треба діяти!”. Частенько стратегія грубої сили виявляється найбільш простій в застосуванні.

    Як приклад розглянемо завдання піднесення до степеня: обчислення
    для деякого числа а і невід’ємного цілого п. Хоча це завдання може показатися тривіальним, воно дозволяє проілюструвати декілька методів розробки алгоритмів, у тому числі і підхід грубої сили. (Відмітимо в дужках, що обчислення значення mod т для великих цілих чисел є основним компонентом провідних алгоритмів шифрування.) За визначенням піднесення до степеня

    .

    Звідси відразу слідує простий алгоритм обчислення

    шляхом множення на a початкового значення, рівного 1, п разів.

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

    Багато важливих завдань вимагають пошуку елементу із спеціальними властивостями в області, експоненціально (або ще швидше) зростаючій із збільшенням розміру екземпляра завдання. Зазвичай такі завдання виникають у випадках, коли присутні – явно або неявно – комбінаторні об’єкти, такі як перестановки, поєднання або підмножини даної множини. Багато подібних завдань є завданнями оптимізації: у них потрібно знайти елемент, який максимізував або мінімізує деякі характеристики, що цікавлять нас, як, наприклад, довжина шляху або призначена вартість.

    Вичерпним або повним перебором (exhaustive search) є підхід до комбінаторних завдань з позиції грубої сили. Він припускає генерацію всіх можливих елементів з області визначення завдання, вибір тих з них, які задовольняють обмеженням, умовою завдання, що накладається, і подальший пошук потрібного елементу (наприклад, що оптимізує значення цільової функції завдання). Відмітимо, що, хоча ідея вичерпного перебору вельми проста, її реалізація зазвичай вимагає алгоритму для генерації певних комбінаторних об’єктів.

     

    1. Задача сортування вибором та бульбашковим методом

    Сортування відносять до табличних і інших складних структур даних, тому виникає необхідність, перш за все, у вивченні цих складних структур даних, наприклад, лінійних і прямокутних масивів (таблиць). Структуру для представлення однорідної інформації в програмуванні прийнято називати масивом. (Фактично терміни таблиця і масив в даному контексті – повні синоніми).

    Важливе питання, на яке треба відповідати при рішенні реальних задач, – коли слідує і коли не слід об’єднувати прості змінні в таблиці. Ключ до відповіді – розуміння таблиці як складової величини, що містить однорідну інформацію. Однорідність означа, що всі елементи таблиці равноправні: мають однаковий зміст, сенс, при обробці виконуються однакові операції.

    Очевидно, що таблиця може бути результатом алгоритму(заповнення), аргументом (обробка) і аргументом-результатом (модифікація). При більш уважному розгляді стає ясно, що обробка (таблиця – аргумент) включає дуже великий клас задач, вирішуваних різними методами. Серед них можна виділити дві великі групи: задачі аналізу і задачі пошуку. В задачах аналізу вимагається проглянути всю таблицю і визначити якісь її характеристики (сума, кількість елементів із заданою властивістю і т.д.)

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

    Наприклад, відома задача про коректування звіту (елементи, меньші 100, замінити на 100) і їй подібні. Тому виділяти модифікацію як окремий клас задач не варто.

    ЗАВАНТАЖИТИ

    Для скачування файлів необхідно або Зареєструватись

    Metod Gruboi Syly (213.5 KiB, Завантажень: 5)

Сторінка: 1 2 3 4 5 6
завантаження...
WordPress: 23.38MB | MySQL:26 | 0,352sec