✅ Алгоритм грубої сили - Вивчіть основні поняття алгоритму Brute Force

Вступ до алгоритму грубої сили

Вступ до алгоритму грубої сили

"Дані - це нова нафта". Це нова мантра, яка керує світовою економікою. Ми живемо в цифровому світі, і кожен бізнес обертається навколо даних, які перетворюються на прибуток і допомагають галузям випереджати свою конкуренцію. Зі швидкою оцифровкою, експоненціальним зростанням бізнес-моделі на основі додатків кібер-злочини є постійною загрозою. Однією з таких поширених видів діяльності, яку виконують хакери, є сила Брута.

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

Пошуки грубої сили

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

Алгоритм грубої сили шукає всі позиції в тексті між 0 і нм, починається там поява візерунка чи ні. Після кожної спроби вона зміщує візерунок праворуч рівно на 1 положення. Часова складність цього алгоритму становить O (m * n). тож якщо ми шукаємо n символів у рядку з m символів, знадобиться n * m спроб.

Давайте подивимось класичний приклад мандрівного продавця, щоб зрозуміти алгоритм легко.

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

Іншим прикладом є спроба зламати 5-значний пароль, тоді груба сила може зайняти до 10 ⁵ спроб зламати код.

Сортування грубої сили

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

Вищенаведене твердження можна записати в псевдокод наступним чином.

Тут проблема полягає в розмірі 'n', а основна операція - тест 'if', де елементи даних порівнюються в кожній ітерації. Різниця між найгіршим та найкращим випадком не буде, оскільки ні своп завжди n-1.

Збігання струнної грубої сили

Якщо всі символи в шаблоні унікальні, то зіставлення рядкової сили Brute можна застосувати зі складністю Big O (n). де n - довжина рядка. Сила брутального зіставлення рядків порівнює візерунок із підрядкою текстового символу за символом, поки він не отримає невідповідний символ. Як тільки буде виявлено невідповідність, залишився символ підрядки скидається, і алгоритм переходить до наступної підрядки.

Наведені нижче псевдокоди пояснюють логіку відповідності рядків. Тут алгоритм намагається шукати візерунок P (0… m-1) у тексті T (0… .n-1).

тут найгіршим випадком було б, коли перехід на іншу підрядку не буде здійснено до порівняння M ^Th .

Найближча пара

Постановка проблеми: з'ясувати дві найближчі точки у наборі n точок у двовимірній декартовій площині. Існує n кількість сценаріїв, де виникає ця проблема. Прикладом реального життя може бути система управління повітряним рухом, де ви повинні стежити за літаками, що летять поруч один з одним, і ви повинні з'ясувати найбезпечнішу мінімальну відстань, яку ці літаки повинні витримувати.

Джерело: Вікіпедія

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

Сила брута вирішує цю задачу за часовою складністю (O (n2)), де n - кількість точок.

Нижче псевдо-код використовує алгоритм грубої сили, щоб знайти найближчу точку.

Опуклий корпус

Постановка проблеми : Опуклий корпус - найменший багатокутник, який містить усі точки. Опуклий корпус множини s точки - це найменший опуклий багатокутник, що містить s.

Опуклий корпус для цього набору точок - це опуклий багатокутник з вершинами при P1, P5, P6, P7, P3

Лінійний відрізок P1 і Pn множини з n точок є частиною опуклого корпусу тоді і тільки тоді, коли всі інші точки множини лежать всередині межі полігона, утвореної відрізком лінії.

Давайте пов'язуємо це з гумкою,

Точки (x1, y1), (x2, y2) роблять пряму ax + через = c

Коли a = y2-y1, b = x2-x1 і c = x1 * y2 - x2 * y1 і ділить площину на ax + by-c 0

Тому нам потрібно перевірити ax + by-c для інших точок.

Брутальна сила вирішує цю проблему з часовою складністю O (n ³ )

Вичерпний пошук

Для дискретних проблем, в яких невідомо ефективного рішення, стає необхідністю перевірити кожне можливе рішення послідовно.

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

Спробуємо вирішити проблему продавця подорожей (TSP) за допомогою вичерпного алгоритму пошуку Brute.

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

Ми розглядаємо схему Гамільтона для вирішення цієї проблеми. Якщо схема існує, то будь-яка точка може починати вершини та закінчувати вершини. Після вибору початкових вершин нам знадобиться лише порядок для інших вершин, тобто n-1

Тоді було б (n-1)! Можливі комбінації та загальна вартість обчислення шляху буде O (n). таким чином, загальна часова складність буде O (n!).

Висновок

Тепер, коли ми досягли кінця цього підручника, я сподіваюся, що ви, хлопці, тепер добре зрозуміли, що таке Brute Force. Ми також бачили різні алгоритми Brute force, які можна застосувати у своїй програмі.

Алгоритм грубої сили - Вивчіть основні поняття алгоритму Brute Force