Головна

Поняття структур даних та алгоритмів

  1. D. Об отношении частных форм структуры к общему строю.
  2. EGO-СТРУКТУРИРОВАННОСТИ СОЗНАНИЯ
  3. I. ВАРИАЦИИ ОКРАСОВ И СТРУКТУРЫ ШЕРСТИ
  4. I. Поняття, предмет, метод та система трудового права України
  5. II. Структура психологического исследования.
  6. II. СТРУКТУРНАЯ СХЕМА АСОИУ
  7. III. Требования к структуре основной образовательной программы

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

Задачі, розв'язувані за допомогою комп'ютера, рідко виражаються мовою бітів. Як правило, дані мають формат чисел, літер, текстів, символів і більш складних структур, наприклад, послідовностей, списків і дерев. Ще різноманітніше алгоритми, які застосовуються для рішення різних задач; фактично алгоритмів не менше ніж обчислювальних задач. Для точного опису абстрактних структур даних і алгоритмів програм використовуються системи формальних позначень, що називаються мовами програмування, коли зміст всякого речення визначається точно й однозначно. Серед засобів, що представляються майже всіма мовами програмування, є можливість посилатися на елемент даних, користуючись привласненим йому ім'ям чи ідентифікатором. Одні іменовані величини є константами, що зберігають постійне значення в тій частині програми, де вони визначені, інші - змінними, яким у програмі може бути привласнене будь-яке нове значення. Компілятор, що транслює текст програми в двійковий код, зв'язує кожен ідентифікатор з визначеною адресою пам'яті. Однак, для того, щоб компілятор зміг це виконати, необхідно повідомити "тип" кожної іменованої величини.

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

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

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

 



ГЛАВА 1 | Збереження інформації

Системи числення | Класифікація структур даних | Базові операції над структурами даних | Технологія програмування | Аналіз розроблюваних алгоритмів |

© um.co.ua - учбові матеріали та реферати