ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Юрист по наследству
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

         
     
    VB, MS Access, VC + +, Delphi, Builder C + + принципи (технологія), алгоритми програмування
         

     

    Інформатика, програмування

    Введення 8

    Цільова аудиторія 10

    Глава 1. Основні поняття 15

    Що таке алгоритми? 15

    Аналіз швидкості виконання алгоритмів 16

    Простір - час 17

    Оцінка з точністю до порядку 17

    Пошук складних частин алгоритму 19

    Складність рекурсивних алгоритмів 20

    Багаторазова рекурсія 21

    Непряма рекурсія 22

    Вимоги рекурсивних алгоритмів до обсягу пам'яті 22

    Найгірший і усереднений випадок 23

    часто зустрічаються функції оцінки порядку складності 24

    Логарифми 25

    Реальні умови - наскільки швидко? 25

    Звернення до файлу підкачки 26

    Псевдоуказателі, посилання на об'єкти і колекції 27

    Резюме 29

    Глава 2. Списки 30

    Знайомство зі списками 31

    Прості списки 31

    Колекції 32

    Список змінного розміру 33

    Клас SimpleList 36

    неврегульовані списки 37

    Зв'язкові списки 41

    Додавання елементів до зв'язного списку 43

    Видалення елементів із зв'язкового списку 44

    Знищення зв'язкового списку 44

    Сигнальні мітки 45

    Інкапсуляція зв'язкових списків 46

    Доступ до осередків 47

    Різновиди зв'язкових списків 49

    Циклічні зв'язкові списки 49

    Проблема циклічних посилань 50

    Двусвязние списки 50

    Потоки 53

    Інші зв'язкові структури 56

    Псевдоуказателі 56

    Резюме 59

    Глава 3. Стеки і черги 60

    Стеки 60

    Множинні стеки 62

    Черги 63

    Циклічні черзі 65

    Черги на основі зв'язкових списків 69

    Застосування колекцій як черг 70

    Пріоритетні черзі 70

    Багатопотокові черзі 72

    Резюме 74

    Глава 4. Масиви 75

    Трикутні масиви 75

    Діагональні елементи 77

    Нерегулярні масиви 78

    Пряма зірка 78

    Нерегулярні зв'язкові списки 79

    розріджені масиви 80

    Індексування масиву 82

    Дуже розріджені масиви 85

    Резюме 86

    Глава 5. Рекурсія 86

    Що таке рекурсія? 87

    Рекурсивна обчислення факторіали 88

    Аналіз часу виконання програми 89

    Рекурсивна обчислення найбільшого спільного дільника 90

    Аналіз часу виконання програми 91

    Рекурсивна обчислення чисел Фібоначчі 92

    Аналіз часу виконання програми 93

    Рекурсивна побудова кривих Гільберта 94

    Аналіз часу виконання програми 96

    Рекурсивна побудова кривих Серпінського 98

    Аналіз часу виконання програми 100

    Небезпеки рекурсії 101

    Нескінченна рекурсія 101

    Втрати пам'яті 102

    Необгрунтоване застосування рекурсії 103

    Коли потрібно використовувати рекурсію 104

    Хвостова рекурсія 105

    Нерекурсівное обчислення чисел Фібоначчі 107

    Усунення рекурсії в загальному випадку 110

    Нерекурсівное побудова кривих Гільберта 114

    Нерекурсівное побудова кривих Серпінського 117

    Резюме 121

    Глава 6. Дерева 121

    Визначення 122

    Подання дерев 123

    Повні вузли 123

    Списки нащадків 124

    Представлення нумерацією зв'язків 126

    Повні дерева 129

    Обхід дерева 130

    Впорядковані дерева 135

    Додавання елементів 135

    Видалення елементів 136

    Обхід впорядкованих дерев 139

    Дерева з посиланнями 141

    Робота з деревами з посиланнями 144

    Квадродеревья 145

    Зміна MAX_PER_NODE 151

    Використання псевдоуказателей в квадродеревьях 151

    Вісімкове дерева 152

    Резюме 152

    Глава 7. Збалансовані дерева 153

    Збалансованість дерева 153

    АВЛ-дерева 154

    Видалення вузла з АВЛ-дерева 161

    Б-дерева 166

    Продуктивність Б-дерев 167

    Вставка елементів в Б-дерево 167

    Видалення елементів із Б-дерева 168

    Різновиди Б-дерев 169

    Поліпшення продуктивності Б-дерев 171

    Балансування для усунення розбиття блоків 171

    Питання, пов'язані зі зверненням до диска 173

    База даних на основі Б + дерева 176

    Резюме 179

    Глава 8. Дерева рішень 179

    Пошук в деревах ігри 180

    Мінімакс пошук 181

    Поліпшення пошуку в дереві гри 185

    Пошук в інших деревах рішень 187

    Метод гілок і меж 187

    евристики 191

    Інші складні завдання 207

    Задача про здійснимість 207

    Задача про розбивання 208

    Завдання пошуку Гамільтона шляху 209

    Завдання комівояжера 210

    Задача про пожежних депо 211

    Коротка характеристика складних завдань 212

    Резюме 212

    Глава 9. Сортування 213

    Загальні міркування 213

    Таблиці покажчиків 213

    Об'єднання і стиснення ключів 215

    Приклади програм 217

    Сортування вибором 219

    Рандомізація 220

    Сортування вставкою 221

    Вставка у зв'язаних списках 222

    Бульбашкова сортування 224 < p> Швидке сортування 227

    Сортування злиттям 232

    Пірамідальна сортування 234

    Піраміди 235

    Пріоритетні черги 237

    Алгоритм пірамідальною сортування 240

    Сортування підрахунком 241

    Сортування комірками 242

    Сортування комірками із застосуванням зв'язкового списку 243

    Сортування комірками на основі масиву 245

    Резюме 248

    Глава 10. Пошук 248

    Приклади програм 249

    Пошук методом повного перебору 249

    Пошук в упорядкованих списках 250

    Пошук у зв'язаних списках 251

    Двійковий пошук 253

    Інтерполяційний пошук 255

    рядкові дані 259

    Стежачий пошук 260

    Інтерполяційний стежить пошук 261

    Резюме 262

    Глава 11. Хешування 263

    Зв'язування 265

    Переваги і недоліки зв'язування 266

    Блоки 268

    Зберігання хеш-таблиць на диску 270

    Зв'язування блоків 274

    Видалення елементів 275

    Переваги і недоліки застосування блоків 277

    Відкрита адресація 277

    Лінійна перевірка 278

    Квадратична перевірка 284

    псевдовипадкових перевірка 286

    Видалення елементів 289

    Резюме 291

    Глава 12. Мережеві алгоритми 292

    Визначення 292

    Подання мережі 293

    Оперувати вузлами і зв'язками 295

    Обходи мережі 296

    Найменші остовне дерева 298

    Найкоротший маршрут 302

    Установка міток 304

    Корекція міток 308

    Інші задачі пошуку найкоротшого маршруту 311

    Застосування методу пошуку найкоротшого маршруту 316

    Максимальний потік 319

    Програми максимального потоку 325

    Резюме 327

    Глава 13 . Об'єктно-орієнтовані методи 327

    Переваги ООП 328

    Інкапсуляція 328

    Поліморфізм 330

    Спадкування і повторне використання 333 < p> Парадигми ООП 335

    Керуючі об'єкти 335

    Контролюючий об'єкт 336

    ітератор 337

    Дружній клас 338

    Інтерфейс 340

    Фасад 340

    породжує об'єкт 340

    Єдиний об'єкт 341

    Перетворення в послідовну форму 341

    Парадигма Модель/Вид/Контроллер. 344

    Резюме 346

    Вимоги до апаратного забезпечення 346

    Виконання програм прикладів 346

    [email protected]

    Далі йде «текст», який будь-який поважає себе, програміст повиненпрочитати хоча б один раз. (Це наше суб'єктивна думка)

    Введення

    Програмування під Windows завжди було нелегким завданням. Інтерфейсприкладного програмування (Application Programming Interface) Windowsнадає в розпорядження програміста набір потужних, але не завждибезпечних інструментів для розробки додатків. Можна порівняти його збульдозером, за допомогою якого вдається досягти разючихрезультатів, але без відповідних навичок і обережності, швидше за все,справа закінчиться тільки руйнуваннями і збитками.
    Ця картина змінилася з появою Visual Basic. Використовуючи візуальнийінтерфейс, Visual Basic дозволяє швидко і легко розробляти закінченідодатки. За допомогою Visual Basic можна розробляти і тестуватискладні програми без прямого використання функцій API. Позбавляючипрограміста від проблем з API, Visual Basic дозволяє сконцентруватися надеталі програми.
    Хоча Visual Basic і полегшує розробку для користувача інтерфейсу,завдання написання коду для реакції на вхідні впливу, обробки їх, іпредставлення результатів лягає на плечі програміста. Тут починаєтьсязастосування алгоритмів.
    Алгоритми являють собою формальні інструкції для виконання складнихзавдань на комп'ютері. Наприклад, алгоритм сортування може визначати, якзнайти певний запис у базі з 10 мільйонів записів. Залежно відкласу використовуваних алгоритмів шукані дані можуть бути знайдені засекунди, годинник або взагалі не знайдені.
    У цьому матеріалі обговорюються алгоритми на Visual Basic і міститься великакількість потужних алгоритмів, повністю написаних на цій мові. У ній такожаналізуються методи поводження зі структурами даних, такими, як списки,стеки, черги і дерева, і алгоритми для виконання типових завдань, такихяк сортування, пошук і хешування.
    Для того щоб успішно застосовувати ці алгоритми, недостатньо їх простоскопіювати в свою програму. Необхідно крім цього розуміти, якрізні алгоритми ведуть себе в різних ситуаціях, що в кінцевому результаті ібуде визначати вибір найбільш відповідного алгоритму.
    У цьому матеріалі поведінка алгоритмів в типовому і найгіршому випадкахописано доступною мовою. Це дозволить зрозуміти, чого ви вправі очікувати відтого чи іншого алгоритму і розпізнати, в яких умовах зустрічаєтьсянайгірший випадок, і відповідно до цього переписати або поміняти алгоритм.
    Навіть найкращий алгоритм не допоможе у вирішенні завдання, якщо застосовувати йогонеправильно.

    ============= xi

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

    Що дають вам ці знання
    Після ознайомлення з даним матеріалом і прикладами ви отримаєте:
    1. Поняття про алгоритми. Після прочитання даного матеріалу і виконання прикладів програм, Ви зможете використовувати складні алгоритми у своїх проектах на Visual Basic і критично оцінювати інші алгоритми, написані вами або ким-небудь ще.
    2. Велику підбірку початкових текстів, які ви зможете легко додати до ваших програм. Використовуючи код, що міститься в прикладах, ви зможете легко додавати потужні алгоритми до ваших програм.
    3. Готові приклади програм дадуть вам можливість протестувати алгоритми.

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

    Цільова аудиторія

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

    Сумісність з різними версіями Visual Basic
    Вибір найкращого алгоритму визначається не особливостями версії мовипрограмування, а фундаментальними принципами програмування.

    ================= xii

    Деякі нові поняття, такі як посилання на об'єкти, класи та колекції,які були вперше введені в 4-й версії Visual Basic, полегшуютьрозуміння, розробку і налагодження деяких алгоритмів. Класи можутьукладати деякі алгоритми в добре продуманих модулях, які легковставити в програму. Хоча для того, щоб застосовувати ці алгоритми,необов'язково розбиратися в нових поняттях мови, ці нові можливостінадають занадто великі переваги, щоб ними можна булознехтувати.
    Тому приклади алгоритмів у цьому матеріалі написані для використання в 4 --й і 5-й версіях Visual. Якщо ви відкриєте їх в 5-й версії Visual Basic,Середа розробки запропонує вам зберегти їх у форматі 5-й версії, аленіяких змін в код вносити не доведеться. Всі алгоритми булипротестовані в обох версіях.
    Ці програми демонструють використання алгоритмів без застосуванняоб'єктно-орієнтованого підходу. Посилання та колекції полегшуютьпрограмування, але їх застосування може призводити до деякого уповільненняроботи програм в порівнянні зі старими версіями.
    Тим не менше, ігнорування класів, об'єктів і колекцій призвело б донедогляду багатьох справді потужних властивостей. Їх використання дозволяєдосягти нового рівня модульності, розробки та повторного використаннякоду. Їх, безумовно, необхідно мати на увазі, принаймні, напочаткових етапах розробки. Надалі, якщо виникнуть проблеми зпродуктивністю, ви зможете модифікувати код, використовуючи більш швидкінизькорівневі методи.
    Мови програмування часто розвиваються в бік ускладнення, але рідков протилежному напрямку. Чудовим прикладом цього єнаявність оператора goto у мові C. Це незручний оператор, потенційнийджерело помилок, який майже не використовується більшістю програмістівна C, але він як і раніше залишається в синтаксисі мови з 1970 року. Він навітьбув включений в C + + і пізніше в Java, хоча створення нової мови було гарнимприводом позбутися від нього.
    Так і нові версії Visual Basic будуть продовжувати вводити нові властивості вмову, але малоймовірно, що з них будуть виключені будівельні блоки,використані при застосуванні алгоритмів, описаних у цьому матеріалі.
    Незалежно від того, що буде додано до 6-й, 7-й або 8-й версії Visual
    Basic, класи, масиви і визначені користувачем типи даних залишаться вмовою. Більша частина, а може і всі алгоритми з наведених нижче, будутьвиконуватися без змін протягом ще багатьох років.

    Огляд глав
    У 1 розділі розглядаються поняття, що ви повинні розуміти до того, якприступити до аналізу складних алгоритмів. У ній викладені методи, якібудуть потрібні для теоретичного аналізу обчислювальної складності алгоритмів.
    Деякі алгоритми з високою теоретичною продуктивністю на практицідають не дуже хороші результати, тому в цій главі також зачіпаютьсяпрактичні міркування, наприклад звернення до файлу підкачки іпорівнюється використання колекцій і масивів.
    У 2 чолі показано, як утворюються різні види списків з використанняммасивів, об'єктів, і псевдоуказателей. Ці структури даних можна зуспіхом застосовувати в багатьох програмах, і вони використовуються в наступнихглавах
    У 3 розділі описані два особливих типи списків: стеки і черги. Ці структуриданих використовуються в багатьох алгоритмах, включаючи деякі алгоритми,описані в наступних розділах. Наприкінці глави наведена модель черги нареєстрацію в аеропорту.
    У 5 чолі обговорюється потужний інструмент - рекурсія. Рекурсія може бутитакож заплутаною і призводити до проблем. У 5 чолі пояснюється, в якихвипадках слід застосовувати рекурсію і показує, як можна від неїпозбутися, якщо це необхідно.
    У 6 чолі використовуються багато з раніше описаних прийомів, такі якрекурсія і зв'язкові списки, для вивчення більш складної теми - дерев. Цяголова також охоплює різні уявлення дерев, такі як дереваз повними вузлами (fat node) і подання у вигляді нумерацією зв'язків
    (forward star). У ній також описані деякі важливі алгоритми роботи здеревами, таки як обхід вершин дерева.
    У 7 чолі порушено більш складна тема. Збалансовані дерева маютьособливими властивостями, які дозволяють їм залишатися врівноваженими іефективними. Алгоритми збалансованих дерев дивно простоописуються, але їх досить важко реалізувати програмно. У цьому розділівикористовується один з найбільш потужних структур подібного типу - Б + дерево
    (B + Tree) для створення складної бази даних.
    У 8 чолі обговорюються завдання, які можна описати як пошук відповідей удереві рішень. Навіть для невеликих завдань, ці дерева можуть бутигігантськими, тому необхідно здійснювати пошук в них максимальноефективно. У цьому розділі порівнюються деякі різні методи, якідозволяють виконати такий пошук.

    Глава 9 присвячена, мабуть, найбільш досліджуваної галузі теоріїалгоритмів - сортування. Алгоритми сортування цікаві з кількохпричин. По-перше, сортування - часто зустрічається завдання. По-друге,різні алгоритми сортувань володіють своїми сильними і слабкимисторонами, тому не існує одного алгоритму, який показував бинайкращі результати в будь-яких ситуаціях. І, нарешті, алгоритми сортуваннядемонструють широкий спектр важних алгоритмічних методів, таких якрекурсія, піраміди, а також використання генератора випадкових чисел длязменшення ймовірності випадання найгіршого випадку.
    У главі 10 розглядається близька до сортування тема. Після виконаннясортування списку, програму може знадобитися знайти елементи в ньому. Уцій главі порівнюється кілька найбільш ефективних методів пошукуелементів у сортованих списках.

    ========= xiv

    У главі 11 обговорюються методи збереження і пошуку елементів, що працюютьнавіть швидше, ніж це можливо при використанні дерев, сортування абопошуку. У цьому розділі також описані деякі методи хешування, включаючивикористання блоків і зв'язкових списків, і кілька варіантів відкритоїадресації.
    У главі 12 описана інша категорія алгоритмів - мережеві алгоритми.
    Деякі з цих алгоритмів, такі як обчислення найкоротшого шляху,безпосередньо застосовні до фізичних мереж. Ці алгоритми також можутьпобічно застосовуватися для вирішення інших завдань, які на перший погляд нездаються пов'язаними з мережами. Наприклад, алгоритми пошуку найкоротшоговідстані можуть розбивати мережу на райони або визначати критичні завдання врозклад проекту.
    У главі 13 пояснюються методи, застосування яких стало можливим завдякивведенню класів в 4-й версії Visual Basic. Ці методи використовують об'єктно -орієнтований підхід для реалізації нетипового для традиційнихалгоритмів поведінки.

    =================== xv


    Апаратні вимоги
    Для роботи з прикладами вам буде потрібно комп'ютер, конфігурація якогозадовольняє вимогам для роботи програмного середовища Visual Basic. Цівимоги виконуються майже для всіх комп'ютерів, на яких можепрацювати операційна система Windows.
    На комп'ютерах різної конфігурації алгоритми виконуються з різноюшвидкістю. Комп'ютер з процесором Pentium Pro з тактовою частотою 2000 МГці 64 Мбайт оперативної пам'яті буде працювати набагато швидше, ніж машина з
    386 процесором і всього 4 Мбайт пам'яті. Ви швидко дізнаєтеся, на що здатневаше апаратне забезпечення.

    Зміни у другому виданні
    Найбільша зміна в новій версії Visual Basic - це появакласів. Класи дозволяють розглянути деякі завдання з іншого боку,дозволяючи використовувати більш простий і природний підхід до розуміння ізастосування багатьох алгоритмів. Зміни в коді програм в цьому викладівикористовують переваги, надані класами. Їх можна розбити на трикатегорії:
    1. Заміна псевдоуказателей класами. Хоча всі алгоритми, які були написані для старих версій VB, все ще працюють, багато хто з тих, що були написані з застосуванням псевдоуказателей (описаних у 2 розділі), набагато простіше зрозуміти, використовуючи класи.
    2. Інкапсуляція. Класи дозволяють укласти алгоритм в компактний модуль, який легко використовувати в програмі. Наприклад, за допомогою класів можна створити кілька зв'язкових списків і не писати при цьому додатковий код для керування кожним списком окремо.
    3. Об'єктно-орієнтовані технології. Використання класів також дозволяє легше зрозуміти деякі об'єктно-орієнтовані алгоритми. У главі 13 описуються методи, які складно реалізувати без використання класів.

    Як користуватися цим матеріалом
    У главі 1 даються загальні поняття, які використовуються протягом усьоговикладу, тому вам слід почати читання з цієї глави. Вам вартоознайомитися з цією тематикою, навіть якщо ви не хочете відразу ж досягтиглибокого розуміння алгоритмів.
    У 6 чолі обговорюються поняття, що використовуються в 7, 8 і 12 главах,тому вам слід прочитати 6 голову до того, як братися за них.
    Решта глави можна читати в будь-якому порядку.

    ============= xvi

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

    Останній план дає порядок для вивчення всього матеріалу цілком. Хоча 7і 8 глави логічно випливають з 6 розділу, вони складніше для вивчення, ніжнаступні голови, тому вони вивчаються трохи пізніше.

    Чому саме Visual Basic?
    Найчастіше зустрічаються скарги на повільне виконання програм,написаних на Visual Basic. Багато інших компілятори, такі як Delphi,
    Visual C + + дають більш швидкий і гнучкий код, і надають програмістубільш потужні засоби, ніж Visual Basic. Тому логічно поставити питання -
    «Чому я повинен використовувати саме Visual Basic для написання складнихалгоритмів? Чи не краще було б використовувати Delphi або C + + або, по крайнеймірою, написати алгоритми на одному з цих мов і підключати їх допрограмами на Visual Basic за допомогою бібліотек? »Написання алгоритмів на
    Visual Basic має сенс з кількох причин.
    По-перше, розробка програми на Visual C + + набагато складніше іпроблематичніше, ніж на Visual Basic. Некорректна реалізація в програмівсіх деталей програмування під Windows може призвести до збоїв у вашомудодатку, середовищі розробки, або в самій операційній системі Windows.
    По-друге, розробка бібліотеки на мові C + + для використання впрограмах на Visual Basic включає в себе багато потенційних небезпек,характерних і для додатків Windows, написаних на C + +. Якщо бібліотекабуде неправильно взаємодіяти з програмою на Visual Basic, вона такожприведе до збоїв у програмі, а можливо і в середовищі розробки і системі.
    По-третє, багато алгоритми досить ефективні і показують непоганупродуктивність навіть при застосуванні не дуже швидких компіляторів,таких, як Visual Basic. Наприклад, алгоритм сортування підрахунком,

    @ Таблиця 1. Плани занять

    =============== xvii

    описуваний в 9 розділі, сортує мільйон цілих чисел менш ніж за 2 секундина комп'ютері з процесором Pentium з тактовою частотою 233 МГц. Використовуючибібліотеку C + +, можна було б зробити алгоритм трохи швидше, але швидкостіверсії на Visual Basic і так вистачає для більшості додатків.
    Скомпільовані за допомогою 5-й версією Visual Basic виконувані файлизводять відставання по швидкості до мінімуму.
    У кінцевому рахунку, розробка алгоритмів на будь-якій мові програмуваннядозволяє більше дізнатися про алгоритми взагалі. У міру вивчення алгоритмів,ви засвоїте методи, які зможете використовувати в інших частинах своїхпрограм. Після того, як ви оволодієте досконало алгоритмами на Visual
    Basic, вам буде набагато легше реалізувати їх на Delphi або C + +, якщо цебуде необхідно.

    ============= xviii


    Глава 1. Основні поняття

    У цьому розділі містяться загальні поняття, які потрібно засвоїти перед початкомсерйозного вивчення алгоритмів. Починається вона з питання «Що такеалгоритми? ». Перш ніж заглибитися в деталі програмування алгоритмів,варто витратити трохи часу, щоб розібратися в тому, що це таке.
    Потім в цьому розділі дається введення у формальну теорію складності алгоритмів
    (complexity theory). За допомогою цієї теорії можна оцінити теоретичнуобчислювальну складність алгоритмів. Цей підхід дозволяє порівнюватирізні алгоритми і передбачати їх продуктивність в різнихумовах. У розділі наводиться декілька прикладів застосування теорії складностідо невеликих завдань.
    Деякі алгоритми з високою теоретичною продуктивністю не дужедобре працюють на практиці, тому в даній главі також обговорюютьсядеякі реальні передумови для створення програм. Занадто частезвернення до файлу підкачки або погане використання посилань на об'єкти іколекції може значно знизити продуктивність прекрасного вінших відносинах програми.
    Після знайомства з основними поняттями, ви зможете застосовувати їх доалгоритмами, викладеним у наступних розділах, а також для аналізувласних програм для оцінки їх продуктивності і зможетепередбачати можливі проблеми до того, як вони обернуться катастрофою.

    Що таке алгоритми?

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

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


    ========== 1

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

    Якщо двері закриті:

    Вставити ключ в замок

    Повернути ключ

    Якщо двері залишається закритою, то:

    Повернути ключ в інший бік
    Повернути ручку дверей
    І т.д.

    Цей фрагмент «коду» відповідає лише за відкривання дверей; при цьому навіть неперевіряється, яка двері відкриваються. Якщо двері заїло або в машинівстановлена протиугінна система, то алгоритм відкриття дверей може бутидосить складним.
    Формалізацією алгоритмів займаються вже тисячі років. За 300 років до н.е.
    Евклід написав алгоритми поділу кутів навпіл, перевірки рівностітрикутників та вирішення інших геометричних задач. Він почав з невеликогословника аксіом, таких як «паралельні лінії не перетинаються» і побудувавна їх основі алгоритми для вирішення складних завдань.
    Формалізовані алгоритми такого типу добре підходять для задач математики,де повинна бути доведена істинність будь-якого положення або можливістьвиконання якихось дій, швидкість же виконання алгоритму не важлива.
    Для виконання реальних завдань, пов'язаних з виконанням інструкцій, наприкладзадачі сортування на комп'ютері записів про мільйон покупців,ефективність виконання стає важливою частиною постановки задачі.

    Аналіз швидкості виконання алгоритмів

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

    Простір - час

    Багато алгоритми надають вибір між швидкістю виконання тавикористовуваними програмою ресурсами. Завдання може виконуватисяшвидше, використовуючи більше пам'яті, або навпаки, повільніше, зайнявши меншийобсяг пам'яті.

    =========== 2

    Гарним прикладом у даному випадку може служити алгоритм знаходженнянайкоротшого шляху. Поставивши карту вулиць міста у вигляді мережі, можна написатиалгоритм, що обчислює найкоротша відстань між будь-якими двома точками вцієї мережі. Замість того, щоб кожен раз заново перераховувати найкоротшийвідстань між двома заданими точками, можна наперед прорахувати його длявсіх пар точок і зберегти результати в таблиці. Тоді, щоб знайтинайкоротша відстань для двох заданих точок, досить буде простовзяти готове значення з таблиці.
    При цьому ми отримаємо результат практично миттєво, але це зажадаєвеликого обсягу пам'яті. Карта вулиць для великого міста, такого як Бостонабо Денвер, може містити сотні тисяч точок. Для такої мережі таблицянайкоротших відстаней містила б понад 10 мільярдів записів. У цьомувипадку вибір між часом виконання і обсягом необхідної пам'яті очевидний:поставивши додаткові 10 гігабайт оперативної пам'яті, можна змуситипрограму виконуватися набагато швидше.
    З зв'язку з цим випливає ідея просторово-часової складності алгоритмів.
    При цьому підході складність алгоритму оцінюється в термінах часу іпростору, і знаходиться компроміс між ними.
    У цьому матеріалі основна увага приділяється тимчасової складності, але митакож постаралися звернути увагу і на особливі вимоги до об'єму пам'ятідля деяких алгоритмів. Наприклад, сортування злиттям (mergesort),обговорюється в 9 розділі, вимагає більше тимчасової пам'яті. Інші алгоритми,наприклад пірамідальна сортування (heapsort), яка також обговорюється в 9чолі, вимагає звичайного обсягу пам'яті.

    Оцінка з точністю до порядку

    При порівнянні різних алгоритмів важливо розуміти, як складність алгоритмуспіввідноситься зі складністю розв'язуваної задачі. При розрахунках за одним алгоритмомсортування тисячі чисел може зайняти 1 секунду, а сортування мільйона - 10секунд, у той час як розрахунки за іншим алгоритмом можуть зажадати 2 і 5секунд відповідно. У цьому випадку не можна однозначно сказати, яка здвох програм краще - це буде залежати від вихідних даних.
    Різниця продуктивності алгоритмів на завданнях різної обчислювальноїскладнощі часто більш важливо, ніж просто швидкість алгоритму. Унаведеному вище випадку, перший алгоритм швидше сортує короткі списки,а другий - довгі.
    Продуктивність алгоритму можна оцінити по порядку величини. Алгоритммає складність порядку O (f (N)) (вимовляється «Про велике від F від N»), якщочас виконання алгоритму зростає пропорційно функції f (N) ззбільшенням розмірності вихідних даних N. Наприклад, розглянемо фрагменткоду, сортують позитивні числа:

    For I = 1 To N

    'Пошук найбільшого елемента в списку.

    MaxValue = 0

    For J = 1 to N

    If Value (J)> MaxValue Then

    MaxValue = Value (J)

    MaxJ = J

    End If

    Next J

    'Вивід найбільшого елемента на друк.

    Print Format $ (MaxJ) & ":" & Str $ (MaxValue)

    'Обнулення елементу для виключення його з подальшого пошуку.

    Value (MaxJ) = 0
    Next I


    =============== 3

    У цьому алгоритмі мінлива циклу I послідовно приймає значення від 1до N. Для кожного збільшення I мінлива J в свою чергу також березначення від 1 до N. Таким чином, у кожному зовнішньому циклі виконується ще Nвнутрішніх процедур. У підсумку внутрішній цикл виконується N * N або N2 разів і,отже, складність алгоритму порядку O (N2).
    При оцінці порядку складності алгоритмів використовується тільки найбільш швидкозростаюча частина рівняння алгоритму. Припустимо, час виконання алгоритмупропорційно N3 + N. Тоді складність алгоритму буде дорівнює O (N3).
    Відкидання повільно ростуть, частин рівняння дозволяє оцінити поведінкуалгоритму при збільшенні розмірності даних завдання N.
    При великих N внесок другій частині в рівняння N3 + N стає все меншепомітним. При N = 100, різниця N3 + N = 1.000.100 і N3 дорівнює всього 100, абоменш ніж 0,01 відсотка. Але це вірно тільки для великих N. При N = 2,різниця між N3 + N = 10 і N3 = 8 дорівнює 2, а це вже 20 відсотків.
    Постійні множники в співвідношенні також ігноруються. Це дозволяє легкооцінити зміни в обчислювальній складності завдання. Алгоритм, часвиконання якого пропорційно 3 * N2, буде мати порядок O (N2). Якщозбільшити N в 2 рази, то час виконання завдання зросте приблизно в 22,тобто в 4 рази.
    Ігнорування постійних множників дозволяє також спростити підрахунок числакроків алгоритму. У попередньому прикладі внутрішній цикл виконується N2 раз,при цьому всередині циклу виконується кілька інструкцій. Можна простопідрахувати кількість інструкцій If, можна підрахувати також інструкції,що виконуються всередині циклу або, крім того, ще й інструкції у зовнішньомуциклі, наприклад оператори Print.
    Обчислювальна складність алгоритму при цьому буде пропорційна N2, 3 * N2або 3 * N2 + N. Оцінка складності алгоритму по порядку величини дасть один і тойж значення O (N3) і відпаде необхідність у точному підрахунку кількостіоператорів.

    Пошук складних частин алгоритму

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

    ============ 4

    Якщо процедура викликає іншу процедуру, необхідно враховувати складністьвикликається процедури. Якщо в ній виконується фіксоване числоінструкцій, наприклад, здійснюється вивід на друк, то при оцінці порядкускладності її можна не враховувати. З іншого боку, якщо в викликаєтьсяпроцедурі виконуєся O (N) кроків, вона може вносити значний вклад ускладність алгоритму. Якщо виклик процедури здійснюється всередині циклу, цейвнесок може бути ще більше.
    Наведемо як приклад програму, яка містить повільну процедуру Slowзі складністю порядку O (N3) і швидку процедуру Fast зі складністю порядку
    O (N2). Складність всієї програми буде залежати від співвідношення між цимидвома процедурами.
    Якщо процедура Slow викликається в кожному циклі процедури Fast, порядкискладності процедур перемножуються. У цьому випадку складність алгоритму дорівнюєтвору O (N2) і O (N3) або O (N3 * N2) = O (N5). Наведемо ілюструє цейвипадок фрагмент коду:

    Sub Slow ()
    Dim I As Integer
    Dim J As Integer
    Dim K As Integer

    For I = 1 To N

    For J = 1 To N

    For K = 1 To N

    'Виконати будь-які дії.

    Next K

    Next J

    Next I
    End Sub

    Sub Fast ()
    Dim I As Integer
    Dim J As Integer
    Dim K As Integer

    For I = 1 To N

    For J = 1 To N

    Slow 'Виклик процедури Slow.

    Next J

    Next I
    End Sub

    Sub MainProgram ()

    Fast
    End Sub

    З іншого боку, якщо процедури, незалежно викликаються з основноїпрограми, їх обчислювальна складність підсумовується. У цьому випадку повнаскладність буде дорівнює O (N3) + O (N2) = O (N3). Таку складність, наприклад, будемати наступний фрагмент коду:

    Sub Slow ()
    Dim I As Integer
    Dim J As Integer
    Dim K As Integer

    For I = 1 To N

    For J = 1 To N

    For K = 1 To N

    'Виконати будь-які дії.

    Next K

    Next J

    Next I
    End Sub

    Sub Fast ()
    Dim I As Integer
    Dim J As Integer

    For I = 1 To N

    For J = 1 To N

    'Виконати будь-які дії.

    Next J

    Next I
    End Sub

    Sub MainProgram ()

    Slow

    Fast
    End Sub


    ============== 5


    Складність рекурсивних алгоритмів

    рекурсивними процедурами (recursive procedure) називаються процедури,викликають самі себе. У багатьох рекурсивних алгоритмах саме ступіньвкладеності рекурсії визначає складність алгоритму, при цьому не завждилегко оцінити порядок складності. Рекурсивна процедура може виглядатипростий, але при цьому вносити великий внесок у складність програми,багаторазово викликаючи саму себе.
    Наступний фрагмент коду містить підпрограму всього з двох операторів. Тимне менше, для заданого N підпрограма виконується N раз, таким чином,обчислювальна складність фрагмента порядку O (N).

    Sub CountDown (N As Integer)

    If N 20 Then

    ArraySize = ArraySize -10

    ReDim Preserve List (1 To ArraySize)

    End If
    End Sub


    ============= 20

    Для дуже великих масивів це рішення може також виявитися не самимкращим. Якщо вам потрібен список, що містить 1000 елементів, до якого зазвичайдодається по 100 елементів, то все ще надто багато часу будевитрачатися на зміну розміру масиву. Очевидною стратегією у цьому випадкубуло б збільшення збільшення розміру масиву з 10 до 100 або більше клітинок.
    Тоді можна було б додавати по 100 елементів одночасно без частогозміни розміру списку.
    Більш гнучким рішенням буде зміна приросту в залежності від розмірумасиву. Для невеликих списків це збільшення було б також невеликим. Хочазміни розміру масиву відбувалися б частіше, вони зажадали бвідносно небагато часу для невеликих масивів. Для великих списків,збільшення розміру буде більше, тому їх розмір буде змінюватися рідше.
    Наст

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status