# data[].attributes.headline
17.01.2024 Загальні відомості про запити

# data[].attributes.subject
17.01.2024 Загальні відомості про запити

# data[].attributes.body
Запит — це один із основних об'єктів БД Access 2016. Головним призначенням запиту є відбір із таблиць потрібних даних, їх опрацювання й подання користувачеві в зручній формі.

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

До простих запитів належать такі, за якими вибираються дані за критерієм одного поля однієї таблиці. Наприклад, простими є такі запити: вибрати з таблиці

МАГАЗИНИ ті номери магазинів, де кількість працівників більше 13, вибрати з таблиці КАДРИ прізвища тих працівників, які народилися після 1979 року.

До складних належать запити, за якими формуються дані з кількох таблиць за критеріями кількох полів.

У запитах різних типів найчастіше реалізуються такі операції:

вибір даних із вказаних полів на основі заданих критеріїв;

упорядкування даних із таблиць за значеннями вказаних полів;

побудова нової таблиці або діаграми з отриманих даних;

опрацювання вибраних із таблиць даних за допомогою вбудованих функцій;

використання отриманих за допомогою запиту даних як джерела для інших запитів;

додавання даних, отриманих за допомогою запитів, до інших таблиць;

обмін даними з іншими БД, а також текстовим редактором Word і таблицями Excel.

У запитах можуть використовуватися специфічні оператори.

# data[].attributes.headline
26.12.2023 Уведення, пошук і редагування даних у таблиці

# data[].attributes.subject
26.12.2023 Уведення, пошук і редагування даних у таблиці

# data[].attributes.body
Дані в таблиці можна вводити після створення їх структур. Існує два способи введення даних у таблиці: за допомогою форм і безпосереднє введення даних таблиці.

Під час уведення даних автоматично перевіряються такі типи даних: числові, грошові, дата і час, логічні.

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

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

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

# data[].attributes.headline
27.12.2023 Сортування та фільтрація записів. Операції над таблицями.

# data[].attributes.subject
27.12.2023 Сортування та фільтрація записів. Операції над таблицями.

# data[].attributes.body
Сортуванням називають розташування записів таблиці в порядку зростання чи спадання значень певного поля. Сортування, нагадаємо, найчастіше застосовують у випадках, коли:

v необхідно дізнатися, які об’єкти мають малі, великі, найменші або найбільші значення тих чи інших параметрів (адже після сортування такі об’єкти розміщуватимуться на початку таблиці);

v потрібно згрупувати об’єкти за певним параметром, тобто розташувати поряд об’єкти з однаковими чи близькими його значеннями.

Як і в табличному процесорі, фільтрація в СКБД Microsoft Access дозволяє відобразити тільки ті записи таблиці, що задовольняють певну умову. Щоб виконати фільтрацію, слід відкрити таблицю і клацнути кнопку (Змінити фільтр), що розташована на панелі інструментів у MS Access 2003. У MS Access 2007/2010 аналогічну команду розміщено на стрічці Главная в області Сортировка и фильтр у меню кнопки Дополнительно.

# data[].attributes.headline
20.12.2023 Класифікація зв’язків за множинністю та обов’язковістю

# data[].attributes.subject
20.12.2023 Класифікація зв’язків за множинністю та обов’язковістю

# data[].attributes.body
У базах даних зв'язки між таблицями можуть мати різні характеристики, такі як множинність (як кілька записів з таблиці A може бути пов'язано з кількома записами з таблиці B) та обов'язковість (чи є у зв'язку обов'язковий запис в одній з таблиць). Класифікація зв'язків включає такі типи:

За множинністю:

1. Один до одного (1:1):

Кожен запис у першій таблиці пов'язаний з одним записом у другій таблиці, і навпаки.

2. Один до багатьох (1:N):

Кожен запис у першій таблиці пов'язаний з багатьма записами у другій таблиці, але кожен запис у другій таблиці може мати лише один запис у першій таблиці.

3. Багато до багатьох (M:N):

Кожен запис у першій таблиці пов'язаний з багатьма записами у другій таблиці, і навпаки. Це реалізується через додаткову (проміжну) таблицю.

За обов'язковістю:

1. Обов'язковий зв'язок (mandatory/required):

Кожен запис у першій таблиці пов'язаний з одним чи більше записами у другій таблиці.

2. Необов'язковий зв'язок (optional):

Кожен запис у першій таблиці може бути пов'язаний з нулем чи одним записом у другій таблиці.

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

# data[].attributes.headline
19.12.2023 Основні відомості про СУБД Access.

# data[].attributes.subject
19.12.2023 Основні відомості про СУБД Access.

# data[].attributes.body
Microsoft Access є системою управління базами даних (СУБД) та частиною пакета Microsoft Office. Основні відомості про Microsoft Access включають:

1. Інтерфейс:

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

2. Таблиці:

Основною одиницею зберігання даних в Access є таблиці. Вони можуть містити різні типи даних, такі як текст, числа, дата та інші.

3. Запити:

Access надає можливості створення запитів для вибірки, фільтрації та обробки даних з таблиць.

4. Форми:

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

5. Звіти:

Дозволяють створювати різні види звітів на основі даних з таблиць чи запитів.

6. Макроси та VBA:

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

7. Підтримка зовнішніх джерел даних:

Можливість підключення до зовнішніх джерел даних, таких як SQL Server, Excel, SharePoint тощо.

8. Безпека:

Access надає можливості встановлення різного рівня доступу та захисту для даних.

9. Інтеграція з іншими продуктами Microsoft:

Access добре інтегрується з іншими програмами Microsoft Office, що полегшує обмін даними та роботу з ними.

10. Шаблони:

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

# data[].attributes.headline
18.12.2023  Бази даних в інформаційних системах

# data[].attributes.subject
18.12.2023  Бази даних в інформаційних системах

# data[].attributes.body
База даних набуває цінності в складі інформаційної системи (ІС) та є однією з найважливіших її складових.

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

В БД використовуються класичні моделі даних: ієрархічна, мережева, реляційна та об’єктно-орієнтовна. Ієрархічна модель є зручною для роботи з ієрархічно впорядкованою інформацією та громіздка для інформації зі складними логічними зв’язками. Мережева модель — це представлення даних у вигляді довільного графа. Перевагою мережевої та ієрархічної моделей є їх ефективність реалізації по затратам пам’яті. Недоліком мережевої моделі даних є складність схеми БД. Реляційну модель запропонував американський математик Едгар Кодд, який довів, що будьяка сукупність даних предметної галузі може бути подана взаємопов‘язаними між собою математичними відношеннями. Об’єктноорієнтовні БД об’єднують в собі дві моделі даних, реляційну та мережеву, використовуються при створенні великих БД зі складними структурами даних. Модельданих в загальному випадку описує набір базових ознак, які мають бути притаманні СУБД заснованій на цій моделі, тому тип СУБД відповідає типу моделі даних. За характером використання СУБД ділять на персональні, наприклад, VisualFoxPro, Paradox, Clipper, dBase, Access та мережеві (багатокористувацькі), наприклад, Oracle, MS SQL, MySQL, lnformix тощо.

# data[].attributes.headline
15.12.2023 Проєктування баз даних. Поняття сутності, атрибута, ключа, зв’язку. Модель «сутність-зв’язок» предметної області. 

# data[].attributes.subject
15.12.2023 Проєктування баз даних. Поняття сутності, атрибута, ключа, зв’язку. Модель «сутність-зв’язок» предметної області. 

# data[].attributes.body
БД-це впорядкований за певними правилами набір взаємопов’язаних даних. На початку проектування баз даних, як правило, розробляється модель предметної області, для якої створюється ця БД. У ній указуються типи об’єктів, що будуть включені до бази даних, і зв’язки між ними. Для наочності таку модель можна подати у графічному вигляді.

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

Атрибут — це властивість сутності. Зв’язок фактично встановлює взаємодію між сутностями.

Деякі з атрибутів є ключовими – вони дозволяють унікально ідентифікувати об’єкт сутності. Наприклад, у людей можуть повторюватись прізвище, ім’я, по батькові, проте не може повторюватись номер паспорту. І знаючи цей номер, ми можемо точно дізнатись, котрий саме Іваненко Тарас Михайлович відкрив рахунок у банку. Отже людину можна ідентифікувати за номером паспорта.

Передусім потрібно знати, що типів зв’язків є всього три: один до одного, один до багатьох і багато до багатьох.

