Реферат: Разработка системы задач (алгоритмы-программы) по дискретной математике
3
5
6
9
4
[4,5]
5
0
3
5
6
7
4
[5]
Время работы алгоритма пропорционально N2 .
Алгоритм Флойда (кратчайшие пути между всеми парами вершин).
Дано. Ориентированный граф G=<V,E>, s - вершина источник; матрица смежности A (A:array[1..n,1..n] of integer); для любых u, v€V вес дуги неотрицательный (А[u,v]>=0). Результат. Матрица D кратчайших расстояний между всеми парами вершин графа и кратчайшие пути.
Идея алгоритма. Обозначим через Dm [i,j] оценку кратчайшего пути из i в j с промежуточными вершинами из множества [1..m]. Тогда имеем: D0 [i,j]:=A[i,j] и D(m+1 ) [i,j]=min{Dm [i,j],Dm [i,m+1]+Dm [m+1,j]}. Второе равенство требует пояснения. Пусть мы находим кратчайший путь из i в j с промежуточными вершинами из множества [1..(m+1)]. Если этот путь не содержит вершину (m+1), то D( m +1) [i,j]=Dm [i,j]. Если же он содержит эту вершину, то его можно разделить на две части от i до (m+1) до j. Время работы алгоритма пропорционально N3 .
Глава 2 Система задач и упражнений.
Классификация задач.
Набор задач, разработанный нами и изложенный ниже можно систематизировать по следующим критериям:
По тематике.
 |
По уровню сложности задачи.
Задачи высокого уровня сложности : это задачи олимпиадного уровня, требующие глубокого знания предмета, а также комплексного подхода к решению задачи (Пример для нашего набора задач, задача о роботах, задача о комнатах музея).
Задачи среднего уровня сложности: это задачи, требующие хороших знаний предмета и навыков применения знаний на практике, т.е в процессе решения задач (Пример: задача о семьях, задача о футболистах, задача про милицию и диспетчера).
Задачи низкого уровня сложности: это задачи, для решения которых необходимы общие знания предмета и не требующие особых навыков применения знаний на практике, т.к. данные задачи направлены на формирование данных навыков.
 |
Ситуативные задачи: это задачи, формулировка которых представляет собой ситуацию из жизни. Это необходимо для более наглядного представления задачи, а также для того, чтобы сделать задачу более интересной для решения.
Задачи со строгой формулировкой: это задачи, в формулировке которой строго изложена суть задачи. Данные задачи являются задачами более низкого уровня, так как в них не требуется определения тематики задачи, а следовательно, и выбора способа решения, требуется лишь реализация алгоритма на языке программирования.
Задачи с единственным способом решения: это задачи, решить которые можно лишь одним способом, т.е. задачу нельзя рассмотреть с точки зрения различных тематик, таким образом, отсутствует выбор способа решения задачи (Пример: задача о футболистах и т.д.).
Задачи с несколькими способами решения: это задачи, которые могут быть рассмотрены с точки зрения различных тематик и, таким образом, имеют более широкий спектр решений (Пример: задача о метрополитене и т.д.).
 |