v Введение

Широкое распространение идей структурного программирования в последние 20-30 лет оказало большое влияние на теорию и практику программирования и привело к пересмотру роли типа и структуры данных при разработке соответствующих алгоритмов и программ. В связи с этим в последние десятилетия при производстве сложных программных систем требуется подго­товка высококвалифицированных специалистов, в совершенстве владеющих современной теорией построения систем обработки данных. В этой теории важное место занимают методы органи­зации и обработки данных. Решение любой задачи сводится к обработке множества данных, которые представляют собой аб­стракцию некоторого фрагмента реального мира.

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

Таким образом, для создания программного продукта, реализующего алгоритм решения задачи данной курсовой работы, нам необходимо обладать знаниями теории структур, методов представле­ния данных на логическом (абстрактном) и физическом (машинном) уровнях, а также эффективных алгоритмов обработки различных структур данных.

Также для того, что бы создать действительно эффективно работающую программу, которая даёт  нужный результат за нужное время следует провести анализ сложности алгоритма по одному из известных методов. Это позволит избежать создания программного продукта, не отвечающего обязательным требованиям по эффективности программ.

Целью этой курсовой работы является создание программной реализации алгоритма, который находит решения геометрической головоломки: Y-пентамино. Игра "Пентамино" - это очень увлекательное и полезное занятие, развивающее множество способностей. Фигурки представляют собой все односвязные комбинации из пяти квадратиков. Всего в одном наборе 12 фигур. Фигурки можно изготовить из бумаги, картона, пластилина, дерева, глины, или из пластмассы, в общем, из чего угодно. Дальше, берём эти фигурки и начинаем собирать прямоугольную область, размером 6х10 квадратиков. Эта задача достаточно сложна для вычислений вручную, но ЭВМ справляется с ней гораздо быстрее. Основные этапы создания программы, включая процесс разработки алгоритма, выбора языка программирования, анализ сложности алгоритма и программы, приведены ниже.

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

Программный продукт, и сама курсовая работа в целом могут быть применены как в научных целях, при анализе быстродействия систем искусственного интеллекта , так и в более широких целях, например, как программа-помощник, встроенная в основную среду-игру «пентамино». Программы такого рода помогают найти решения головоломок, если пользователь не может сделать этого самостоятельно.

v Теоретические сведения, касающиеся метода

При решении задачи, поставленной в курсовой работе, следует применить два основных алгоритмов перебора: алгоритм с возвратами назад(backtracking) и метод проб и ошибок.

-   Алгоритм с возвратами назад:

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