Экспериментальная проверка работоспособности программной модели

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

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

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

Задача определения оптимального разбора в словарном методе сжатия решена не была.

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

2.3. Оценка эффективности решения задачи, выработка рекомендаций по ее практическому использованию в реальной деятельности ВМУЗ.

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

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

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

2.4. Методические и практические рекомендации по составлению задач динамического программирования

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

1. Основные свойства задач, к которым возможно применить метод динамического программирования:

– задача формулируется относительно многошагового процесса принятия решений, цель задачи – оптимизация последовательности принятия решений;

– задача определена для любого числа шагов, структура решения не должна зависеть от числа шагов;

– определены множество характеристик x, множество управляющих характеристик u, относительно которых задается критерий оптимальности, эти множества неизменны при увеличении числа шагов;

– при выборе любого решения на каком-либо шаге возникает такая же задача по отношению к оставшимся шагам.

2. При подготовке материалов в формате. html можно пользоваться текстовым редактором Microsoft Word или FrontPage. Однако сохранять файлы необходимо с английскими именами и в таких же папках. Например, рисунки к документам, как это сделано в нашем проекте, можно разместить в папке IMG. Несоблюдение этого требования приводит часто (закономерность, когда это происходит, установить не удалось, в документациях феномен не описан) к тому, что при компиляции файлов в проект CHM эти файлы, хоть и подключаются, при просмотре проекта оказываются недоступными.

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

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

Например, для единообразного оформления страниц проекта (надпись вверху страницы «Динамическое программирование», набор ссылок на другие страницы, описание используемых стилей и подпрограмм JavaScript) в настоящем проекте использовался   script main(). Это позволяет в считанные минуты изменить вид всех страниц проекта, внеся изменения в файле JS\ main. js. При этом компилятор ни в одной из страниц не видит то, что генерируется этой программой (Рис. 27), а в оформлении страниц (Рис. 28) имена файлов, выделенные жирным шрифтом, отсутствуют.  

Рис. 27. Автоматически генерируемые ссылки

<title> ... </title>

<meta http-equiv ="content-type"

content ="text/html; charset=windows-1251"

>

<link rel=stylesheet href=" CSS/main.css " type=text/css>

<img src=" IMG/DP.png ">

<a href=" prev. htm ">Предыдущая страница</a>

...

Рис. 28. Оформление заголовка всех страниц

<script src=JS\main.js></script>

<script>

main("Контактная информация","Индекс","Index");

</script>

 

Рис. 29. Содержание фиктивного файла main. htm

<html>

<head>

<meta http-equiv ="content-type"

content ="text/html; charset=windows-1251"

>

<link rel=stylesheet href="CSS/main.css" type=text/css>

<script src="JS/main.js"></script>

</head>

<body>

<img src="IMG/DP.png">

</body>

</html>

 

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

 

Заключение

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

 

Литература

1. Беллман Р. Динамическое программирование. М.: Иностранная литература, 1960.– 400 с.

2. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования.– М.: Наука, 1965.– 458 с.

3. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления.– М.: Наука, 1969.– 118 с.

4. Вентцель Е.С. Исследование операций.– М.: Наука, 1988.

5. Зенкевич Н.А., Губар Е.А. Практикум по исследованию операций: Учебное пособие для обучающихся по специальности «Прикладная математика и информатика».– СПб., 2007. – 170 с.

6. Математическая энциклопедия / Гл. ред. И.М. Виноградов.– М.: Советская энциклопедия, 1979.

Приложение

Рисунок 30. Текст вспомогательных подпрограмм динамического формирования в проекте HTML -страниц (DHTML)

function sText(id,text)

{

document.getElementById(id).innerText = text;

}

function sHTML(id,html)

{

document.getElementById(id).innerHTML = html;

}

 

Рисунок 31. Текст подпрограмм формирования и использования таблиц в задачах бинарного разделения

// Создание таблицы размером n x m

// mode = 1 для задачи кратчайшего пути

// mode = 0 для задачи определения числа путей

 

