Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
РЕАЛІЗАЦІЯ РЕЖИМУ АВТОМАТИЧНОЇ ПІДТРИМКИ ПОШАГОВОГО РЕЖИМУ ТРИГОНОМЕТРИЧНИХ ЗАДАЧ У МАТЕМАТИЧНІЙ СИСТЕМІ НАВЧАЛЬНОГО ПРИЗНАЧЕННЯ
Інформація про навчальний заклад
ВУЗ:
Херсонський державний університет
Інститут:
Не вказано
Факультет:
РТ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2011
Тип роботи:
Магістерська робота
Предмет:
Інформатика інженер програміст
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ,
МОЛОДІ ТА СПОРТУ УКРАЇНИ
ХЕРСОНСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ
ФАКУЛЬТЕТ ФІЗИКИ, МАТЕМАТИКИ ТА ІНФОРМАТИКИ
ЗАТВЕРДЖУЮ
до захисту в ДЕК
Перший проректор університету
_________професор О.В. Мішуков
“___”___________ 2011 р.
АЛЕКСЕЙЧУК ІВАН ВАЛЕРІЙОВИЧ (______________)
РОЗРОБКА ВИМОГ, АРХІТЕКТУРИ ТА ФУНКЦІОНАЛЬНОСТІ WEB–ОРІЄНТОВАНОГО СЕРЕВИЩА ДЕМОНСТРАЦІЇ АЛГОРИТМІВ
8.080201. ІНФОРМАТИКА
Випускна робота освітньо-кваліфікаційного рівня «Магістр»
ПОГОДЖЕНО
Декан факультету Науковий керівник
__________ доцент Кузьмич В.І. _______ професор Співаковський О.В “___”___________ 2011 р. “___”___________ 2011 р.
Завідувач кафедри інформатики Рецензент
______ професор Співаковський О.В __________ професор Львов М.С.
“___”___________ 2011 р. “___”___________ 2011 р.
Херсон – 2011
ЗМІСТ
Вступ 3
Розділ 1. Задача дослідження ефективності алгоритмів 6
1.1. Поняття алгоритму та його ефективності 6
1.2. Класи складності алгоритмів 10
1.3. Методи оцінки дослідження ефективності алгоритмів 19
Розділ 2. Архітектура програмного забеспечення 26
2.1. Поняття архітектури програмного забезпечення 26
2.2. Поняття гнучкої архітектура 29
2.3. Оцінка успішності кінцевої архітектури продукту 32
Розділ 3. Розробка системи візуалізації алгоритмів та проведення обчислювального експерименту в ПМК «Відеоінтерпретатор 3.0» 37
3.1. Постановка задачі та вимоги до продукту 37
3.2. Застосовані архітектурні рішення 40
3.3. Аналіз та вибір технологій розробки 50
3.4. Інтеграція з порталом «ВебОАП» 54
Список використаних джерел 60
Додаток А. Описання основних структур імперативної мови програмування 67
ВСТУП
Тенденції останніх десятиліть демонструють невпинну інформатизацію освітнього процесу. Інструменти сучасної освіти докорінно відрізняються від інструментів освіти минулих років, все більшу популярність отримують інтерактивні середовища багатоцільового призначення. Тобто такі, що є корисними як при проведенні аудиторних занять, практикумів, так і при самостійному використанні.
Можна навести багато прикладів таких середовищ, серед яких слід відмітити такі інноваційні продукти, створені в лабораторіях та відділах Херсонського державного університету як «Терм», «Віртуальна біологія», «Алгебра 7», «Алгебра 8», «Світ лінійної алгебри». Всі ці продукти об’єднує мета подавання складного шкільного та академічного матеріалу наочним та зрозумілим шляхом. Також важливою рисою таких продуктів є інтеграція їх з іншими джерелами інформації: підручником, посібником або методичними матеріалами по темі. Таким чином школяру чи студенту надається в край важлива змога переходити від вивчення теоретичного матеріалу до практичної чи дослідницької роботи.
Одним з найцікавіших, з точки зору організації навчального процесу, прикладів системи, що вдало поєднує в собі навчальні, методичні, контролюючі та дослідницькі інструменти, є портал Web-ОАП «Основи алгоритмізації та програмування». До складу продукту входить навчальний посібник, тести для кожної викладеної теми, збірка задач, середовище демонстрації алгоритмів та проведення обчислювального експерименту.
На останній інструмент слід звернути особливу увагу, оскільки він надає унікальні в своєму роді можливості. Середовище демонстрації (або «Відеоінтерпретатор») створює для студентів можливість дивитися виконання алгоритму в спрощеній для засвоєння формі. Але навіть більший інтерес викликає модуль обчислювального експерименту, що дозволяє досліджувати питання ефективності алгоритмів. Слід зауважити, що середовище має досить довгу історію, що налічує більше ніж два десятиліття, останню версію було створено у 2007 році.
Актуальність створення нової версії ПМК «Відеоінтерпретатор» витікає з застарілості поточної, що було створено за допомогою технології ActiveX та MFC, також ці технології накладають обмеження щодо платформи використання, якою на даний час виступає лише ОС Windows. Це надзвичайно звужує коло користувачів, відсіюючи тих, що надають перевагу Linux, Mac OS, та іншим.
Слід зауважити, що було проаналізовано досить багато шляхів подальшого розвитку продукту – від більш лояльного, що базувався можливості корегувати поточну версію до кардинального, що припускав створення нової. Вибір було зупинено на останньому варіанті, оскільки в архітектурі та коді продукту були виявлені численні недоліки і це могло сказатися на кінцевому релізі.
Метою даної роботи є проектування архітектури нової версії ПМК «Відеоінтерпретатор», що характеризується гнучкістю та надає можливість подальшого розвитку продукту.
Під гнучкістю, в даному контексті, треба розуміти змогу додавання нових компонентів та заміни існуючих.
Об’єктом є гнучка архітектура складних програмних систем, у тому числі педагогічної спрямованості.
Предметом дослідження є архітектурні та технологічні рішення, що створюють спроможність подальшого розвитку складної системи.
Завданнями в рамках реалізації проекту виступають:
Аналіз поточної версії ПМК «Відеоінтерпретатор» та побудова його онтології.
Дослідження архітектурних та технологічних рішень, що диктує сьогодення.
Розробка тонкого ядра системи, що включає базові інтерфейси описання та взаємодії компонентів.
Створення кросплатформового додатку, що покриває таку множину платформ: Windows, Linux, Mac OS.
Гіпотеза дослідження стверджує, що створення нової архітектури та використання актуальних технологій створює можливість нормального розвитку середовища.
Теоретична цінність роботи проглядається в дослідженні архітектурних прийомів, що дозволяють створювати складні системи, а аналіз актуальних технології, що інтегруються з указаними архітектурними рішеннями.
Практична цінність роботи полягає у створенні нової версії дослідницького середовища Відеоінтерпретатор.
Для проведення даної роботи застосовувалися методи аналізу, синтезу, збору інформації, обробки і аналізу даних, методи програмної інженерії та тестування.
Структура роботи складається з вступу, трьох розділів, висновку і списку літератури.
Апробація. По тематиці роботи була зроблена доповідь під назвою «Середовище демонстрації як інструментальний засіб для організації обчислювального експерименту» на VIІ Міжнародній науково-практичній конференції ICTERI 2011 «ІКТ в освіті, дослідженнях та індустріальних додатках: ІНТЕГРАЦІЯ, ГАРМОНІЗАЦІЯ ТА ТРАНСФЕР ЗНАНЬ», де було отримано схвальні відгуки та пропозиції.
РОЗДІЛ 1 ЗАДАЧА ДОСЛІДЖЕННЯ ЕФЕКТИВНОСТІ АЛГОРИТМІВ
Поняття алгоритму та його ефективності
Алгоритм (латин. Algorithmi, від імені перського математика IX ст. аль-Хорезмі) – послідовність,система, набір систематизованих правил виконання обчислювального процесу, що обов'язково приводить до розв’язання певного класу задач після скінченного числа операцій.
Поняття алгоритму є чистою абстракцією, оскільки не визначає ні об’єкт, що має його виконувати, ні висовує ніяких обмежень щодо його кроків. Більш того, навіть не має чіткого визначення, яких існує цілий ряд:
Алгоритм – це кінцевий набір правил, який визначає послідовність операцій для вирішення конкретної множини завдань і володіє п’ятьма важливими рисами: кінцівку, визначеність, введення, висновок, ефективність.
Алгоритм – це будь-яка система обчислень, що виконуються за строго визначеними правилами, яка після деякого числа кроків призводить до вирішення поставленого завдання.
Алгоритм – це точне розпорядження, що визначає обчислювальний процес, що йде від варійованих вихідних даних до шуканого результату.
Алгоритм – точне розпорядження про виконання в певному порядку деякої системи операцій, що ведуть до розв’язання всіх задач даного типу
Алгоритм – суворо детермінована послідовність дій, що описує процес перетворення об’єкта з початкового стану в кінцеве, записана за допомогою зрозумілих виконавцю команд
Алгоритм – це послідовність дій, спрямованих на отримання певного результату за кінцеве число кроків.
Алгоритм – однозначно, доступно і коротко описана послідовність процедур для відтворення процесу з обумовленим завданням алгоритму результатом при заданих початкових умовах. Універсальність (або спеціалізація) алгоритму визначається придатністю і надійністю даного алгоритму для вирішення нестандартних завдань.
Алгоритм – це зрозумілі й точні приписи виконавцю здійснити кінцеве число кроків, спрямованих на вирішення поставленого завдання.
Алгоритм – це деякий кінцевий набір розрахованих на певного виконавця операцій у результаті виконання яких через певне число кроків може бути досягнута поставлена мета чи вирішена задача певного типу.
Алгоритм – це послідовність дій, або приводить до розв’язання задачі, або пояснюючий чому це рішення отримати не можна.
Алгоритм – це точна, однозначна, кінцева послідовність дій, яку має виконати користувач для досягнення конкретної мети або для вирішення конкретної задачі або групи завдань.
Алгоритм – це точне розпорядження, яке задає обчислювальний (алгоритмічний) процес, що починається з довільного початкового даного і спрямований на отримання повністю визначеним цим вихідним даним результату.
Алгоритм – це опис послідовності дій, яке веде до кінцевого результату.
Будь-який алгоритм має відповідати таким властивостям як дискретність, результативність, доступність, масовість, скінченність, однозначність. Однією з найочевидніших та у той час найважливіший властивостей алгоритму є його функціональність.
результативність – алгоритм повинен давати деякий результат. скінченність – робота алгоритму повинна закінчуватися за кінцеве число кроків;
визначеність – всі складові алгоритму повинні допускати однозначне трактування і бути зрозумілими виконавцю (наприклад, комп’ютеру). Тобто виконавець повинен володіти засобами виконання всіх інструкцій;
масовість – алгоритм повинен давати рішення для цілої групи завдань, що відрізняються вихідними даними;
детермінованість – багаторазове застосування щодо одного й того ж набору вихідних даних повинно давати однаковий результат;
ефективність – всі кроки алгоритму повинні бути такими, щоб виконавець міг виконати їх за кінцевий час, що лежить в деяких розумних межах. І якщо мова йде про обчислювальну машину, то – в межах розумних обмежень щодо використовуваної пам’яті;
Саме з ефективністю алгоритму інтуїтивно пов’язане поняття «вартості», що розуміється як кількісна оцінка необхідних для його реалізації ресурсів. Більш точний сенс поняттю вартості дозволяє надати поняття складності алгоритмів. Воно визначає вартість у часі і в просторі, дозволяє оцінити час виконання та обсяг необхідної пам’яті.
В міру накопичення досвіду роботи в деякій галузі знань, кожен спеціаліст починає інтуїтивно відчувати, що та чи інша задача більш чи менш важка, ніж інша. Зрозуміло, такого суб’єктивного, не вираженого кількісною мірою поняття як «легше» або «важче» на практиці не достатньо. Таким чином постає задача визначення можливості оцінки складності та кількісних показників складності.
Складність алгоритму оцінюють за його динамічним характеристикам, а не статичними: наприклад, велика програма може виконуватися дуже швидко, а коротка – дуже довго. На практиці складність алгоритму зазвичай пов’язують з основним його параметром, що істотно впливає на кількість виконуваних дій. Як правило, це розмір масиву даних, що обробляються (розмір задачі).
Природно вважати критерієм якості алгоритму рішення найгіршого з можливих випадків його застосування.
Таким чином, складністю алгоритму називається виражена у вигляді функції від розмірності вхідних даних верхня межа кількості операцій, необхідних для реалізації алгоритму.
Складність завдання – це складність найкращого алгоритму, відомого для її вирішення. Тому вона залежить від рівня розвитку методів рішення. Тут виникають три принципових питання:
До якої межі можна покращувати даний алгоритм?
Чи веде облік складності до появи деякої класифікації завдань?
Чи існують методи переходу з одного класу до іншого, тобто від більш складних завдань до більш простим?
Метою аналізу складності алгоритмів є знаходження оптимального алгоритму для вирішення даної задачі. В якості критерію оптимальності алгоритму вибирається складність алгоритму, що розуміється як кількість елементарних операцій, які необхідно виконати для вирішення задачі за допомогою даного алгоритму. Функцією складності називається відношення, що зв’язують вхідні дані алгоритму з кількістю елементарних операцій.
Складність алгоритмів по-різному залежить від вхідних даних. Для деяких алгоритмів складність залежить тільки від обсягу даних, для інших алгоритмів – від значень даних, в деяких випадках порядок надходження даних може впливати на складність. Складність багатьох алгоритмів може в тій чи іншій мірі залежати від всіх перерахованих вище факторів.
Одним із спрощених видів аналізу, що використовуються на практиці, є асимптотичний аналіз алгоритмів. Метою асимптотичного аналізу є порівняння витрат часу та інших ресурсів різними алгоритмами, призначеними для вирішення однієї і тієї ж задачі, при великих обсягах вхідних даних. Використовувана в асимптотичному аналізі оцінка функції складності, що називається складністю алгоритму, дозволяє визначити, як швидко зростає складність алгоритму з збільшенням обсягу даних. У асимптотичному аналізі алгоритмів використовуються позначення, прийняті в математичному асимптотичному аналізі.
Доцільно ввести поняття класу алгоритму, що витікає з означення функціональності. Має сенс порівняння характеристик ефективності алгоритмів, що належать до одного класу.
Класи складності алгоритмів
Нехай – множина класів алгоритмів, та – метрики за якими оцінюється ефективність алгоритму, тоді для та має сенс запис де – оцінки ефективності алгоритмів зам метрикою .
Під терміном ефективності алгоритму можна розуміти інтегральну характеристику його ефективності за часом виконання, дане значення можна представити у вигляді часового проміжку, але такий показник не буде релевантним, оскільки один і той самий алгоритм на різних, або навіть одній ЕОМ, може виконуватися різну кількість часу, тому частіше час виконання розуміють як кількості виконаних операцій, використаних апаратних ресурсів тощо.
Важливою умовою отримання адекватної оцінки ефективності алгоритму вважають виконання алгоритмів на ідентичних вхідних даних.
Аналізу ефективності алгоритмів присвячено цілий розділ інформатики – теорія складності обчислень, що вивчає вартість роботи, необхідної для вирішення обчислювальної проблеми. Вартість вирішення обчислювальної проблеми зазвичай вимірюється абстрактними поняттями часу і простору, що також називають обчислювальними ресурсами. Час визначається кількістю елементарних кроків, необхідних для вирішення проблеми, тоді як простір визначається обсягом пам’яті або місця на носії даних. Таким чином, у цій області робиться спроба відповісти на центральне питання розробки алгоритмів: «як зміниться час виконання й обсяг використаної пам’яті в залежності від розміру входу і виходу?». Під розміром входу потрібно розуміти довжину опису даних задачі в бітах (наприклад, в задачі комівояжера довжина входу пропорційна кількості міст і доріг між ними), а під розміром виходу – довжина опису рішення задачі (оптимального маршруту у задачі комівояжера).
Теорія складності обчислень виникла із потреби порівнювати швидкодію алгоритмів, чітко описувати їх поведінку (час виконання й обсяг необхідної пам’яті) в залежності від розміру входу і виходу. Кількість елементарних операцій, витрачених алгоритмом для вирішення конкретного екземпляра задачі, залежить не тільки від розміру вхідних даних, але і від самих даних. Наприклад, кількість операцій алгоритму сортування вставками значно менше у разі, якщо вхідні дані вже відсортовані. Щоб уникнути подібних труднощів, розглядають поняття часової складності алгоритму в гіршому випадку.
Часова складність алгоритму (в гіршому випадку) – це функція розміру вхідних і вихідних даних, що дорівнює максимальній кількості елементарних операцій, що виконуються алгоритмом для вирішення екземпляру задачі зазначеного розміру. У задачах, де розмір виходу не перевершує або пропорційний розміру входу, можна розглядати часову складність як функцію розміру тільки вхідних даних.
Аналогічно поняттю часової складності в гіршому випадку визначається поняття часової складності алгоритму в найкращому випадку. Також розглядають поняття середнього часу роботи алгоритму, тобто математичне очікування часу роботи алгоритму. Іноді говорять просто: «часова складність алгоритму» або «час роботи алгоритму», маючи на увазі часову складність алгоритму в гіршому, найкращому або середньому випадку (в залежності від контексту).
За аналогією з часовою складністю, визначають просторову складність алгоритму, тільки тут говорять не про кількість елементарних операцій, а про обсяг використовуваної пам’яті.
Незважаючи на те, що функція часової складності алгоритму в деяких випадках може бути визначена точно, в більшості випадків шукати точне її значення безглуздо. Справа в тому, що по-перше, точне значення часової складності залежить від визначення елементарних операцій (наприклад, складність можна вимірювати у кількості арифметичних операцій, бітових операцій чи операцій на машині Тьюрінга), а по-друге, при збільшенні розміру вхідних даних внесок постійних множників і доданків нижчих порядків, що фігурують у виразі для точного часу роботи, стає вкрай незначним.
Розгляд вхідних даних великого розміру і оцінка порядку зростання часу роботи алгоритму приводять до поняття асимптотичної складності алгоритму. При цьому алгоритм з меншою асимптотичної складністю є більш ефективним для всіх вхідних даних, за винятком лише, можливо, даних малого розміру. Для запису асимптотичної складності алгоритмів використовуються асимптотичні позначення, що подано в Табл. 1.1.
Табл. 1.1. Асимптотичні позначення
Позначення
Пояснення критерію класифікації
f обмежена зверху функцією g (з точністю до постійного множника) асимптотично
f обмежена знизу функцією g (з точністю до постійного множника) асимптотично
f обмежена знизу і зверху функцією g асимптотично
g домінує над f асимптотично
(продовження Табл.1.1)
Позначення
Пояснення критерію класифікації
f домінує над g асимптотично
f еквівалентна g асимптотично
В технічній літератур та в академічному процесі більш вживаними є так звані позначення через «О» Детальний опис подано в таблиці 1.2. Графічне зображення залежностей продемонстровано на Рис. 1.3.
Табл. 1.2. Поширені складності алгоритмів.
Позначення
Пояснення та приклад
Сталий час роботи не залежно від розміру задачі.
Приклад: Очікуваний час пошуку в хеші.
Дуже повільне зростання необхідного часу.
Приклад: Очікуваний час роботи інтерполюючого пошуку n елементів.
Логарифмічне зростання – подвоєння розміру задачі збільшує час роботи на сталу величину.
Приклад: Обчислення ; двійковий пошук в масиві з n елементів.
Лінійне зростання – подвоєння розміру задачі подвоїть і необхідний час.
Приклад: Додавання/віднімання чисел з n цифр; лінійний пошук в масиві з n елементів.
Лінеаритмічне зростання – подвоєння розміру задачі збільшить необхідний час трохи більше ніж вдвічі.
Приклад: Сортування злиттям або купою n елементів; нижня границя сортування порівнянням n елементів
(продовження Табл.1.2)
Позначення
Пояснення та приклад
Квадратичне зростання – подвоєння розміру задачі вчетверо збільшує необхідний час.
Приклад: Елементарні алгоритми сортування.
Кубічне зростання – подвоєння розміру задачі збільшує необхідний час у вісім разів.
Приклад: Звичайне множення матриць.
Експоненціальне зростання – збільшення розміру задачі на 1 призводить до c-кратного збільшення необхідного часу; подвоєння розміру задачі підносить необхідний час у квадрат
Приклад: Деякі задачі комівояжера, алгоритми пошуку повним перебором
Рис. 1.3. Графічне відображення алгоритмів різної складності
Клас складності – це множина задач розпізнавання, для вирішення яких існують алгоритми, схожі за обчислювальною складністю.
Всі класи складності знаходяться в ієрархічному відношенні: одні містять у собі інші. Однак про більшість включень невідомо, чи є вони суворими. Одна з найбільш відомих відкритих проблем у цій галузі – рівність класів P і NP. Якщо це припущення вірне (у чому більшість вчених сумнівається), то представлена на рис. 1.4 ієрархія класів сильно згорнеться. На даний момент найбільш поширеною є гіпотеза про невирожденості ієрархії (тобто всі класи різні). Крім того, відомо, що EXPSPACE не дорівнює класу PSPACE.
Клас NP (від англ. non-deterministic polynomial) – множина задач розпізнавання, рішення яких можливо, за наявності деяких додаткових відомостей (так званого сертифіката рішення), «швидко» (за час, що не перевершує полінома від розміру даних) перевірити на машині Тьюринга.
Еквівалентно клас NP можна визначити як містить завдання, які можна «швидко» вирішити на недетермінованої машині Тьюринга.
Різниця між поліноміальними і експоненціальними алгоритмами сходить до фон Нейманом.
Клас складності NP визначається для множини мов, тобто множин слів над кінцевим алфавітом . Мова називається належить класу NP, якщо існують двомісний предикат з класу P (тобто обчислюваною за поліноміальний час) і константа такі, що для будь-якого слова умова рівносильне умові . Слово називається сертифікатом приналежності мови . Таким чином, якщо у нас є слово, що належить мові, і ще одне слово-свідок обмеженої довжини (яке буває важко знайти), то ми швидко зможемо переконатися у тому, що дійсно належить .
Рис. 1.4. Ієрархія класів складності
Еквівалентна визначення можна отримати, використовуючи поняття недетермінованої машини Тьюрінга (тобто такої машини Тьюрінга, у програми якої можуть існувати різні рядки з однаковою лівою частиною). Якщо машина зустріла «розвилку», тобто неоднозначність у програмі, то далі можливі різні варіанти обчислення. Предикат, який являє дана недетермінованих машина Тьюрінга, вважається рівним одиниці, якщо існує хоч один варіант обчислення, повертає 1, і нулю, якщо всі варіанти повертають 0. Якщо довжина обчислення, що дає 1, не перевершує деякого многочлена від довжини , то предикат називається належить класу NP. Якщо у мови існує розпізнає його предикат з класу NP, то мова називається належить класу NP. Це визначення еквівалентно наведеним вище: як свідка можна взяти номери потрібних гілок при розвилках в обчисленні. Так як для належить мови довжина всього шляху обчислення не перевершує многочлена від довжини , то і довжина свідка також буде обмежена многочленом від .
Всяку завдання про приналежність слова мови , що лежить в класі NP, можна вирішити за експоненційний час перебором всіх можливих сертифікатів довжини менше .
Клас (від англ. polynomial) називають множину здач, для яких існують «швидкі» алгоритми рішення (час роботи яких поліноміальної залежить від розміру вхідних даних). Клас включений у більш широкі класи складності алгоритмів.
Алгоритм ототожнюється з детермінованою машиною Тьюринга, яка обчислює відповідь з даного на вхідну стрічку слову з вхідного алфавіту . Часом роботи алгоритму при фіксованому вхідному слові називається кількість робочих тактів машини Тюринга від початку до зупинки машини. Складністю функції , що обчислюється деякою машиною Тьюрінга, називається функція , що залежить від довжини вхідного слова і рівна максимуму часу роботи машини по всіх вхідним словами фіксованої довжини :
Якщо для функції f існує машина Тьюрінга така, що для деякого числа і достатньо великих n, то кажуть, що вона належить класу , або поліноміальна за часом.
Згідно з тезою Черча - Тьюрінга, будь мислимий алгоритм можна реалізувати на машині Тьюрінга. Для будь-якої мови програмування можна визначити клас подібним чином (замінивши у визначенні машину Тьюрінга на реалізацію мови програмування). Якщо компілятор мови, на якому реалізовано алгоритм, уповільнює виконання алгоритму поліноміальної (тобто час виконання алгоритму на машині Тьюрінга менше деякого многочлена від часу виконання його на мові програмування), то визначення класів для цієї мови і для машини Тьюринга збігаються. Код на асемблері допускає перетворення в машину Тьюрінга з невеликим поліноміальним уповільненням, а оскільки всі існуючі мови допускають компіляцію в асемблер (знову ж таки, з поліноміальним уповільненням), то визначення класу для машин Тьюринга і для будь-якого існуючого мови програмування збігаються.
У теорії алгоритмів питання про рівність класів складності P і NP є однією з центральних відкритих проблем вже більше трьох десятиліть. Якщо на нього буде дана ствердна відповідь, це буде означати, що теоретично можливо вирішувати багато складних завдання істотно швидше, ніж зараз.
З визначення класів P і NP відразу випливає наслідок: . Проте до цих пір нічого не відомо про суворість цього включення, тобто чи існує завдання, що лежить в NP, але не лежить в P (Рис. 1.5). Якщо такого завдання не існує, то всі завдання, що належать класу NP, можна буде вирішувати за поліноміальний час, що обіцяє величезну вигоду з обчислювальної точки зору. Зараз найскладніші завдання з класу NP (так звані NP-повні задачі) можна вирішити за експоненційний час, що майже завжди неприйнятно.
Рис.1.5. Відношення класів складності NP та P.
В даний час більшість математиків вважають, що ці класи не рівні. Згідно з опитуванням, проведеним у 2002 році серед 100 вчених, [66, c.34-47]
61 людина вважає, що відповідь - «не рівні»;
9 - «рівні»;
22 не змогли відповісти;
8 вважають, що гіпотеза не виводиться з поточної системи аксіом і, таким чином, не може бути доведена або спростована.
З вищезазначеного видно, що проблема дослідження відношення класів P та NP є актуальною в науковому середовищі і потребує глибшого аналізу.
Методи оцінки дослідження ефективності алгоритмів
Існує три основних способи дослідження ефективності алгоритму
аналітичний
практичний
комбінований
Суть аналітичного методу полягає в аналізі ефективності арифметичних обчислень та оцінці використання основних управляючих структур алгоритму – оператора розгалуження, оператора повторення, виклику підпрограми (для рекурсивних алгоритмів). З першими все більш-менш зрозуміло – треба уникати повторного обчислення значень, що часто використаються, спрощувати формули, мати на увазі, що операції ділення – найдовша операція на більшості процесорів, користуватися операціями зсуву та інше.
З другими ситуація значно цікавіша та складніша, оскільки саме за допомогою цих структур, підчас зловживаючи, програмісти складають програми. Отже яким чином можна наприклад проаналізувати ефективність наступного коду, представленого у лістингу 1.6.
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
for ( j = 0; j < N; j++ ) {
// Виконання обчислень
}
Лістинг 1.6 Алгоритм з кубічною збіжністю
Ми маємо три вкладені один в інший цикли, тобто кожний з них буде виконуватися N разів, тобто загалом N * N * N = N3 разів. У такому випадку кажуть, до алгоритм має кубічну збіжність і записують
C * N3 або O(N3),
де C – деякий коефіцієнт, при множенні на котрий N ми отримаємо кубічну складність
Буде доречним сказати, що алгоритми з такою складність не можна вважати ефективними для більшості класів задач, де навіть квадратична збіжність вважається поганим показником, хоча існують специфічні класи алгоритмів зі складністю навіть вищу за кубічну.
Наприклад, час роботи алгоритму, що виконує тільки операції читання і занесення n даних в оперативній пам’яті, визначається формулою де – час читання-запису, – сумарний час допоміжних операцій. Тут має місце лінійна залежність від , і складність алгоритму тому називається лінійною. Коефіцієнти і невідомі, але залежать від ЕОМ, транслятора і т.д. Тому цікавим є характер залежності від основного параметра, говорять про теоретичну складності, враховуючи ту функцію від основного параметра, що визначає складність. У даному випадку це
Сортування за допомогою прямого обміну («бульбашкове сортування») елементів масиву представляє собою наступний процес: визначається найменший елемент у всьому масиві і проводиться його обмін з першим елементом; потім визначається найменший елемент в частині масиву і проводиться його обмін з другим елементом і т . д. Значить, все виконується порівнянь при пошуку першого елемента, порівнянь при пошуку другого елемента і т.д.
Це поліном другого ступеня (кажуть, що складність алгоритму поліноміальна, а в даному випадку - квадратична). Для великих n можна вважати, що складність .
Якщо складність алгоритму оцінюється по вже написаної програмі, то замість числа порівнянь обчислюється число повторень внутрішніх процедур
for k: = 1 to n–1 do
begin
min: = A [k];
for i: = k +1 to n do
if min> A [i] then
begin
min: = A [i];
A [i]: = A [k];
A [k]: = min;
end;
end;
Лістинг 1.7. Сортування обмінами
Зовнішній цикл виконується раз. Внутрішній цикл при кожному повторенні зовнішнього спрацьовує в середньому (при рівномірному розкиді величин) разів. Помноживши, отримуємо ту ж саму величину.
При великих значеннях n за асимптотичну оцінку можна взяти, тобто складність має порядок .
Оцінками часу роботи алгоритму є максимальне, мінімальне та середнє час його виконання. Вони можуть збігатися або не збігатися. У наведеній процедурі сортування вони збігаються.
Максимальне число кроків – циклів очевидно визначається ситуацією виду . Тоді, якщо за параметр n взяти значення , то максимальна оцінка складності – порядку . Але мінімальна оцінка складності при відповідає ситуації . Результат в цьому випадку досягається за один крок, а складність - O (1) не залежить від n.
Наступний метод – практичний, більш наочний та полягає в замірюванні часу виконання певного алгоритму реалізованого на певній мові програмування.
int main() {
cout<<”Buble sort”<<endl;
inputArray(array);
startTime = timeGetTime();
bubleSort(array);
cout<<timeGetTime()–startTime<<” ms”<<endl;
cout<<”Insert sort”<<endl;
inputArray(array);
startTime = timeGetTime();
insertSort(array);
cout<<timeGetTime()–startTime<<” ms”<<endl;
cout<<”Insert sort”<<endl;
inputArray(array);
startTime = timeGetTime();
insertSort(array);
cout<<timeGetTime()–startTime<<” ms”<<endl;
}
Лістинг 1.8. Приклад практичного обчислення ефективності алгоритму
Як можна зрозуміти за Лістингом 1.8., все що потрібно зробити для дослідження ефективності алгоритму – запам’ятати час коли почалося виконання алгоритму, та відняти це значення від часу коли алгоритм було завершено. Звісно ця оцінка буде різнитися раз від разу і одиничні заміри не будуть давати репрезентативної оцінки та в цілому метод можна вважати статистично вірним.
Рис.1.9. Практичний обчислювальний експеримент в процесі
На Рис. 1.9. представлено результати обчислювального експерименту для трьох видів сортувань – обмінами, вставками та швидке сортування Хоара. Обчислювальний експеримент було проведено за двома метриками: кількістю порівнянь, та затраченого часу. В даній реалізації кожна ітерація обчислювального експерименту представляє запуск тестового додатку, тому кількість таких запусків дорівнює кількості точок на осі абсцис. В більш складних системах експеримент може проводитись на десятках алгоритмів за десятками показників. Такі системи можуть включати інструменти побудови графічних залежностей та мають можливість експорту в розповсюджені формати файлів.
При проведенні оцінки ефективності алгоритмів таким шляхом часто практикується заповнення матриць, де занотовується кількість елементів та затрачений час на виконання. По цим таблицям потім будують графік (Рис. 1.10.), використовуючи один з методів математичної статистики, наприклад, метод найменших квадратів.
Слід зауважити, що такий метод є рутинним та вимагає від студента не абиякої уваги, старанності та ретельності, в інакшому випадку отримані результати можуть не відповідати дійсності.
Рис.1.10. Побудова таблиць за даними експерименту
Останній спосіб проведення – комбінований, поєднує елементи аналітичного та практичного способу. Такий спосіб найбільш прийнятний в умовах навчального процесу, оскільки він, на відміну від першого, наштовхує студента будувати гіпотези відносно збіжності алгоритму, а не запам’ятати конкретну формулу до конкретного алгоритму. Та на відміну від другого, все ж таки, має теоретичне підґрунтя. Саме на цьому шляху проведення обчислювального експерименту робиться акцент в рамках роботи зі середовищем «Основи алгоритмізації та програмування».
РОЗДІЛ 2. АРХІТЕКТУРА ПРОГРАМНОГО ЗАБЕСПЕЧЕННЯ
Поняття архітектури програмного забезпечення
Архітектура програмного забезпечення (англ. software architecture) – це структура програми чи обчислювальної системи, що включає програмні компоненти, зовнішні властивості цих компонентів, а також відносини між ними. Цей термін також може бути застосованим до документування архітектури програмного забезпечення. Документування ПЗ спрощує процес комунікації між зацікавленими особами (англ. stakeholders), дозволяє зафіксувати прийняті на ранніх етапах проектування рішення щодо високорівневим дизайном системи та дозволяє повторно використовувати компоненти цього дизайну та шаблони в інших проектах.
Галузь комп’ютерних наук з моменту свого формування стикнулася з проблемами, зв’язаними зі складністю програмних систем. Раніше проблеми складності вирішувались розробниками шляхом правильного вибору структур даних, розробки алгоритмів та застосування концепції розмежування повноважень. Хоча термін «архітектура програмного забезпечення» є відносно новим для індустрії ПЗ, фундаментальні принципи цієї галузі застосовувалися піонерами розробки ПЗ починаючи з середини 1980-х років. Перші спроби усвідомити та пояснити програмну архітектуру системи були вкрай неточними та мали вади з організованістю, часто представляючи собою діаграми блоків поєднані лініями. В 1990-і роки було зроблено спроба визначити та систематизувати основні аспекти даної дисципліни. В цей час було розроблено початковий набор шаблонів проектування, стилів дизайну, передового досвіду (best-practices), мов описання та формальна логіка.
Фундаментальною ідеєю дисципліни програмної архітектури є ідея зниження складності системи шляхом абстракції та розмежування повноважень. На сьогоднішній день немає згоди у відношенні чіткого визначення терміну «архітектура програмного забезпечення».
Початок архітектурі ПЗ як концепції було покладено в науково-дослідницький роботі Едсгере Дейкстри у 1968 році та Девіда Парнаса на початку 1970-х. Ці вчені підкреслили, що структура системи ПЗ має важливе значення та, що побудова правильної структури є критично важливим етапом створення програмного продукту.
В розвитку архітектури програмного забезпечення як дисципліни грають важливу роль науково-дослідні установи. Мери Шоу та Девид Герлан з університету Carnegie Mellon написали книгу під назвою "Архітектура програмного забезпечення: перспективи нової дисципліни у 1996 році", в якій висунули концепції архітектури програмного забезпечення, такі як компоненти, з’єднувачі, стилі та інші. У каліфорнійському університеті інституті Ирвайна по дослідженню ПЗ в першу чергу досліджуються архітектурні стилі, мови описання архітектури та динамічні архітектури.
Першим стандартом програмної архітектури є стандарт IEEE 1471: ANSI / IEEE 1471–2000: Рекомендації по описанню переважно программних систем. Його було прийнято у 2007 році, під назвою ISO / IEC 42010:2007[65].
Архітектура ПЗ є реалізацією нефункціональных вимог до системи, у той час проектування ПЗ є реалізацією функціональних вимог.
Архітектура ПЗ, яку також можна представити у вигляді розробки стратегії – це діяльність, що зв’язана з визначенням глобальних обмежень, що накладаються на проектування системи, такиі як вибір парадигми програмування, архітектурних стилів, стандарти розробки ПЗ, що засновані на використанні компонентів, принципи проектування та обмеження, що накладаються державним законодавством. Детальне проектування, розробка тактики – це діяльність зв’язана з визначенням локальних обмежень проекту, такі як шаблони проектування, архітектурні моделі, ідіоми програмування й рефакторингу. Згідно гіпотези «напруги/околи» (Intension/Locality Hyphotysis), різниця між архітектурним и детальним проектуванням визначаєтся критерієм околу (Locality Criteria), згідно якому твердження, що дизайн ПЗ не є локальним (а є архітектурним) істино тоді і тільки тоді, коли програма, яка задовольняє цьому критерію може бути розширена в програму, яка не задовольняє йому. Наприклад, стиль додатку клієнт–сервер є архітектурним стилем (стратегічним дизайном), тому що програма, яка побудована на цьому принципі, може бути розширена в програму, яка не є клієнт–сервером, шляхом додавання peer–to–peer вузлів.
Архітектура є проектуванням (дизайном), але не всякий дизайн є архітектурним дизайном. На практиці
19.06.2013 12:06-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора