September 30
Грокаємо алгоритми: Ілюстрований посібник для програмістів і допитливих
“Алгоритм — це набір інструкцій для розвʼязання задачі.”
“Бінарний пошук - це алгоритм; вхідними даними для цього алгоритму є сортовані елементи”
“Якщо елемент, який ти шукаєш, є в цьому списку, бінарний пошук у відповідь на твій запит повертає його розташування. Якщо ж ні - пошуковий алгоритм поверне null”“для будь-якого списку з кількістю елементів п бінарний пошук буде виконуватися за log2 n кроків у найгіршому випадку, а простий пошук — за n кроків.”
“Нотація «О-велике» — це спеціальна нотація, яка описує, наскільки швидкий алгоритм.”
“Псевдокод — це високорівневий опис задачі, яку ти намагаєшся вирішити, але у вигляді коду. Він написаний як код, але наближено до людської мови.”
“Рекурсія — це коли функція викликає саму себе.”
“слова Лі Колдвела (Leigh Caldwell) зі Stack Overflow: «Застосування циклів може підвищити продуктивність програми. Рекурсія ж допоможе підвищити продуктивність програміста. Обирайте, що важливіше у вашій ситуації!» [Посилання на цитату Колдвела: http://stackover/#ow.com/a/72694/139117]”
“кожна рекурсивна функція складається з двох частин: базового та рекурсивного випадків. Рекурсивний випадок — це коли функція викликає саму себе. Базовий випадок — це коли функція не викликає себе знову… щоб не зациклитися.”
“алгоритм Евкліда. The Khan Academy пропонує чудове пояснення за посиланням: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm”
“Порада. Коли ти пишеш рекурсивну функцію, що включає масив базовим випадком часто буде пустий масив або масив із одним елементом. Якщо застряг, спочатку спробуй цей спосіб.”
“Склади хеш-функцію та масив разом, і ти отримаєш структуру даних, яка називається хеш-таблиця.”
“Граф - це модель, що зображає обʼєкти та звʼязки між ними.”
“Кожен граф складається з вершини та ребра (або дуги).”
“Графи складаються з вершин і ребер. Вершина (або вузол) може напряму звʼязуватися з багатьма іншими вершинами. Такі вершини будуть називатися сусідніми (або суміжними).”
“Графи — це спосіб зобразити, як різні речі повʼязані між собою.”
“Пошук у ширину — це пошуковий алгоритм іншого типу: той, який виконується на графах. Він допоможе знайти відповіді на два запитання: Тип запитання 1: Чи є шлях від вершини А до вершини Б?. Тип запитання 2: Який найкоротший маршрут від вершини А до вершини Б?”
“Пошук у ширину знаходить не просто шлях між вершинами А і Б, він визначає саме найкоротший із них.”
“у черзі можливі тільки дві операції: розміщення в черзі - enqueue, та видалення з черги - dequeue.”
“Знайомишся з алгоритмом Дейкстри, що дозволяє відповідати на запитання «Який шлях до Х найкоротший?» для зважених графів.”
“Коли ти працюєш із алгоритмом Дейкстри, кожне ребро графа має число, що з ним асоціюється. Це називається вагою.”
“Граф із вагою ребер називається зваженим графом.”
“Щоб розрахувати найкоротший шлях для ненавантаженого графа, використовують пошук у ширину. А для того, щоб розрахувати найкоротший шлях для зваженого, використовують алгоритм Дейкстри.”
“Ти не можеш застосовувати алгоритм Дейкстри, якщо твій граф має ребра негативної ваги. Негативне значення ребер ламає алгоритм.”
“ти не можеш залучити алгоритм Дейкстри на ребрах із відʼємною вагою. Якщо ти хочеш знайти найкоротший шлях для графа, де є ребра з відʼємною вагою, для цього існує свій алгоритм. Називається він алгоритмом Беллмана-Форда.”
“Пошук у ширину застосовується для розрахунку найкоротшого шляху ненавантаженого графа.”
“Алгоритм Дейкстри застосовується для розрахунку найкоротшого шляху зваженого графа.”
“Алгоритм Дейкстри працює тільки тоді, коли всі ребра мають позитивні значення.”
“Якщо у графі ти маєш ребра з відʼємною вагою, застосуй алгоритм Беллмана-Форда.”
“іноді досконале — це ворог хорошого. Часто потрібен алгоритм, який буде розвʼязувати задачу досить добре. І саме в цьому блиск жадібних алгоритмів, бо вони легкі в написанні та зазвичай дають достатньо близьку відповідь.”
“Це називається алгоритмом апроксимації. Коли розрахунок точного рішення вимагає завеликої кількості часу, апроксимаційний алгоритм спрацює. Апроксимаційні алгоритми оцінюються за тим, 1) наскільки вони швидкі, 2) наскільки близькі вони до оптимального рішення. Жадібні алгоритми завжди гарний вибір не тільки тому, що вони легкі в застосуванні, але й тому, що вони зазвичай швидко виконуються.”
“Задача комівояжера та задача про покриття множини мають дещо спільне: ти розраховуєш кожне можливе рішення й обираєш найменше / найкоротше з них. Обидві ці задачі є NP-повними (NP-complete).”
“не існує легкого способу визначення задач як NP-повних. Ось кілька порад: 1) Твій алгоритм працює швидко зі жменькою елементів, але сильно сповільнюється з кожним іх приростом. 2) «Усі комбінації з Х» зазвичай вказують на NP-повнузадачу. 3) Тобі треба розрахувати «усі можливі варіації» Х, бо ти не можеш розбити задачу на менші підзадачі? Це цілком може бути NP-повна. 4) Якщо твоя задача включає послідовність (таку як послідовність міст для комівояжера), 1 11 важко ви-рішити, це теж скоріше за все NP-повна задача. 5) Якщо твоя задача передбачає множини (як множини радіостанцій) і її важко вирішити, це може бути NP-повна задача. 6) Якщо твою задачу можна сформулювати як задачу про покриття множин або задачу комівояжера, тоді напевно віднесемо 11 до NP-повних задач.”
“Жадібні алгоритми легко писати та швидко вико-нувати, тому з них виходять гарні апроксимаційні (наближені) алгоритми.”
“Динамічне програмування починається з вирішення підзадач і далі вибудовує рішення для цілої задачі.”
“Динамічне програмування працює тільки тоді, коли кожна підзадача незалежна — коли вона не повʼязана з іншими підзадачами.”
“Динамічне програмування корисне, коли ти намагаєшся оптимізувати щось, наявне в обмеженій кількості. У задачі про пакування рюкзака тобі потрібно максимально збільшити цінність украдених речей, кількість яких обмежено місткістю рюкзака.”
“Ти можеш скористатися динамічним програмуванням, коли задачу може бути розбито на окремі менші підзадачі, незалежні одна від одної.”
“Далі кілька загальних порад: 1) Кожне рішення динамічного програмування включає таблицю. 2) Цінність кожної клітинки таблиці - це зазвичай те, що ти намагаєшся оптимізувати. У задачі з рюкзаком цінностями були ціни на вкрадені речі. 3) Кожна клітинка — це підзадача, а тому подумай, як саме ти будеш ділити свою задачу на менші підзадачі. Це допоможе тобі зрозуміти, що таке вісі.”
“Біологи використовують найдовшу спільну підпослідовність, щоб виявити схожості в ланцюжках ДНК. За її допомогою вони визначають, наскільки схожі дві тварини або два захворювання. Найдовшу спільну підпослідовність застосовують для пошуку ліків від розсіяного склерозу.”
“Функція diff визначає відмінності між двома файлами, і працює вона саме за принципом динамічного програмування.”
“Алгоритм к-найближчих сусідів (KNN) простий, але дуже корисний! Якщо ти намагаєшся щось класифікувати, варто спробувати застосувати саме його.”
“OCR —це акронім до optical character recognition (оптичне розпізнавання символів). Це значить, що ти можеш зробити фото сторінки з текстом, і твій компʼютер автоматично прочитає цей текст для тебе.”
“KNN (алгоритм k-найближчих сусідів) використовується для класифікації та регресії, що містить пошук k-найближчих сусідів.”
“Класифікація = категоризація по групах.”
“Добір правильних ознак — важлива складова успішної роботи алгоритму KNN.”
“Б-дерева — спеціальний тип бінарних дерев, що часто застосовується для зберігання інформації у базах даних.”
“Kalid, “An interactive Guide to the Fourier Transform,” Better Explained”
“MapReduce використовує дві прості концепції виконання запитів щодо даних на багатьох машинах. Коли ти маєш великий набір даних (мільярди рядків), MapReduce дасть відповідь на запит протягом кількох хвилин, тоді як традиційна база даних може зайняти години.”
“Фільтри Блума пропонують рішення. Фільтри Блума - це ймовірнісна структура даних. Вони дають тобі відповідь, яка може бути помилковою, але скоріше за все правильна. Замість хешу ти можеш запитати фільтри Блума, чи ти сканував ці сторінки раніше. Хеш-таблиця дасть тобі точну відповідь. А фільтри Блума дадуть відповідь, яка скоріше за все правильна: 1) Хибно позитивні можливі. Google сказав би «Ти вже перевіряв цей сайт», навіть якщо насправді ні. 2) Хибно негативні неможливі. Якщо фільтр Блума від-повідає: «Ти не сканував цей сайт», тоді ти точно його ще не сканував.”
“Ти можеш використати SHA, щоб сказати, чи однакові два файли. Це дуже зручно, коли ти маєш дуже великий список файлів.”
“Лінійне програмування (або лінійну оптимізацію) використовують для максимального збільшення того, що має певні обмеження.”
“Лінійне програмування — це загальніший метод, а задачі на графах — його підрозділ.”