ЗМІСТ
Технічне завдання на розробку ПС
. Теоретична частина
. 1 Відомості про алгоритми
. 2 Відомості про гру «п'ятнашки»
. Функціональне опис
Висновок
Список використаних джерел
Додаток А
Додаток Б
Технічне завдання на розробку ПС
Розробити програму, що дозволяє реалізувати на комп'ютері гру «п'ятнашки».
1. Теоретична частина
1.1 Відомості про алгоритми
алгоритми? тм, від імені вченого аль-Хорезмі (перс. ???????? [al-Khw? razm?]) - точний набір інструкцій, що описують порядок дій виконавця для досягнення результату рішення задачі за кінцевий час. У старій трактуванні замість слова «порядок» використовувалося слово «послідовність», але в міру розвитку паралельності в роботі комп'ютерів слово «послідовність» стали замінювати більш загальним словом «порядок». Це пов'язано з тим, що робота якихось інструкцій алгоритму може бути залежна від інших інструкцій або результатів їх роботи. Таким чином, деякі інструкції повинні виконуватися строго після завершення роботи інструкцій, від яких вони залежать. Незалежні інструкції або інструкції, що стали незалежними через завершення роботи інструкцій, від яких вони залежать, можуть виконуватися в довільному порядку, паралельно або одночасно, якщо це дозволяють використовувані процесор і операційна система.
Раніше часто писали «алгорифм», зараз таке написання використовується рідко, але, тим не менш, має місце (наприклад, Нормальний алгорифм Маркова).
Часто в якості виконавця виступає деякий механізм (комп'ютер, токарний верстат, швейна машина), але поняття алгоритму необов'язково відноситься до комп'ютерних програм, так, наприклад, чітко описаний рецепт приготування страви також є алгоритмом, в такому випадку виконавцем є людина.
Поняття алгоритму відноситься до первинних, основним, базисним поняттям математики. Обчислювальні процеси алгоритмічного характеру (арифметичні дії над цілими числами, знаходження найбільшого загального дільника двох чисел і т. Д.) Відомі людству з глибокої давнини. Однак, в явному вигляді поняття алгоритму сформувалося лише на початку XX століття.
Часткова формалізація поняття алгоритму почалася зі спроб вирішення проблеми дозволу (нім. Entscheidungsproblem), яку сформулював Давид Гільберт в 1928 році. Наступні етапи формалізації були необхідні для визначення ефективних обчислень або «ефективного методу»; серед таких формалізацій - рекурсивні функції Геделя - Ербрана - Кліні +1930, 1934 і 1935 рр.,?-ісчісленіе Алонзо Черча 1936 р «Формулювання 1» Еміля Посту 1936 року і машина Тьюринга. У методології алгоритм є базисним поняттям і отримує якісно нове поняття як оптимальності в міру наближення до прогнозованого абсолюту. У сучасному світі алгоритм у формалізованому виразі складає основу освіти на прикладах, за подобою. На основі подібності алгоритмів різних сфер діяльності була сформована концепція (теорія) експертних систем.
Неформальне визначення
Кожен алгоритм припускає існування початкових (вхідних) даних і в результаті роботи призводить до отримання певного результату. Робота кожного алгоритму відбувається шляхом виконання послідовності деяких елементарних дій. Ці дії називають кроками, а процес їх виконання називають алгоритмічним процесом. Таким чином виявляється властивість дискретності алгоритму. Важливою властивістю алгоритмів є масовість, або можливість застосування до різних вхідним даним. Тобто, кожен алгоритм покликаний вирішувати клас однотипних завдань. Необхідною умовою, якому задовольняє алгоритм, є детермінованість, або визначеність. Це означає, що виконання команд алгоритму відбувається за єдиним зразком та призводить до однакового результату для однакових вхідних даних. Вхідні дані алгоритму можуть бути обмежені набором допустимих вхідних даних. Застосування алгоритму до неприпустимих вхідним даним може призводити до того, що алгоритм ніколи не зупиниться або потрапить в тупиковий стан (зависання), з якого не зможе вийти.
Формальне визначення
Різноманітні теоретичні проблеми математики і прискорення розвитку фізики і техніки поставили на порядок денний точне визначення поняття алгоритму. Перші спроби уточнення поняття алгоритму і його дослідження здійснювали в першій половині XX століття Алан Тьюринг, Еміль Пост, Жак Ербран, Курт Гедель, Андрій Марков, Алонзо Черч. Було розроблено кілька визначень поняття алгоритму, але згодом було з'ясовано, що всі вони ви...