Один до одного – це клас та класний керівник. В одного класу може бути лише один класний керівник, і вчитель може бути класним керівником лише одного класу. Тому – 1 до 1.

Один до багатьох – у класі вчиться багато учнів, але учень вчиться лише в одному класі. У школі багато класів, але конкретний клас  належить лише до однієї школи.

І багато до багатьох – вчитель викладає у багатьох класах, а у класі викладає багато вчителів. Актор знімається у багатьох фільмах, а у фільмі знімається багато акторів.

Більше ніяких типів зв’язків не буває, всіх їх можна віднести до одного з трьох типів.

# data[].attributes.headline
13.11.2023 Використання бази даних у сучасному житті

# data[].attributes.subject
13.11.2023 Використання бази даних у сучасному житті

# data[].attributes.body
Використання баз даних у сучасному житті є важливим аспектом для зручного та ефективного управління інформацією. Вони застосовуються у бізнесі, науці, медицині та інших галузях для зберігання, оновлення та аналізу великих обсягів даних, сприяючи при цьому прийняттю обґрунтованих рішень та оптимізації процесів.

1. Бізнес: Бази даних використовуються у бізнесі для зберігання клієнтської інформації, відстеження запасів, та управління транзакціями. Наприклад, система управління клієнтами (CRM) дозволяє компаніям зберігати та аналізувати дані про клієнтів для покращення обслуговування.

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

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

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

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

# data[].attributes.headline
27.11.2023 Критерії застосування задач динамічного програмування

# data[].attributes.subject
27.11.2023 Критерії застосування задач динамічного програмування

# data[].attributes.body
Поняття “динамічне програмування” придумав і назвав 1940 року Річард Беллман, а змінив і доповнив його визначення – 1953 року. Беллману довелося багато часу витратити на вибір назви, бо його бос не любив математичні терміни. Тому автор визначення вибрав слово “програмування” замість “планування” і слово “динамічне”, щоб уникнути принизливих і лайливих тлумачень з боку керівника. Ось так було сформовано назву “динамічне програмування”.

Важливо враховувати такі моменти:

1. Для ефективного застосування цього підходу необхідно запам’ятовувати рішення підзадач.

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

Підсумок

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

# data[].attributes.headline
24.11.2023 Загальна задача динамічного програмування

# data[].attributes.subject
24.11.2023 Загальна задача динамічного програмування

# data[].attributes.body
Після розгляду найтиповіших задач динамічного програмування, простіше сформулювати його основні ідеї.

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

Зробимо ще одне зауваження: у будь-якій задачі динамічного програмування «початок» і «кінець» можна поміняти місцями.

Як розпізнати задачу динамічного програмування? Насамперед варто зазначити, що найкращим критерієм «впізнавання» задач динамічного програмування є власний значний досвід у розв'язуванні таких задач. Разом з тим, можна дати й деякі поради. Спочатку треба розглянути питання про можливість розбиття задачі на етапи, що найчастіше міститься вже у формулюванні самої задачі, як, наприклад, дослідження (аналіз) фінансування одного підприємства по роках або кількох окремих підприємств в економічних задачах. Але іноді таке розбиття необхідно робити штучно, як, наприклад, у задачі про прокладання найвигіднішого шляху. Кількість етапів у задачі найчастіше визначається так само в умові задачі. Якщо ж їх доводиться визначати самостійно, то необхідно орієнтуватися на тип змінних, обумовлених у задачі, на критерії визначення кінцевого результату. Не можна забувати, що в разі збільшення кількості етапів значно зростає об'єм розрахунків, що у свою чергу впливає на загальний час виконання алгоритму

# data[].attributes.headline
23.11.2023 Задача про заявки

# data[].attributes.subject
23.11.2023 Задача про заявки

# data[].attributes.body
Задача. Є n заявок на проведення занять в деякій аудиторії. У заявці з номером j вказано два числа sj і fj — початок і кінець заняття (у хвилинах від початку доби). Заявки з номерами j та k сумісні, якщо проміжки [sj , fj ) і [sk , fk ) не перетинаються, тобто справджується одна з нерівностей: fj ≤ sk або fk ≤ sj. Перший рядок файлу input.txt містить запис числа n. Кожний з наступних n рядків містить записи двох чисел: початку й кінця заняття. Потрібно записати у файл output.txt:

у перший рядок максимальну кількість сумісних між собою заявок;

у другий рядок номери відповідних заяв у порядку виконання.

Алгоритм розв'язання задачі про вибір заявок

1. Упорядкувати заявки за зростанням часу закінчення.

2. Надати множині заяв (відповіді) значення порожньої множини.

3. До множини заяв відповіді включити першу (після упорядкування) заявку.

4. Знайти у переліку першу заявку, що починається не раніше закінчення останньої, включеної у відповідь.

5. Включити знайдену заявку до множині заяв (відповіді).

6. Два попередні кроки повторювати доти, поки при пошуку чергової заявки не буде досягнуто кінця переліку заяв.

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

# data[].attributes.body
Нехай є монети номіналом 25, 10, 5 та 1 цент. Якою найменшою кількістю монет можна видати суму S центів? На думку зразу ж інтуїтивно спадає такий алгоритм розв'язування цієї задачі: спочатку візьмемо максимально можливу кількість монет номіналом 25 центів, але так, щоб ця сума не перевищу, вала S. Потім визначимо, скільки монет номіналом 10 центів не перевищить залишку від S. Ту саму операцію проведемо із монетою номіналом 5 центів. Остаточний залишок видамо монетами 1 цент.

Цей алгоритм без сумніву можна назвати жадібним і записати у такому вигляді:

1.     Спочатку визначити максимальне п, для якого 25 * n <= S.

2. Якщо S - 25 п > 0, то визначити максимальне m, для якого 10 m <= S - 25 * n; у протилежному випадку перейти до п. 5.

3.     Якщо S - 25 п - 10 m > 0, то визначити максимальне k, для якого 5 k <= S - 25 п - 10 * n; у протилежному випадку перейти до п. 5.

4.     Якщо S - 25 n - 10 m - 5 k > 0, то суму S - 25 п - 10 ** m - 5 * k видати монетами номіналом 1 цент.

5.     Завершити алгоритм.

# data[].attributes.headline
15.11.2023 Задача про коника-стрибунця

# data[].attributes.subject
15.11.2023 Задача про коника-стрибунця

# data[].attributes.body
Коник-стрибунець довго сидів на поділці 0 числової прямої, так довго, що придумав інноваційну методологію свого переміщення. Отже за кожну ітерацію руху він виконує рівно два стрибка, переміщаючись спочатку на a, а потім на b одиничних відрізків по числовій прямій, причому, якщо число додатне, то він рухається вправо, а якщо від’ємне, то вліво. Тривалість стрибка в секундах дорівнює відповідній кількості одиничних відрізків, на яку переміщується коник.

Наприклад, якщо a = 3, а b = -2, то через 3 сек. він буде на поділці 3, а через 5 сек. від початку руху попаде на відмітку 1. Далі, на 8 секунді переміститься на поділку 4, а на 10 секунді повернеться на 2.

При заданих a та b знайти скільки необхідно часу в секундах, щоб дострибати до поділки x числової прямої або вивести -1, якщо це неможливо.

Вхідні дані

Цілочисельні значення a, b, x — в одному рядку через проміжок. Значення по модулю не перевищують 10^9.

Вихідні дані

Відповідь до задачі.

# data[].attributes.headline
13.11.2023 Жадідні алгоритми

# data[].attributes.subject
13.11.2023 Жадідні алгоритми

# data[].attributes.body
Жадібний алгоритм - інтуїтивний та ефективний спосіб розв'язання задач оптимізації.

Основні характеристики жадібних алгоритмів

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

Відсутність зворотного кроку: Жадібні алгоритми не переглядають або не змінюють вже зроблені вибори.

Швидкість виконання: Жадібні алгоритми зазвичай є ефективними та швидкими у виконанні завдань.

Переваги жадібних алгоритмів

Простота реалізації: Жадібні алгоритми зазвичай мають просту структуру та легко реалізуються.

Швидкість виконання: Жадібні алгоритми можуть бути дуже швидкими у виконанні завдань.

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

Обмеження жадібних алгоритмів

Локальна оптимальність: Жадібні алгоритми намагаються знайти локально оптимальне рішення на кожному кроці, що може не завжди призводити до глобально оптимального рішення.

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

# data[].attributes.headline
10.11.2023   Динамічне програмування

# data[].attributes.subject
10.11.2023   Динамічне програмування