function nwInit (n, m, mode)

{

var i, j,

t = {"n":n, "m":m, "W":new Array(n+1), "f":new Array(n+1)};

 

for (i = 1; i <= n; i++)

{

t [i] = new Array(m+1); // Данные

t.W [i] = new Array(m+1); // Решение

t.f [i] = new Array(m+1); // Флаг

 

for (j = 1; j <= m; j++)

{

t.f [i][j] = 0;

 

if (mode==0)

{

   t [i][j] = i*10+j;

   t.W[i][j] = (i==1)||(j==1)?1:t.W[i-1][j]+t.W[i][j-1];

}

else

{

   t [i][j] = rInt(8);

   t.W[i][j] = t [i][j] + (i+j==2? 0: i==1? t.W[i][j-1]: j==1? t.W[i-1][j]: Math.max(t.W[i][j-1], t.W[i-1][j]));

}     

}

}

return t;

}

 

// Поиск кратчайшего пути, путь выделяется

// флагами

 

function nwTrack (t,p)

{

var i, j, n = t.n, m = t.m;

 

for (i = 1; i <= n; i++)

for (j = 1; j <= m; j++)

t.f [i][j] = 0;

  

while (p && n >= 1 && m >= 1)

{

t.f [n][m] = 1;

p--;

 

if (n==1) m--; else

if (m==1) n--; else

// Выбор направления с наибольшей суммой

if (t.W[n-1][m]>=t.W[n][m-1])

n--;

else

m--;

}

}

 

// Рисование таблицы в формате HTML

function nwDraw (t,tt,nm)

{

var i, j, ij, s;

s = '<table border="3" cellspacing="0" class="demo" lign=center>';

for (i = 1; i <= t.n; i++)

{

s += '<tr>';

for (j = 1; j <= t.m; j++)

{

ij = i*10+j;

s += (t.f[i][j]==0? '<td>':'<td bgcolor=#F3F3F3>') +

   (

    (ij==nm)? '<font color = red>'+tt[i][j]+'</font>':

    (ij< nm)? tt[i][j]

            : '&nbsp;'

  )+ '</td>';

}

s += '</tr>';

}

return s + '</table>';

} 

 

 

[1] Сам Р. Беллман – математик, поэтому его книги представляют большую ценность для действующих математиков и обучающихся по математическим специальностям.

[2] В общем же случае управление может осуществляться по состоянию u (t, x ).

[3] В некоторых изданиях включена под названием задачи о черепашке.

[4] Левенштейн, Владимир Иосифович, род. в 1935 г., российский математик, известен благодаря введенному в 1965 г. понятию дистанции редактирования. Практическим применением дистанции Левенштейна является определение похожести последовательностей символов, к примеру в коррекции орфографии или при поиске дубликатов.

[5] Чтоб перевести слово Конь в слово Кот необходимо совершить одно удаление и одну замену, соответственно дистанция Левенштейна составляет 2.

[6] Метод используется в эффективных LZ -алгоритмах сжатия в архиваторах RAR (последние версии) и 7 z. В них словарь создается динамически при последовательном просмотре текста. Принципиально словарное сжатие эффективно при передаче формальных текстов по каналам связи для их разгрузки, при этом сами словари могут не передаваться.

[7] В математике игра является не формой досуга, развлечения, отдыха, а любыми целенаправленными действиями в условиях соперничества (антагонистическая игра) или сотрудничества (кооперативная игра). Самые важные области приложения теории игры – военное дело, экономика. Например, игрой являются действия самолета и ракеты, при которых у ракеты цель – попасть в самолет, у самолета – избежать попадания.

[8] http://oszone.net/3789

[9] Из справки помощи программы HTML Help Workshop.

[10] Свободно распространяется на сайте разработчика www.Microsoft.com, инсталляция HtmlHelp. exe занимает 3425 К.

[11] В наше распоряжении была htm2chm-3.0.9.3-en.exe, инсталляция – 729987 байт, английская версия, известно о существовании русского варианта программы.