Докторская диссертация на тему: Можно ли её решить полным перебором

Введение

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

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

Конечно, описанная ниже модель, ни в коем случае не претендует на полноту и точность, это всего лишь (я надеюсь удачный) демонстрационный пример.

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

Конечно, это целый класс задач, но мы далее будем говорить только об одном представителе этого класса - задаче составления расписания учебных занятий. Однако этот представитель очень ярок и нам его будет достаточно.

Оглавление

- Введение

- О характере задачи

- Можно ли её решить полным перебором

- Множество D

- Прогноз тупика Заключение

- Литература

Заключение

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

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

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

Общую идею, выходя из тупика даёт построенный выше ориентированный граф. Если мы зашли в тупик, то необходимо сделать несколько шагов в обратном направлении, против направления стрелок.

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

Список литературы

1. Вострикова З.П. и др. "Программирование на языке "БЕЙСИК" для персональных ЭВМ". Машиностроение, 1993г.

2. Гохман А.В. и др. "Сборник задач по математической логике и алгебры множеств", издательство Саратовского Университета, 1969г.

3. Гусев В.В. Основы импульсной техники.М. Советское радио, 1975

4. Касаткин В.Н. "Информация, алгоритмы, ЭВМ", М. Просвещение, 1991г.

5. Машовцев В.А. Вступительные экзамены по информатике // Информатика. 1997, №13

6. Орлов В.А. О вступительных экзаменах по информатике // Информатика, 1997, №15

7. Яснева Г.Г. Логические основы ЭВМ // Информатика и образование, 1998, №2

8. Лыскова В.Ю., Ракитина Е.А. Логика в информатике, М. Информатика и образование 1999

9. Шауцкова Л.З. "Решение логических задач средствами алгебры логики", газета Информатика 1999, №5.