Алгоритм впорядкування купою

Робота алгоритму сортування купою починається з віклику процедури Build_Max_H, за допомогою якої з початкового масиву A[1 n] створюється незростаюча купа. Далі послідовно з купи виймається найбільший елемент, який міняють з останнім в купі. Після кожного обміну розмір купи зменшують на одиницю. В кінці отримують повністю відсортований неспадній масив:

Heapsort(A)

1 Build_Max_Heap(A)

2 for downto 2

3 do Поміняти

4

5 Max_Heapify(A,1)

Час роботи процедури Heapsort рівний O(n log n), оскільки всього потрібно n-1 викликів Max_Heapify, кожен з яких працює за O(log n).

Б) Біноменальна купа

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

Кожне біноміальне дерево у купі підпорядковується властивості неспадної купи (англ. min-heap property): ключ вузла не менший за ключ його батьківського вузла.

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

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

Лекція 10. Об‘єктно-орієнтований стиль програмування.

Абстрагування є одним із головних засобів, використовуваних для розв’язування складних задач.
Абстракція — це такі істотні характеристики деякого об’єкта, які відрізняють його від усіх інших видів об’єктів і, отже, чітко визначають істотні особливості даного об’єкта щодо подальшого розгляду та аналізу.
Абстрагування концентрує увагу на зовнішніх особливостях об’єкта й дозволяє відокремити найістотніші особливості поведінки від деталей їх здійснення.
Таке відокремлення (поведінки від здійснення) називається бар­тером абстракції, який базується на принципі мінімізації зв’язків, коли інтерфейс об’єкта містить лише істотні аспекти поведінки. Корисним є ще один додатковий принцип, який називається принципом найменшої виразності, згідно з яким абстракція має відбивати лише саму суть об’єкта, не більше, але і не менше. Вибір достатньої множини абстракцій для заданої предметної області є головною проблемою об’єктно-орієнтованого проектування.

• Абстракція сутності об’єкта — об’єкт являє собою модель істотних сторін предметної області.
• Абстракція поведінки — об’єкт складається з узагальненої мно­жини операцій, кожна з яких виконує певну функцію.
• Абстрагування щодо вигляду — об’єкт об’єднує групи операцій віртуальної машини, які або використовуються для управління об’єктом, або відповідають функціям нижнього рівня.
• Довільна абстракція — об’єкт включає в себе набір не залежних одна від одної операцій.

Об'єктно-орієнтоване програмування (ООП) — одна з парадигм програмування, яка розглядає програму як множину «об'єктів», що взаємодіють між собою. В ній використано декілька технологій від попередніх парадигм, зокрема успадкування, модульність, поліморфізм та інкапсуляцію. Незважаючи на те, що ця парадигма з'явилась в 1960-тих роках, вона не мала широкого застосування до 1990-тих. На сьогодні багато із мов програмування (зокрема, Java, C#, C++, Python, PHP, Ruby та Objective-C, ActionScript 3) підтримують ООП.

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

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

Дата добавления: 2014-01-05