Название: Алгоритмы и программы (Афанасьева Т. В.)

Жанр: Информационные системы и технологии

Просмотров: 1329


1.2. формальное решение задачи

 

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

Наиболее        распространенными и          хорошо            изученными   являются

математические модели. Например, в качестве математической модели звезды можно использовать систему уравнений, описывающую процессы, происходящие в недрах звезды. Математической моделью другого рода являются математические соотношения, позволяющие рассчитать оптимальный план работы предприятия. К основным достоинствам математических моделей относятся хорошо изученные и широко применяемые математические методы решения большого класса задач, что значительно облегчает формирование основной идеи и   выбор методов решения задачи. В дальнейшем в пособии рассматриваются только математические модели.

Приступая      к          разработке      формальной   модели            решения          задачи,

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

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

К основным вопросам, на которые целесообразно обратить внимание на этапе формального решения задачи, следует отнести:

         Что дано? Как можно обозначить исходные данные исходя из их типа, определенного на предыдущем этапе?

         Что  неизвестно?  Как  можно  обозначить  результирующие данные исходя из их типов?

         Какие условия, ограничения можно определить для исходных и результирующих данных? Как их записать?

         Какие    соотношения    между    исходными    данными    и результатами можно записать еще? Как их записать?

         Какая   формальная   модель   больше   всего   подходит   для решения этой задачи?

         Известен  ли  метод  решения  для  такой  или  родственной задачи? Если метод известен,  как его записать в терминах введенных ранее обозначений исходных, результирующих данных и условий? Требуются ли промежуточные данные? К какому типу их следует отнести?

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

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

 

Пример 1. Постановка задачи. Требуется определить пригодность для проведения учебных занятий данной аудитории.

Решение.

Этап 1. Анализ постановки задачи и ее предметной области.

В  результате  анализа  предметной  области,  выявляем,  что  эта  предметная область связана с образовательным процессом. Постановка задачи может быть переформулирована  следующим  образом:  определить,  подходит  ли  некоторая аудитория для проведения занятий группы   учеников при некоторой норме площади для каждого ученика. Введем обозначения для входных и выходных данных. Исходные данные: А – ширина аудитории, B – ее длина, К – количество учеников в группе, N – допустимое минимальное количество квадратных метров для одного ученика (норма), M – количество парт в аудитории. В качестве выходных данных будут выступать сообщения: «Аудитория может быть использована для проведения учебных занятий» и

«Аудитория не может быть использована для проведения учебных занятий».

Этап 2. Формальное решение.

Определим отношения между входными и выходными данными. Введем дополнительные понятия: S – площадь аудитории, C – требуемая по нормам площадь для проведения занятий в группе из К учеников, D – требуемое количество парт для обучения группы из К учеников. Опишем соотношения между входными и выходными данными, используя математические зависимости. Математическая модель:

 

S  A  B

C  N  K ,

 

 

S  C ,

 

 

K  2  D .

 

Задача построения алгоритмов, реализующих выбранные методы решения задачи, детализирует и визуализирует процесс ее решения. Алгоритмизация позволяет определить последовательность преобразования исходных данных в результирующие и уже на этом этапе оценить эффективность решения, уточнить методы решения для различных потоков входных данных и выявить некоторые ошибки. Поэтому особенно важно уделить серьезное внимание алгоритмизации решения заданной задачи. Вопросы корректного построения алгоритмов  являются наиболее значимыми для большого класса вычислительных задач со сложными структурами данных, со сложной логикой и большим объемом вычислительных операций, решаемых программными средствами ЭВМ. В этом случае алгоритмическое представление, алгоритмическая модель решения задачи, созданная на основе метода решения рассматривается как промежуточное звено между методом решения и его программной реализацией. В принципе, желательно понимать, что между   методом решения задачи и реализующим алгоритмом существует отношение «один метод – множество алгоритмов», поэтому необходимо принимать решение о выборе наиболее адекватного, оптимального алгоритма, удовлетворяющего заданным условиям и ограничениям.

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

 

Задания для самостоятельного выполнения

Цель заданий. Приобрести умения в синтезе формальной модели решения   задач.   Сформировать  компетенции   анализа   и   синтеза   при решении простых задач.

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

 

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

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

2. Определите            вариант пути от дома до места учебы, в зависимости от времени выхода из дома и времени начала учебных занятий.

3. В  избирательной  компании  в  органы  власти  участвуют  две  партии: зеленых и прозрачных. Какая информация будет опубликована в СМИ по итогам голосования?

4. Подсчитать количество цифр в целом числе.

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

6. Некоторая    группа    студентов    сдавала    экзамен    по    дисциплине

«Редакторское            дело».  Определить    средний          балл    группы по этой дисциплине.

7. В группе учатся как девушки, так и юноши. Определить, кто лучше сдал экзамен по дисциплине «Информатика» – юноши или девушки?

8. Определить            среднюю        и          общую стоимость       книг    авторов в книжном магазине.

9. Определить    объем    выпуска    книжной    продукции    издательства

«Эдельвейс»   в          печатных        листах,            учитывая        коэффициент  перевода авторских страниц в печатные листы.

10. Определить          общую стоимость       выпуска          книжной         продукции издательства «Прогресс» с учетом цены и тиража.

 

Контрольные вопросы

1. Что понимается под синтезом формальной модели решения задачи?

2. Приведите примеры математических моделей.

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

4. Какие существуют способы поиска метода решения задач?

5. В чем заключается алгоритмизация?

6. Укажите место алгоритмической модели в процессе решения задачи.

7. Приведите пример формальной модели решения задачи.