# data[].attributes.body
Динамічне програмування є потужним і ефективним методом вирішення складних обчислювальних задач. Воно базується на розбитті великої задачі на менші незалежні підзадачі, розв’язок яких може бути запам’ятаний і використаний для вирішення більш складних задач.

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

Алгоритм динамічного програмування може бути реалізований за допомогою наступних кроків:

1. Визначення базових випадків: визначення базових випадків, для яких відомий результат безпосередньо.

2. Рекурсивне визначення значень: визначення значень задачі за допомогою рекурсивного вираховування менших підзадач.

3. Запам’ятовування результатів: запам’ятовування результатів підзадач для уникнення повторних обчислень.

4. Побудова оптимального розв’язку: побудова оптимального розв’язку задачі на основі результатів підзадач.

5. Обчислення результату: обчислення та повернення результату задачі.

# data[].attributes.headline
07.11.2023 Алгоритм Флойда-Уоршела

# data[].attributes.subject
07.11.2023 Алгоритм Флойда-Уоршела

# data[].attributes.body
Алгоритм Флойда-Воршелла — алгоритм динамічного програмування для знаходження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа. Розроблений в 1962 році Робертом Флойдом і Стівеном Воршеллом.

Динамічне програмування – це альтернативне вирішення задач методом «в лоб», тобто brute forc'ом або жадний алгоритм. Використовується там, де оптимальне вирішення підзадачі меншого розміру може бути використано для вирішення основної задачі. В загальному виді метод виглядає так:

1. Розбір задачі на під задачі меншого розміру.

2. Знаходження оптимального вирішення під задач рекурсивно.

3. Використання результатів під задач для вирішення основної задачі.

Алгоритм Флойда-Воршелла можна використовувати для вирішення таких задач:

Знаходження найкоротших шляхів у напрямленому графі.

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

Знаходження регулярних виразів, що позначають регулярні граматики, які приймаються скінченним автоматом (Алгоритм Кліні, який є узагальненням алгоритму Флойда-Воршелла).

Невиродженість матриці в методі Гауса

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

Знаходження найдовшого шляху.

Швидкі обрахунки у Pathfinder network.

Розрахунок канонічних форм матриць меж різності (DBM)

# data[].attributes.headline
03.11.2023 Алгоритм Дейкстри

# data[].attributes.subject
03.11.2023 Алгоритм Дейкстри

# data[].attributes.body
Алгоритм Дейкстри.

Задача про найкоротший шлях полягає у знаходженні найкоротшого шляху від заданої початкової вершини до заданої кінцевої вершини. Формулювання задач про знаходження відстаней таке:

1. Для заданої початкової вершини a знайти найкоротші шлахи від a до всіх інших вершин.

2. Знайти найкоротші шляхи між усіма парами вершин.

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

Алгоритм Дейкстри – найефективніший алгоритм на графах відкритий нідерландським вченим Е.Дейкстром у 1959 році. Цей алгоритм знаходить найкоротшу відстань від однієї вершини графу до всіх решти. Алгоритм працює лише для графів у яких ребра не мають від’ємної ваги. Алгоритм широко застосовується в програмуванні і технологіях, наприклад, його використовують протоколи маршрутизації OSPF та IS-IS.

# data[].attributes.headline
02.11.2023 Визначення найкоротшого шляху у графі

# data[].attributes.subject
02.11.2023 Визначення найкоротшого шляху у графі

# data[].attributes.body
В теорії графів, задача про найкоротший шлях полягає в знаходженні такого шляху між двома вершинами (або вузлами) графу, що сума ваг ребер з яких він складається мінімальна. Прикладом може бути знаходження найкоротшого шляху між двома пунктами на дорожній мапі; в цьому випадку, вершинами є пункти, а ребрами — відтинки дороги із вагами, рівними часу, необхідному для подолання цього відрізку.

Формально, маємо зважений граф (це набір вершин V і ребер E з дійсно-значимою функцією ваги f : E → R), і заданим елементом v з V, знайти шлях P з v до v' з V такий, що найменша серед усіх шляхів, що зв'язують v з v' .

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

Задача про найкоротші шляхи з одного входу, тут ми маємо знайти найкоротші шляхи між вхідною вершиною v та всіма іншими вершинами графу.

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

Задача про найкоротші шляхи для всіх пар, тут ми маємо знайти найкоротші шляхи між кожною парою вершин v, v' в графі.

Найважливіші алгоритми для розв'язання цієї задачі:

Алгоритм Дейкстри розв'язує задачі з однією парою, одним входом і одним виходом.

Алгоритм Беллмана-Форда розв'язує задачі з одним входом, якщо ваги ребер можуть бути від'ємні.

Алгоритм пошуку A* розв'язує задачу для однієї пари із використанням евристики в спробі пришвидшити пошук.

Алгоритм Флойда-Воршелла розв'язує задачу для всіх пар.

Алгоритм Джонсона розв'язує задачу для всіх пар, і може бути швидшим за алгоритм Флойда-Воршелла на розріджених графах.

Теорія збурень знаходить (в найгіршому випадку) локально найкоротший шлях.

# data[].attributes.headline
01.11.2023 Реалізація алгоритму пошуку в глибину

# data[].attributes.subject
01.11.2023 Реалізація алгоритму пошуку в глибину

# data[].attributes.body
Обхід графа в глибину — приклад:
Використовуючи розглянутий алгоритм побудувати дерево пошуку в глибину наступного неорієнтованого графа:

ПОБУДОВА ДЕРЕВА ОБХОДУ В ГЛУБИНУ ДЛЯ НЕОРІЄНТОВАНОГО ГРАФА

Отже, починаючи з довільно обраної вершини, наприклад вершини номер «1» рухаємося по першому зустрічному нам ребру (1,2). Так як вершину «2» ми ніколи раніше не відвідували, залишаємося в «2» і проходимо по першому не пройденому ребру, інцидентному «2», а саме (2,3). Тепер у вершині «3» першим не пройденим ребром являється ребро (3,1). Проходимо його і виявляємо, що вершина «1» вже відвідувалася раніше. Тому повертаємося в «3» і помічаємо ребро (3,1) як зворотне (пунктирною лінією). Повернувшись у вершину «3», шукаємо інше не пройдене ребро і йдемо по першому зустрічному з них, скажімо (3,4). Так як «4» — нова вершина, залишаємося в ній і шукаємо не пройдене ребро. В даному випадку таким являється ребро (4,2). Оскільки вершина «2» відвідувалася раніше, позначати ребро (4,2) пунктирною лінією і повертаємося в «4». Через те, що не пройденних ребер, інцидентних «4», не залишилось, повертаємрся у «3».
Побудова дерева обходу в глубину для неорієнтованого графа
У «3» виявляємо не пройдене ребро (3,5) і проходимо його. Оскільки «5» — нова вершина, залишаємося в ній і шукаємо не прйдене інцидентне їй ребро, яким являється ребро (5,1). Так як «1» — вже пройдена вершина, помічаємо ребро (5,1) пунктирною лінією. Тепер вершина «5» повністю переглянута, що свідчить про те, що необхідно повернутись у батьківську по відношенню до неї, тобто у вуршину «3». У «3» немає ребер, що залишилися не пройденими, тому, аналогічним чином, рухаємося назад в «2» і, нарешті, в «1». Всі ребра, інцидентні «1», пройдені, що означає кінець процедури.

# data[].attributes.body
Існує багато алгоритмів на графах, в основі яких лежить систематичний перебір вершин графа, такий що кожна вершина переглядається в точності один раз. Тому важливою задачею є знаходження гарних методів пошуку в графі. Взагалі кажучи, метод «гарний», якщо

Опишемо такий метод пошуку у неорієнтованому графі, який став однією з основних методик проектування графових алгоритмів. Цей метод називається пошуком вглиб.

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

Для того, що здійснювати обхід графа вглиб використовується структура даних стек  (від англ. Stack - пачка, стос : у пачку кладуть зверху і беруть також зверху). Стек - це структура даних з короткою характеристикою типу: останнім прийшов - першим пішов (last-in, first-out   --  LIFO).

Стек можна уявити у вигляді трубки, запаяної з одного кінця. Наочною ілюстрацією такої трубки є магазин автомата чи гвинтівки. Особливістю магазина є те, що патрон у ньому можна покласти лише з одного кінця (через вікно магазину), при цьому патрони, що там були, протискуються вглиб. І вийняти патрон можна лише через вікно, з того ж кінця; при цьому у вікні з'являється новий патрон із глибини магазин. Легко помітити, що виймати патрони можна лише у порядку, зворотному тому, в якому ми їх клали - це і є особливістю магазину - стеку.

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

Найпростішою реалізацію стека є масив (таблиця) зі змінною, що є індексом, який визначає верхівку стека.

# data[].attributes.headline
30.10.2023 Реалізація алгоритму пошуку в ширину

# data[].attributes.subject
30.10.2023 Реалізація алгоритму пошуку в ширину

# data[].attributes.body
Наведемо кроки алгоритму

1. Почати з довільної вершини v. Виконати BFS(v):=1. Включити вершину v у чергу.

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

3. Нехай {x,y} - ребро, у якому номер BFS(у) не визначено. Позначити це ребро потовщеною суцільною лінією, визначити BFS(у) як черговий BFS-номер, включити вершину у чергу й перейти до кроку 2.

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

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

Розглянемо попередні графи і здійснимо для них обхід в ширину. Почнемо знову з 1-ої вершини. 1-а вершина зв'язана з 2, 4 і 12-ою. Їх ще називають «дітьми». Дивимося, які вершини сумісні з «дітьми»: 2-а вершина ні з якою новою (нерозглянутою ще) вершиною не сумісна, 4-а пов'язана з 6-ою і 7-ою, 12-а зв'язана з 10-ою і 11-ою. Всі ці вершини називають «дітьми дітей» або «онуками».  Далі розглядаємо всі нові вершини, які сумісні з «онуками»: 6-а пов'язана з 5-ою,  9-ою і 13-ою;   7-а  - з 3-ою; 10-а та 11-а несумісні ні з якими новими  вершинами. Вершини 5, 9, 13 і 3 є «правнуками», на наступному кроці 5-а вершина сумісна з 8-ою. Обхід графа в ширину можна завершити, бо ми обійшли вже всі вершини.

На малюнку у дужках подана нумерація вершин по черзі, в якій вершини переглядаюся у процесі пошуку в ширину; вершини- «діти» позначені жовтим кольором, вершини - «онуки» - зеленим, «правнуки» - блакитним, і нарешті «праправнуки» - синім.

# data[].attributes.body
Пошук в ширину (обхід в ширину, BFS) - це один з основних алгоритмів на графах.

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

Алгоритм працює за O(n+m), де n - кількість вершин, m - кількість ребер.

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

# data[].attributes.headline
18.10.2023 Рекурсивний пошук

# data[].attributes.subject
18.10.2023 Рекурсивний пошук

# data[].attributes.body
Рекурсивний пошук по першому найкращому

збігу (англ. Recursive Best-First Search — RBFS) — це

простий рекурсивний алгоритм, в якому робляться

спроби імітувати роботу стандартного пошуку за

першим найкращим збігом, але з використанням

тільки лінійного простору. Будь-яка функція (метод) у своєму тілі може викликати

сама себе. Рекурсія – це такий спосіб задавання

функції, при якому результат повернення з функції для

даного значення аргументу визначається на основі

результату повернення з тієї ж функції для

попереднього (меншого або більшого) значення

аргументу.

Якщо функція (метод) викликає сама себе, то такий

виклик називається рекурсивний виклик функції. При

кожному рекурсивному виклику запам’ятовуються

попередні значення внутрішніх локальних змінних та

переданих у функцію параметрів. Щоб наступний крок

рекурсивного виклику відрізнявся від попереднього,

значення як мінімум одного з параметрів функції

повинно бути змінене. Припинення процесу

рекурсивних викликів функції відбувається, коли

змінюваний параметр досягнув деякого кінцевого

значення, наприклад, оброблено останній елемент в

масиві.

# data[].attributes.headline
16.10  Теорія графів

# data[].attributes.subject
16.10  Теорія графів

