значають одне і те ж поняття (див. Теза Черча - Тьюринга).
Формальні властивості алгоритмів
Різні визначення алгоритму в явній або неявній формі містять наступний ряд загальних вимог:
Дискретність - алгоритм повинен представляти процес вирішення завдання як послідовне виконання деяких простих кроків. При цьому для виконання кожного кроку алгоритму потрібно кінцевий відрізок часу, тобто перетворення вихідних даних у результат здійснюється в часі дискретно.
Детермінованість (визначеність) - в кожен момент часу наступний крок роботи однозначно визначається станом системи. Таким чином, алгоритм видає один і той же результат (відповідь) для одних і тих же вихідних даних. У сучасному трактуванні у різних реалізацій одного і того ж алгоритму має бути ізоморфний граф. З іншого боку, існують імовірнісні алгоритми, в яких наступний крок роботи залежить від поточного стану системи і генерується випадкового числа. Однак при включенні методу генерації випадкових чисел в список «вихідних даних», імовірнісний алгоритм стає підвидом звичайного.
Зрозумілість - алгоритм для виконавця повинен включати тільки ті команди, які йому (виконавцю) доступні, які входять в його систему команд.
завершаемості (кінцівка) - при коректно заданих вихідних даних алгоритм повинен завершувати роботу і видавати результат за кінцеве число кроків. З іншого боку, імовірнісний алгоритм може і ніколи не видати результат, але ймовірність цього дорівнює 0.
Масовість (універсальність) - алгоритм повинен бути застосовний до різних наборам вихідних даних.
Результативність - завершення алгоритму певними результатами.
Алгоритм містить помилки, якщо призводить до отримання неправильних результатів або не дає результатів зовсім.
Алгоритм не містить помилок, якщо він дає правильні результати для будь-яких допустимих вихідних даних.
Наявність вихідних даних і деякого результату
Алгоритм - це точно певна інструкція, послідовно застосовуючи яку до вихідних даних, можна отримати рішення задачі. Для кожного алгоритму є деяке безліч об'єктів, допустимих в якості вихідних даних. Наприклад, в алгоритмі ділення дійсних чисел ділене може бути будь-яким, а дільник не може бути дорівнює нулю. Алгоритм служить, як правило, для вирішення не однієї конкретної задачі, а деякого класу задач. Так, алгоритм складання застосуємо до будь-якій парі натуральних чисел. У цьому виражається його властивість масовості, тобто можливості застосовувати багаторазово один і той же алгоритм для любої задачі одного класу. Для розробки алгоритмів і програм використовується алгоритмізація - процес систематичного складання алгоритмів для вирішення поставлених прикладних завдань. Алгоритмізація вважається обов'язковим етапом у процесі розробки програм та вирішенні задач на ЕОМ. Саме для прикладних алгоритмів і програм принципово важливі детермінованість, результативність і масовість, а також правильність результатів вирішення поставлених завдань. Алгоритм - це зрозуміле і точне розпорядження, виконавчо здійснити послідовність дій, спрямованих на досягнення мети.
1.2 Відомості про гру «п'ятнашки»
Плями? шки - популярна головоломка, придумана в 1878 році Ноєм Чепмен. Являє собою набір однакових квадратних кісточок з нанесеними числами, ув'язнених у квадратну коробку. Довжина сторони коробки в чотири рази більше довжини сторони костяшек для набору з 15 елементів, відповідно в коробці залишається незаповненим одне квадратне поле. Мета гри - переміщаючи кісточки по коробці домогтися упорядкування їх за номерами, бажано зробивши якомога менше переміщень.
Суть самої гри полягає в наступному:
- Гравець на екрані бачить табло, яке розбите на 16 клітин. У п'ятнадцяти з них розташовані неповторювані цифри, у випадковому порядку від 1 до 15 і одна порожня.
У загальному вигляді дане табло можна представити у вигляді таблиці 1:
Таблиця 1 - Зразок
+286134951211141571013
Гравець повинен переміщати по однієї клітини з цифрою на порожнє місце.
- Так відбувається до тих пір, поки користувач не вибудує послідовну комбінацію цифр (Таблиця 2), і лише після цього гравець вважається переможцем.
Таблиця 2 - Правильне заповнення табло
+123456789101112131415
Математичний опис.
П'ятнашки являють собою класичну задачу для моделювання евристичних алгоритмів. Зазвичай завдання вирішують через кількість переміщень і пошук Манхеттенського відст...
