Алгоритми і структури даних Опорний конспект лекцій для студентів заочно-дистанційної форми навчання спеціальності „Економічна кібернетика”



Сторінка1/19
Дата конвертації20.11.2016
Розмір1.02 Mb.
  1   2   3   4   5   6   7   8   9   ...   19

Міністерство освіти і науки України

Тернопільський державний економічний університет

Факультет комп’ютерних інформаційних технологій




Алгоритми і структури даних
Опорний конспект лекцій

для студентів заочно-дистанційної форми навчання

спеціальності „Економічна кібернетика”

Тернопіль – 2006




Струбицький П.Р., Бондар О.В. Алгоритми і структури даних – Опорний конспект лекцій для студентів заочно-дистанційної форми навчання – Тернопіль: ТДЕУ, 2006 – с.

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

Посібник рекомендований для студентів спеціальностей „Економічна кібернетика”, „Комп’ютерні системи та мережі” та „Програмне забезпечення автоматизованих систем”.
Укладачі: Струбицький Павло Романович, к.т.н., доцент кафедри Економічної кібернетики ТАНГ;

Бондар Олесь Васильович, викладач кафедри Економічної кібернетики ТАНГ.

Друкується за рішенням редакційно-видавничої ради.
Відповідальний за випуск: к.е.н., доцент Гладій Г. М.
Рецензенти:

завідувач кафедри Комп’ютерних наук ТДЕУ,

д.т.н., професор Дивак М.П.

завідувач кафедри Інформатики та методики її викладання ТНПУ, к.ф.-м.н., доцент Мартинюк С.В.




ВСТУП


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

Ніколас Вірт
Без розуміння структур даних і алгоритмів неможливо створити серйозний програмний продукт. І слова епіграфу є цьому підтвердженням. Тому головна мета даного навчального посібника полягає в наступному:

  • показати всю різноманітність існуючих структур даних, представлення їх в пам’яті на фізичному рівні і на логічному рівні;

  • виконувані над ними операції фізичного і логічного рівнів;

  • показати значення структурного підходу до розробки алгоритмів.

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

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


1.АЛГОРИТМИ і дані

1.1.Структурування і абстракція програм


Будь-які достатньо великі програми проектуються шляхом декомпозиції задачі – виділення в задачі деяких структур і їхніх абстракцій. Абстрагування від проблеми передбачає ігнорування ряду деталей для того, щоб звести задачу до більш простої. Задачі абстрагування і наступна декомпозиція типові для процесу створення програм: декомпозиція використовується для поділу програм на компоненти; абстрагування ж передбачає продуманий вибір компонентів для цієї задачі.

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

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

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

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

Інший підхід базується на структуризації даних (програмування – це обробка даних). У програмах можна застосовувати різні алгоритми, але в реальної програми завжди є замовник, який маючи вхідні дані, хоче, щоб за ними можна було отримати вихідні дані, а якими засобами це забезпечується – його не цікавить. Таким чином, задачею будь-якої програми є перетворення вхідних даних у вихідні. Мови програмування представляють набір базових типів даних і операції над ними. Інтегруючи базові типи, програміст створює більш складні типи даних і визначає нові операції над складними типами. В ідеалі останній крок композиції дає типи даних, які відповідають вхідним і вихідним даним задачі, а операції над цими типами реалізують в повному обсязі задачу проекту. Розглядаючи програму не як набір функцій, а перш за все, як деякий набір даних, кожен, із яких має дозволену групу функцій, отримують наступне абстрактне представлення програми.

Аналіз такого представлення програми дозволяє також отримати абстракцію даних.

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

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

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

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

  1   2   3   4   5   6   7   8   9   ...   19


База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка