Page 5 - 4570

4

ВСТУП

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

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