Квадратичний час О(N2)

1.19. Логарифмічний час О(log N) та О(N log N).

1.20. Час факторіалу О(N!).

Для позначення складності виконується так звана О-нотація (від англ. «order» – порядок), згідно з якою алгоритми бувають різного порядку складності:

– О(1) – алгоритм першого порядку складності – завжди займає один і той самий час на виконання;

– О(N) – алгоритм N-ного порядку складності – час зростає лінійно, пропорційно до N;

– O(N²) – алгоритм порядку складності N² – час зростає квадратично;

– O(log N) – алгоритм логарифмічного порядку складності – час зростає логарифмічно;

– O(N log N) – логарифмічно за певною основою;

– O(N!) – алгоритм порядку складності N! – час зростає у факторіальній залежності.

На рис. 1.2 подано схематичне зображення різних порядків складності.

Рисунок 1.2 – Схематичне представлення різних порядків складності алгоритмів

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

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

1.21. Оптимізація алгоритмів

Алгоритми класу складності NP вважаються неприйнятними для реалізації на сучасних ЕОМ у їх прямому вигляді.

Необхідно знаходити способи оптимізації алгоритмів.

Приклад:

– Якщо необхідно перевірити, чи є число 15256677987889881453 складеним, і у нас є число 123567898761 (яке називається свідком), то виявиться, що залишок від ділення одного на інше рівний нулю і перше число є складеним

– У даному разі задача класу складності NP може бути зведеною до меншого класу складності за рахунок того, що вирішуватись буде не початкова задача, а допоміжна спрощена задача (наприклад, пошук свідка)

– Яким чином можна оптимізувати алгоритм, якщо свідок невідомий?

Розгортання циклів.

Розгортання циклів дозволяє зменшити кількість ітерацій, зменшивши таким чином кількість службових операцій, які необхідно виконати для реалізації циклу (переходи, збільшення значення лічильника, перевірка умови циклу)

Розглянемо простий код:

int[] a = new int[10];

for (int i = 0; i < 10; i++)

{

a[i] = i * 2;

}

Яким чином наведений цикл можна розгорнути?

Варіанти розгортання циклу.

Варіант 1:

for (int i = 0; i < 10; i+=2)

{

a[i] = i * 2;

a[i + 1] = (i + 1) * 2;

}

Варіант 2:

for (int i = 0; i < 10; i += 5)

{

a[i] = i * 2;

a[i + 1] = (i + 1) * 2;

a[i + 2] = (i + 2) * 2;

a[i + 3] = (i + 3) * 2;

a[i + 4] = (i + 4) * 2;

}

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

Команди для вимірювання часу виконання коду в C#:

/* Read the initial time. */

DateTime startTime = DateTime.Now;

Console.WriteLine(startTime);

/* Do something that takes up some time. */

...

/* Read the end time. */

DateTime stopTime = DateTime.Now;

Console.WriteLine(stopTime);

/* Compute the duration between the initial and the end time. */

TimeSpan duration = stopTime - startTime;

Console.WriteLine(duration);

Лекція 2. Структури даних в алгоритмічній мові програмування

План лекції

1. Визначення алгоритмічної мови програмування.

2. Базові елементи сучасної мови програмування: типи даних; екземпляри даних; вирази; оператори; функції; класи.

3. Поняття типу даних.

4. Прості типи: числові; символьні; логічні.

5. Тип даних рядок.

6. Структуровані типи даних: масиви, записи, множини.

7. Типи даних за значенням та за посиланням.

8. Сумісність типів та перетворення між типами даних.

9. Екземпляри даних: змінні; константи.

10. Видимість даних..

Для самостійного вивчення:

–

2.1. Визначення алгоритмічної мови програмування

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

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

Приклад алгоритмічних мов програмування: АЛГОЛ, BASIC, Pascal, C/C++, Java, C#.

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

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

Функціональне програмування.

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

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

Приклад функціональних мов програмування: Haskell, Erlang, Nemerle, F#.

Логічне програмування.

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

Першою мовою логічного програмування була мова Planner, в якій була закладена можливість автоматичного виведення результату з даних і заданих правил перебору варіантів (сукупність яких називалася планом). Planner використовувався для того, щоб знизити вимоги до обчислювальних ресурсів (за допомогою методу backtracking) і забезпечити можливість виведення фактів, без активного використання стека. Потім була розроблена мова Prolog, яка не вимагала плану перебору варіантів і була, в цьому смислі, спрощенням мови Planner.

Від мови Planner також відбулися логічні мови програмування QA-4, Popler, Conniver, і QLISP. Мови програмування Mercury, Visual Prolog, Oz і Fril будувалися вже від мови Prolog. На базі мови Planner було розроблене також декілька альтернативних мов логічного програмування, не заснованих на методі backtracking, наприклад, Ether

2.2. Базові елементи сучасної мови програмування: типи даних; екземпляри даних; вирази; оператори; функції; класи.

Основні складові мови програмування (незалежно від парадигми):

Алфавіт — символи, дозволені для запису команд і даних. Як правило, це літери латинського алфавіту, арабські цифри, розділові знаки, спеціальні символи.

Команди — перелік і правила запису дій, які передбачені мовою програмування.

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

Ідентифікатори — символьне позначення (ім’я, адреса) даних, функцій, програм тощо.

Коментарі — пояснення до команд і програм.

Синтаксис — правила запису команд, опису і позначення даних, використання розділових знаків, коментарів тощо.

Семантика — опис дій для виконання написаних без синтаксичних помилок команд і визначення даних.

Основні складові алгоритмічної мови

Ідентифікатори (імена) – послідовність символів для позначення об’єктів програми (змінних, масивів, функцій)

Операції: арифметичні; логічні; відношення; конкатенації.

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

Дані – величини, які обробляються програмою. Типи даних – розмежування даних мови програмування за певними групами (типами). У мовах програмування зі строгою типізацією (Pascal, C-подібні мови) тип даних задається явно, існують жорсткі обмеження на неявне перетворення між типами даних. У мовах програмування з нестрогою типізацією (BASIC) тип даних можна не задавати, визначається автоматично, перетворення між типами більш гнучке. Екземпляри даних – це конкретні змінні і константи певного типу, які зберігають значення:

Константи – це дані, які зафіксовані під час виконання програми і не можуть бути змінені.

Змінні – це дані, які можуть змінювати своє значення під час виконання програми.

Складні типи даних можуть поєднувати декілька складових: масиви, записи, об’єкти.

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

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

Структурні складові

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

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

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

Стандартна функція (підпрограма) – підпрограма, яка вбудована у мову програмування (стандартні бібліотеки функцій).

Класи і об’єкти

Клас – особлива структурна одиниця об’єктно-орієнтованих мов (ОО) програмування, яка поєднує дані і код, що призначений для їх обробки. За своїм характером близька до типу даних, тому у мовах програмування, які є повністю об’єктно-орієнтованими (Smalltalk), всі типи даних є класами.

Об’єкт – це екземпляр класу, тобто конкретна змінна, що зберігає дані, структура яких визначена декларацією класу.

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