паралельні та розподілені обчислення Лабораторна робота № 4 МОЖЛИВОСТІ ВИКОРИСТАННЯ ПАРАЛЕЛЬНИХ АЛГОРИТМІВ. МЕТА РОБОТИ. Дослідити можливості розв’язання різноманітних задач за допомогою паралельних алгоритмів. Навчитися виділяти незалежні гілки обчислень та виконувати їх паралельно. ПОРЯДОК ВИКОНАННЯ РОБОТИ Проаналізувати завдання і виділити в ньому незалежні гілки обчислень(якщо це можливо). Використати метод розбиття задачі на підзадачі та виділення незалежних подій. Реалізувати кожну гілку окремо. Об’єднати всі частини для вирішення поставленої задачі і переконатися у правильності реалізації. Оцінити обчислювальні та часові затрати створеної програми (тобто як зростає час виконання при збільшенні розмірності задачі) ЗМІСТ ЗВІТУ 1.Тема, мета, завдання. 2.Аналіз задачі та опис незалежних подій. 3.Текст програми. 4. Результат виконання програми на обраному наборі вхідних даних. 5.Висновки. ВАРІАНТИ ЗАВДАНЬ № Завдання
1, 15 Графом називається сукупність точок (вузлів), деякі з яких з’єднані між собою направленими ребрами. Граф, що складається з n вузлів можна описати двома матрицями порядку n: матрицею з’єднань та матрицею зв’язків. Елемент матриці з’єднань якщо граф містить ребро направлене від вузла i до вузла j та в іншому випадку. Елемент матриці зв’язків якщо з вузла i можна попасти у вузол j, рухаючись по ребрах і в іншому випадку. Завдання: ввести кількість вузлів деякого графу. Задавши довільним чином матрицю з’єднань(в інтерактивному режимі або випадковим чином), побудувати матрицю зв’язків для цього графу. Передбачити графічне відображення такого графу та числовий вивід обох матриць.
2, 16 Лінія називається унікурсальною, якщо її можна накреслити не відриваючи перо від паперу та не проходячи два рази одне і теж ребро. (Зауважимо, що лінія є унікурсальною лише тоді, коли кількість тих вузлів з яких виходить непарна кількість ребер не більше двох). Лінію, що містить n вузлів можна задати квадратною матрицею з’єднань,(порядку n), в якій елемент якщо вузол i з’єднаний з вузлом j ребром, що не містить інших вузлів. Завдання: ввести кількість вузлів деякої лінії. Задавши довільним чином матрицю з’єднань(в інтерактивному режимі або випадковим чином), визначити чи є така ліні унікурсальною і якщо є, то отримати послідовність номерів вузлів, які будуть пройдені для викреслювання лінії. Передбачити графічне відображення.
3, 17 Ввести п’ять попарно різних цілих чисел a,b,c,d,e. Впорядкувати їх по зростанню, використовуючи не більше 7 порівнянь. Запропонувати узагальнений алгоритм сортування таких послідовностей, зберігаючи пропорцію кількості порівнянь.
4, 18 “Ханойські вежі”. Є три стержні. На першому з них нанизано m дисків зростаючого вниз діаметру. Розташувати диски в тому ж порядку на іншому стержні. Диски можна переміщувати лише по одному, не можна класти більший диск на менший. Завдання: запропонувати алгоритм вирішення поставленої задачі, забезпечивши ввід кількості дисків та відображення їх переміщення в процесі перестановки.
ВАРІАНТИ ЗАВДАНЬ № Завдання
5, 19 Запропонувати та відобразити алгоритм реалізації гри “LIFE”. Гра моделює життя деякої колонії живих клітин, які виживають, розмножуються або гинуть згідно наступних умов. Клітина виживає, якщо вона має двох або трьох сусідів з восьми можливих. Якщо у клітини лише один сусід, або немає жодного, то вона гине (від ізоляції). Якщо клітина має більше трьох сусідів, то вона гине (від перенаселення). В будь-якій порожній позиції, яка має рівно трьох сусідів у наступному поколінні з’являється нова клітина. Гра повинна починатися з довільної кількості клітин, що розташовані в ігровому полі випадковим чином (інтерактивний режим задавання вхідних даних) – так звана початкова популяція. Програма повинна коректно завершувати роботу у таких випадках: а).загинула вся популяція, б) на вимогу користувача.
6, 20 Задати (ввести з клавіатури, або генерувати випадковим чином) цілочисельну матрицю А розмірності n*m, кожен елемент якої дорівнює 0,1,2, або 3. Визначити кількість четвірок . в яких всі елементи різні.
7, 21 Елемент матриці називається сідловою точкою, якщо він є одночасно найменшим у рядку та найбільшим у стовпці. Задати (ввести з клавіатури, або генерувати випадковим чином) дійсну матрицю розміру n*m (вводиться з клавіатури). Визначити чи є в ній сідлові точки та вказати індекси першої та останньої з них.
8, 22 В полі 8*8 кліток зображено кілька прямокутників, кожен з яких складається з кліток, різні прямокутники не перетинаються і не доторкаються один до одного. Задана квадратна матриця порядку 8, в якій елемент рівний нулю, якщо відповідна клітина належить прямокутнику і відмінний від нуля, в іншому випадку. Визначити кількість прямокутників. Початковими даними вважати матрицю елементів, яка повинна вводитися під час виконання програми. Графічно відобразити вхідні дані.
9, 23 Задати натуральні числа . В послідовності вибрати підпослідовність таку, що . Якщо таку підпослідовність вибрати неможливо, то слід вивести відповідне повідомлення. (При вирішенні даної задачі слід використати наступне міркування. Для того, щоб вибрати необхідну підпослідовність для кожного елемента вхідної послідовності слід визначити чи приймається він у шукану підпослідовність. Може виникнути наступна ситуація: відносно членів прийняті які-небудь рішення, після чого виявилось, що, як би ми не розпоряджались іншими членами, нам все одно не вдасться отримати підпослідовність, що задовольняє поставленій умові (наприклад, якщо сума декількох додатних чисел більше m, то неможливо додати до них ще декілька додатних чисел, так, щоб сума стала рівна m). В цьому випадку слід виключити з розгляду всі підпослідовності, перші елементи яких вибрані з , згідно з прийнятими рішеннями.)
ВАРІАНТИ ЗАВДАНЬ № Завдання
10, 24 Задати натуральне число m. Отримати m розташувань 8 ферзів на шаховій дошці при яких жоден з ферзів не загрожує іншим (тобто жодні два ферзі не знаходяться на одній горизонталі, на одній вертикалі, на одній діагоналі). Якщо m більше ніж загальна кількість таких конфігурацій, то слід знайти всі комбінації.
11, 25 Лабіринт задається матрицею з’єднань(див.1) в якій для кожної пари кімнат вказано чи з’єднані вони коридором. Задати (ввести з клавіатури, або генерувати випадковим чином): кількість кімнат лабіринту (n); матрицю з’єднань для них; номери кімнат . Побудувати шлях з кімнати з номером i в кімнату з номером j.
12, 26 Задати (ввести з клавіатури, або генерувати випадковим чином) матрицю з’єднань деякої лінії, що містить 6 вузлів. З’ясувати чи існує замкнений шлях, що складається з декількох відрізків лінії, який проходить через кожні 6 вузлів рівно один раз. Якщо такий шлях існує, то побудувати відповідну послідовність номерів вузлів. Вивести лінію графічно.
13, 27 Є деяка кількість міст, деякі з яких з’єднані дорогами відомої довжини. Вся система доріг описується квадратною матрицею порядку n, в якій елемент рівний будь-якому від’ємному числу, якщо місто i безпосередньо не з’єднано з містом j та рівний довжині дороги у протилежному випадку. Знайти для 1-го міста найкоротші дороги в інші міста. Вхідними даними вважати кількість міст та матрицю доріг.
14, 28 Для попередньої задачі припустити, що кожне місто має пряму дорогу до кожного іншого, і знайти найкоротший шлях, що проходить через всі міста.
29, 30 Задати (ввести з клавіатури, або генерувати випадковим чином) цілочисельну матрицю А розмірності n*m, кожен елемент якої дорівнює 0,1,2, або 3. Визначити кількість четвірок . в яких всі елементи однакові.