# data[].attributes.body
Теорія графів – розділ дискретного аналізу, який має широке застосування в багатьох наукових дисциплінах завдяки тому, що поняття і інструментарій цієї теорії виявися дуже зручним для дослідження та інтерпретації різноманітних проблем у великої кількості наук: кібернетиці, технічній і економічній, теорії автоматів, теорії управління, теорії інформації тощо.
Графом називається пара двох множин: вершини V і ребер E, що зв’язують вершини. Термін сукупність означає можливість наявності однакових пар.
Граф називається скінченим, якщо множини його вершин і ребер є скінченими. Множину вершин графа G позначають V(G), а множину ребер – E(G). Кількість вершин графа – n(G), а кількість ребер графа – m(G).
Граф з порожньою множиною ребер називається нуль-графом. Якщо ж множина вершин V – порожня, то порожня і множина E. Такий граф називається порожнім.
Граф, що містить кратні ребра, називається мультиграфом.
Скінченний неорієнтований граф без петель і кратних ребер називається звичайним.
Якщо пари (, )  E вважаються упорядкованими, то граф називається орієнтованим або орграфом. Інакше граф називається неорієнтованим. Ребра орієнтованого графа прийнято називати дугами та зображати направленими відрізками.

# data[].attributes.body
Рядки - це простий тип даних поряд з цілими і дійсними числами. Рядок - це послідовність символів, укладених в одинарні або подвійні лапки.
В Python немає символьного типу, типу даних, об'єктами якого є поодинокі символи. Однак мова дозволяє розглядати рядки як об'єкти, що складаються з підрядків довжиною в один і більше символів. При цьому, на відміну від списків, рядки не прийнято відносити до структур даних.
Нумерація символів у рядку
Кожний символ у рядку має унікальний порядковий номер — індекс. Нумерація символів починається з нуля. Розглянемо приклади роботи з рядками в інтерактивному режимі До конкретного символу в рядку можна звертатися за його індексом, зазначивши індекс у квадратних дужках.
Рядки забезпечують використання всього що може бути представлене у текстовій формі, наприклад:
 інформацію у файлах;
 дані про імена, описи, коментарі в базах даних;
 адреси доменних імен в мережі Internet;
 інформаційні тексти в документах, що підтримують кодування Unicode;
 інше.
У мові Python підтримуються три типи рядків:
 рядки типу str – призначені для представлення тексту в форматі Unicode та інших системах кодування. Цей формат містить символи в кодуванні ASCII та символи в інших кодуваннях;
 рядки типу bytes – призначені для представлення двійкових даних;
 рядки типу bytearray – призначені для представлення двійкових даних з врахуванням змін в типі bytes.
У версії Python 2.6 для представлення тексту Unicode використовується тип unicode.

# data[].attributes.headline
09.10   Тернарний пошук

# data[].attributes.subject
09.10   Тернарний пошук

# data[].attributes.body
Тернарний пошук базується на розділенні даних на три рівні замість двох, як у бінарному пошуку. Цей метод особливо корисний у випадках, коли дані мають структуру, що дозволяє ефективно знаходити шукані елементи.

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

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

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

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

Проте, важливо мати на увазі, що тернарний пошук працює ефективно лише з впорядкованими даними. Якщо дані не впорядковані, цей метод може давати неправильні результати.

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

# data[].attributes.body
Чергою називається структура даних, організована за і принципом «першим прийшов — першим пішов».

Принцип обробки елементів черги схожий на звичайне формування черги в магазині.

і - початок черги, який ще носить назву «голова» черги, та у - кінець черги, що називається «хвостом» черги.

Черга є структурою послідовного доступу.

# data[].attributes.headline
05.09.2023 МАТЕМАТИЧНІ МОДЕЛІ: ОЗНАЧЕННЯ, ХАРАКТЕРИСТИКИ, ЕТАПИ ПОБУДОВИ 

# data[].attributes.subject
05.09.2023 МАТЕМАТИЧНІ МОДЕЛІ: ОЗНАЧЕННЯ, ХАРАКТЕРИСТИКИ, ЕТАПИ ПОБУДОВИ 

# data[].attributes.body
Математична модель – це наближений опис довільного класу явищ зовнішнього світу, поданий за допомогою математичної символіки

Етапи:
- постановка задачі
- побудова математичної моделі;
- дослідження системи на моделі,  прогнозування й управління оригіналом за результатами цих досліджень.

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

# data[].attributes.headline
04.09.2023. Циклічні алгоритми

# data[].attributes.subject
04.09.2023. Циклічні алгоритми

# data[].attributes.body
Алгоритми з повторенням – це алгоритми, у яких кількість одних і тих самих інструкцій виконується неодноразово.

Такі алгоритми називають циклічними.

Приклад

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