Алговики - Вклад [ru]

Участник:Zerika

2025-12-09T21:11:13Z

Zerika: /* 2.4 Выводы для классов архитектур */

'''Седловой элемент матрицы''' <math> A = (a_{i, j})_{i = 1, j = 1}^{m, n}</math> — элемент матрицы <math>a_{k, d}</math>, удовлетворяющий условиям <math>a_{k, d} = \max_{1 \le i \le m} a_{i, d} = \min_{1 \le j \le n} a_{k, j}</math>, то есть элемент матрицы, который одновременно является минимальным элементом в соответствующей строке матрицы и максимальным элементом в соответствующем столбце матрицы. Из определения следует, что <math>a_{k, d} = \max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j}</math>. Более того, для матрицы существует седловой элемент тогда и только тогда, когда <math>\max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j}</math>.
'''Примеры'''
 
Матрица
: <math>\begin{bmatrix}
5 & 6 & 4 & 5\\
-2 & 5 & 3 & 7\\
8 & 7 & -2 & 6\\
\end{bmatrix}
</math>
имеет 1 седловой элемент, равный 4, который расположен в первой строке в третьем столбце матрицы, так как он одновременно является минимальным элементом в соответствующей строке матрицы (в данном случае в первой строке матрицы) и максимальным элементом в соответствующем столбце матрицы (в данном случае в третьем столбце матрицы).

Матрица
: <math>\begin{bmatrix}
2 & 3 & 5 & 2\\
2 & 4 & 6 & 2\\
-2 & 7 & 2 & 0\\
\end{bmatrix}
</math>
имеет 4 седловых элемента, равных 2, которые расположены в первой строке в первом столбце, в первой строке в четвёртом столбце, во второй строке в первом столбце, во второй строке в четвёртом столбце матрицы, соответственно.

Данный пример показывает, что матрица может иметь несколько (более одной) седловых точек.
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для поиска седловой точки в числовой матрице A. Седловой точкой называется элемент матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце. Алгоритм является прямым (не итерационным) и детерминированным. Его суть заключается в последовательном сканировании строк матрицы для поиска минимумов, а затем в проверке этих кандидатов на максимальность в соответствующих столбцах. В матрице может быть несколько седловых точек или не быть ни одной.

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

=== Математическое описание ===
Пусть задана матрица '''A''' размерности '''m x n''' (m строк, n столбцов).

Элемент '''Aij''' является седловой точкой, если выполняются два условия:

Он является минимальным элементом в своей строке i:

'''Aij = min Aik, k от 1 до n'''

Он является максимальным элементом в своем столбце j:

'''Aij = max Adj, d от 1 до m'''

Алгоритм можно описать как поиск таких индексов (i, j), для которых:

'''∀k: Aij ≤ Aik и ∀d: Aij ≥ Adj'''
=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит из двух последовательных этапов:

Поиск минимумов в строках, в котором для каждой строки i матрицы A последовательно сравниваются элементы Aij с текущим минимумом, и при нахождении меньшего значения обновляются минимальный элемент и его позиция столбец (d).

Проверка кандидатов в столбцах d, в котором для каждого найденного минимума строки последовательно сравниваются элементы Aid соответствующего столбца с кандидатом, и при обнаружении большего элемента проверка прекращается.
=== Макроструктура алгоритма ===
Алгоритм состоит из двух последовательных макроопераций:

1. Поиск минимума в каждой строке матрицы. Эта операция представляет собой цикл по всем строкам, внутри которого выполняется сканирование элементов строки.

2. Проверка найденных кандидатов на максимальность в их столбцах. Эта операция представляет собой цикл по всем строкам-кандидатам, внутри которого для каждого кандидата выполняется полный проход по его столбцу.

=== Схема реализации последовательного алгоритма ===
Для каждой строки i:

# Найти индекс позиции j минимального элемента строки.
# Проверить, является ли Ai,j максимальным в столбце j.
# Если да — вернуть (i,j) как седловую точку.
# Если ни для одной строки условие не выполнено — сообщить об отсутствии седловой точки.

=== Последовательная сложность алгоритма ===
Для матрицы размером '''m×n'''
 Поиск минимума в строке занимает — '''O(n)'''
 
Проверка максимума в столбце — '''O(m)'''
 
Итого на каждую строку — '''O(m+n)'''
 
Общая сложность — '''O(m(m+n))''', что при квадратной матрице '''n = m''' равно '''O(n^2)'''

=== Информационный граф ===
Информационный граф отражает две основные операции над каждой строкой: поиск минимума и проверку максимума в столбце. Между итерациями отсутствуют зависимости, параллелизм возможен по строкам.

Граф относительно прост и состоит из двух последовательных уровней вычислений для каждой строки.

* Уровень 1 (Поиск минимумов): m независимых вершин (по одной на каждую строку), каждая из которых выполняет операцию нахождения минимума в своем наборе данных (элементах строки) и номер его столбца d. Эти вершины не связаны между собой.

* Уровень 2 (Проверка кандидатов): m вершин (по одной на каждого кандидата). Каждая вершина i на этом уровне использует результат вершины i с первого уровня (столбец-кандидат) и требует данные всего столбца d из исходной матрицы для проверки на максимум. Вершины этого уровня также независимы друг от друга.

Связь между уровнями: Результат работы вершины i Уровня 1 (значение d) является входным данным для вершины i Уровня 2.

[[Файл: Graf sedl.png |500px|thumb|center|Граф поиска седловой точки матрицы]]

=== Ресурс параллелизма алгоритма ===
* Параллелизм на макроуровне (между строками): Поиск минимумов в строках может выполняться полностью параллельно. Все m задач Уровня 1 независимы. Аналогично, проверка всех m кандидатов на Уровне 2 также может выполняться параллельно.
* Параллельная сложность:
# При наличии m процессоров поиск минимумов во всех строках можно выполнить за O(n) времени (время обработки одной строки).
# Проверку всех кандидатов на наличие максимума в столбцах, при наличии m процессоров, можно выполнить за O(m) времени (время прохода по одному столбцу). Таким образом, общая параллельная сложность составляет O(n + m).
#Параллелизм реализуется на уровне итераций по строкам — независимые проверки каждой строки и связанных с ними операций.
Для матрицы большого размера этот подход позволяет ускорить алгоритм на многопроцессорных системах.
=== Входные и выходные данные алгоритма ===
'''Входные данные:''' Прямоугольная числовая матрица A размером m x n. Тип элементов - целый или вещественный. Особых свойств от матрицы не требуется.

'''Выходные данные:''' Координаты найденных седловых точек (i, j) или индикатор ее отсутствия (например, None).

=== Свойства алгоритма ===
* В матрице может быть несколько седловых точек или ни одной
* Алгоритм устойчив к дублирующимся значениям

== ''' Программная реализация алгоритма''' ==
=== 2.1 Особенности реализации последовательного алгоритма ===
def find_all_saddle_points_optimized(matrix):

if not matrix or not matrix[0]:
return []

m = len(matrix) # количество строк
n = len(matrix[0]) # количество столбцов

saddle_points = []

for i in range(m):
# Шаг 1: Находим все индексы минимальных элементов в строке i
min_in_row = matrix[i][0]
min_indices = [0]

for j in range(1, n):
if matrix[i][j] < min_in_row:
min_in_row = matrix[i][j]
min_indices = [j]
elif matrix[i][j] == min_in_row:
min_indices.append(j)

# Шаг 2: Для каждого минимального элемента проверяем,
# является ли он максимальным в своем столбце
for j in min_indices:
is_saddle = True
for k in range(m):
if matrix[k][j] > matrix[i][j]:
is_saddle = False
break

if is_saddle:
saddle_points.append({
'row': i,
'col': j,
'value': matrix[i][j]
})

return saddle_points

=== 2.2 Возможные способы и особенности параллельной реализации алгоритма===
def find_all_saddle_points_parallel(matrix):
if not matrix or not matrix[0]:
return []

m = len(matrix)
n = len(matrix[0])

def process_row(i):
"""
Обработка одной строки для поиска ВСЕХ потенциальных седловых точек
"""
row_results = []

# Находим все минимальные элементы в строке
min_in_row = matrix[i][0]
min_indices = [0]

for j in range(1, n):
if matrix[i][j] < min_in_row:
min_in_row = matrix[i][j]
min_indices = [j]
elif matrix[i][j] == min_in_row:
min_indices.append(j)

# Для каждого минимального элемента проверяем условие
for j in min_indices:
is_saddle = True
for k in range(m):
if matrix[k][j] > matrix[i][j]:
is_saddle = False
break

if is_saddle:
row_results.append((i, j, matrix[i][j]))

return row_results

# Параллельная обработка строк
saddle_points = []
with concurrent.futures.ThreadPoolExecutor(max_workers=min(m, 4)) as executor:
futures = [executor.submit(process_row, i) for i in range(m)]

# Собираем все результаты
for future in concurrent.futures.as_completed(futures):
row_results = future.result()
for result in row_results:
saddle_points.append({
'row': result[0],
'col': result[1],
'value': result[2]
})

return saddle_points

=== 2.3 Результаты прогонов ===
Для всех запусков седловая точка не была найдена (No saddle point found). Значения времени усреднены по трём прогонам. Время показано в секундах.

{| class="wikitable"

! Размер матрицы !! 1 процесс !! 2 процесса !! 4 процесса !! 8 процессов !! 16 процессов !! 32 процесса !! 64 процесса
|-
|1000x1000 || 0.000358 || 0.000233 || 0.000156 ||0.000079 || 0.000064 || 0.000038 || 0.000015
|-
|2000x2000 || 0.001373 || 0.000926 || 0.000701 || 0.000536 || 0.000273 || 0.000090 || 0.000042
|-
|3000x3000 || 0.003451 || 0.002439 || 0.001691 || 0.001200 || 0.000617 || 0.000166 || 0.000085
|-
|4000x4000 || 0.007259 || 0.003992 || 0.002923 || 0.001972 || 0.001029 || 0.000298 || 0.000135
|-
|5000x5000 || 0.011327 || 0.006031 || 0.004380 || 0.002532 || 0.001452 || 0.000439 || 0.000236
|-
|6000x6000 || 0.016217 || 0.008659 || 0.007147 || 0.003346 || 0.002009 || 0.000606 || 0.000326
|-
|7000x7000 || 0.022054 || 0.011617 || 0.008796 || 0.004212 || 0.002220 || 0.000914 || 0.000399
|-
|8000x8000 || 0.028572 || 0.015224 || 0.009939 || 0.005330 || 0.002697 || 0.001254 || 0.000534
|-
|9000x9000 || 0.035642 || 0.019085 || 0.012258 || 0.006447 || 0.003769 || 0.001428 || 0.000769
|-
|10000x10000 || 0.043867 || 0.023461 || 0.012777 || 0.007889 || 0.004756 || 0.002258 || 0.000792
|-
|11000x11000 || 0.052932 || 0.028309 || 0.018155 || 0.009360 || 0.005155 || 0.002243 || 0.001000
|}

=== 2.4 Выводы для классов архитектур ===
'''Сильные стороны для данного алгоритма:'''

* Высокая эффективность для больших матриц

* Минимальные накладные расходы на передачу данных (матрица в общей памяти)

* Простота реализации

'''Ограничения:'''

* Масштабируемость ограничена пропускной способностью памяти

* Эффективность падает для маленьких задач (37.3% для 1000×1000 на 64 ядрах)

* Конкуренция за доступ к памяти при проверке столбцов

'''Рекомендации:'''

* Использовать для матриц размером ≥5000×5000

=== 2.5 Код на MPI ===
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include <time.h>

typedef struct {
int row;
int col;
} SaddlePoint;

int main(int argc, char* argv[])
{
int rank, size;
int m, n;
int i, j;

MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);

if (argc != 3) {
if (rank == 0) {
fprintf(stderr, "Usage: %s <rows> <cols>\n", argv[0]);
}
MPI_Finalize();
return 1;
}

m = atoi(argv[1]);
n = atoi(argv[2]);

if (m <= 0 || n <= 0) {
if (rank == 0) {
fprintf(stderr, "Matrix dimensions must be positive.\n");
}
MPI_Finalize();
return 1;
}

/* Каждый процесс выделяет память под всю матрицу */
int* A = (int*)malloc(m * n * sizeof(int));
if (A == NULL) {
if (rank == 0) fprintf(stderr, "Memory allocation failed.\n");
MPI_Abort(MPI_COMM_WORLD, 1);
}

/* Процесс 0 генерирует матрицу */
if (rank == 0) {
srand((unsigned int)time(NULL));
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
A[i * n + j] = rand() % 1000;
}
}
}

/* Рассылаем всю матрицу всем процессам */
MPI_Bcast(A, m * n, MPI_INT, 0, MPI_COMM_WORLD);

/* === НАЧАЛО ЗАМЕРА ВРЕМЕНИ === */
MPI_Barrier(MPI_COMM_WORLD);
double t1 = MPI_Wtime();

/* Каждый процесс обрабатывает строки: i % size == rank */
int max_local = (m + size - 1) / size; /* верхняя оценка числа строк на процесс */
SaddlePoint* local_saddles = (SaddlePoint*)malloc(max_local * sizeof(SaddlePoint));
int local_count = 0;

for (i = rank; i < m; i += size) {
/* Уровень 1: найти минимум в строке i */
int min_val = A[i * n + 0];
int min_j = 0;
for (j = 1; j < n; j++) {
if (A[i * n + j] < min_val) {
min_val = A[i * n + j];
min_j = j;
}
}

/* Уровень 2: проверить максимум в столбце min_j */
int is_max = 1;
for (j = 0; j < m; j++) {
if (A[j * n + min_j] > min_val) {
is_max = 0;
break;
}
}

if (is_max) {
local_saddles[local_count].row = i;
local_saddles[local_count].col = min_j;
local_count++;
}
}

double t2 = MPI_Wtime();

/* Собрать результаты */
int* all_counts = NULL;
int total_saddles = 0;

if (rank == 0) {
all_counts = (int*)malloc(size * sizeof(int));
}

MPI_Gather(&local_count, 1, MPI_INT, all_counts, 1, MPI_INT, 0, MPI_COMM_WORLD);

if (rank == 0) {
for (i = 0; i < size; i++) {
total_saddles += all_counts[i];
}
}

SaddlePoint* global_saddles = NULL;
int* displs = NULL;

if (rank == 0) {
global_saddles = (SaddlePoint*)malloc(total_saddles * sizeof(SaddlePoint));
displs = (int*)malloc(size * sizeof(int));
displs[0] = 0;
for (i = 1; i < size; i++) {
displs[i] = displs[i - 1] + all_counts[i - 1];
}
}

MPI_Gatherv(
local_saddles, local_count, MPI_BYTE,
global_saddles, all_counts, displs, MPI_BYTE,
0, MPI_COMM_WORLD
);

/* Вывод */
if (rank == 0) {
FILE* fout = fopen("result.out", "a");
if (fout) {
fprintf(fout, "%d %d %.6f\n", m, size, t2 - t1);
fclose(fout);
}

if (total_saddles == 0) {
printf("No saddle point found.\n");
} else {
printf("Found %d saddle point(s):\n", total_saddles);
for (i = 0; i < total_saddles; i++) {
printf(" (%d, %d)\n", global_saddles[i].row, global_saddles[i].col);
}
}
printf("Matrix: %dx%d, Processes: %d, Time: %.6f seconds\n", m, n, size, t2 - t1);

free(all_counts);
free(displs);
free(global_saddles);
}

free(local_saddles);
free(A);
MPI_Finalize();
return 0;
}

== ''' Литература''' ==

Участник:Zerika

2025-12-09T21:06:58Z

Zerika: /* 2.5 Код на MPI */

'''Седловой элемент матрицы''' <math> A = (a_{i, j})_{i = 1, j = 1}^{m, n}</math> — элемент матрицы <math>a_{k, d}</math>, удовлетворяющий условиям <math>a_{k, d} = \max_{1 \le i \le m} a_{i, d} = \min_{1 \le j \le n} a_{k, j}</math>, то есть элемент матрицы, который одновременно является минимальным элементом в соответствующей строке матрицы и максимальным элементом в соответствующем столбце матрицы. Из определения следует, что <math>a_{k, d} = \max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j}</math>. Более того, для матрицы существует седловой элемент тогда и только тогда, когда <math>\max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j}</math>.
'''Примеры'''
 
Матрица
: <math>\begin{bmatrix}
5 & 6 & 4 & 5\\
-2 & 5 & 3 & 7\\
8 & 7 & -2 & 6\\
\end{bmatrix}
</math>
имеет 1 седловой элемент, равный 4, который расположен в первой строке в третьем столбце матрицы, так как он одновременно является минимальным элементом в соответствующей строке матрицы (в данном случае в первой строке матрицы) и максимальным элементом в соответствующем столбце матрицы (в данном случае в третьем столбце матрицы).

Матрица
: <math>\begin{bmatrix}
2 & 3 & 5 & 2\\
2 & 4 & 6 & 2\\
-2 & 7 & 2 & 0\\
\end{bmatrix}
</math>
имеет 4 седловых элемента, равных 2, которые расположены в первой строке в первом столбце, в первой строке в четвёртом столбце, во второй строке в первом столбце, во второй строке в четвёртом столбце матрицы, соответственно.

Данный пример показывает, что матрица может иметь несколько (более одной) седловых точек.
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для поиска седловой точки в числовой матрице A. Седловой точкой называется элемент матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце. Алгоритм является прямым (не итерационным) и детерминированным. Его суть заключается в последовательном сканировании строк матрицы для поиска минимумов, а затем в проверке этих кандидатов на максимальность в соответствующих столбцах. В матрице может быть несколько седловых точек или не быть ни одной.

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

=== Математическое описание ===
Пусть задана матрица '''A''' размерности '''m x n''' (m строк, n столбцов).

Элемент '''Aij''' является седловой точкой, если выполняются два условия:

Он является минимальным элементом в своей строке i:

'''Aij = min Aik, k от 1 до n'''

Он является максимальным элементом в своем столбце j:

'''Aij = max Adj, d от 1 до m'''

Алгоритм можно описать как поиск таких индексов (i, j), для которых:

'''∀k: Aij ≤ Aik и ∀d: Aij ≥ Adj'''
=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит из двух последовательных этапов:

Поиск минимумов в строках, в котором для каждой строки i матрицы A последовательно сравниваются элементы Aij с текущим минимумом, и при нахождении меньшего значения обновляются минимальный элемент и его позиция столбец (d).

Проверка кандидатов в столбцах d, в котором для каждого найденного минимума строки последовательно сравниваются элементы Aid соответствующего столбца с кандидатом, и при обнаружении большего элемента проверка прекращается.
=== Макроструктура алгоритма ===
Алгоритм состоит из двух последовательных макроопераций:

1. Поиск минимума в каждой строке матрицы. Эта операция представляет собой цикл по всем строкам, внутри которого выполняется сканирование элементов строки.

2. Проверка найденных кандидатов на максимальность в их столбцах. Эта операция представляет собой цикл по всем строкам-кандидатам, внутри которого для каждого кандидата выполняется полный проход по его столбцу.

=== Схема реализации последовательного алгоритма ===
Для каждой строки i:

# Найти индекс позиции j минимального элемента строки.
# Проверить, является ли Ai,j максимальным в столбце j.
# Если да — вернуть (i,j) как седловую точку.
# Если ни для одной строки условие не выполнено — сообщить об отсутствии седловой точки.

=== Последовательная сложность алгоритма ===
Для матрицы размером '''m×n'''
 Поиск минимума в строке занимает — '''O(n)'''
 
Проверка максимума в столбце — '''O(m)'''
 
Итого на каждую строку — '''O(m+n)'''
 
Общая сложность — '''O(m(m+n))''', что при квадратной матрице '''n = m''' равно '''O(n^2)'''

=== Информационный граф ===
Информационный граф отражает две основные операции над каждой строкой: поиск минимума и проверку максимума в столбце. Между итерациями отсутствуют зависимости, параллелизм возможен по строкам.

Граф относительно прост и состоит из двух последовательных уровней вычислений для каждой строки.

* Уровень 1 (Поиск минимумов): m независимых вершин (по одной на каждую строку), каждая из которых выполняет операцию нахождения минимума в своем наборе данных (элементах строки) и номер его столбца d. Эти вершины не связаны между собой.

* Уровень 2 (Проверка кандидатов): m вершин (по одной на каждого кандидата). Каждая вершина i на этом уровне использует результат вершины i с первого уровня (столбец-кандидат) и требует данные всего столбца d из исходной матрицы для проверки на максимум. Вершины этого уровня также независимы друг от друга.

Связь между уровнями: Результат работы вершины i Уровня 1 (значение d) является входным данным для вершины i Уровня 2.

[[Файл: Graf sedl.png |500px|thumb|center|Граф поиска седловой точки матрицы]]

=== Ресурс параллелизма алгоритма ===
* Параллелизм на макроуровне (между строками): Поиск минимумов в строках может выполняться полностью параллельно. Все m задач Уровня 1 независимы. Аналогично, проверка всех m кандидатов на Уровне 2 также может выполняться параллельно.
* Параллельная сложность:
# При наличии m процессоров поиск минимумов во всех строках можно выполнить за O(n) времени (время обработки одной строки).
# Проверку всех кандидатов на наличие максимума в столбцах, при наличии m процессоров, можно выполнить за O(m) времени (время прохода по одному столбцу). Таким образом, общая параллельная сложность составляет O(n + m).
#Параллелизм реализуется на уровне итераций по строкам — независимые проверки каждой строки и связанных с ними операций.
Для матрицы большого размера этот подход позволяет ускорить алгоритм на многопроцессорных системах.
=== Входные и выходные данные алгоритма ===
'''Входные данные:''' Прямоугольная числовая матрица A размером m x n. Тип элементов - целый или вещественный. Особых свойств от матрицы не требуется.

'''Выходные данные:''' Координаты найденных седловых точек (i, j) или индикатор ее отсутствия (например, None).

=== Свойства алгоритма ===
* В матрице может быть несколько седловых точек или ни одной
* Алгоритм устойчив к дублирующимся значениям

== ''' Программная реализация алгоритма''' ==
=== 2.1 Особенности реализации последовательного алгоритма ===
def find_all_saddle_points_optimized(matrix):

if not matrix or not matrix[0]:
return []

m = len(matrix) # количество строк
n = len(matrix[0]) # количество столбцов

saddle_points = []

for i in range(m):
# Шаг 1: Находим все индексы минимальных элементов в строке i
min_in_row = matrix[i][0]
min_indices = [0]

for j in range(1, n):
if matrix[i][j] < min_in_row:
min_in_row = matrix[i][j]
min_indices = [j]
elif matrix[i][j] == min_in_row:
min_indices.append(j)

# Шаг 2: Для каждого минимального элемента проверяем,
# является ли он максимальным в своем столбце
for j in min_indices:
is_saddle = True
for k in range(m):
if matrix[k][j] > matrix[i][j]:
is_saddle = False
break

if is_saddle:
saddle_points.append({
'row': i,
'col': j,
'value': matrix[i][j]
})

return saddle_points

=== 2.2 Возможные способы и особенности параллельной реализации алгоритма===
def find_all_saddle_points_parallel(matrix):
if not matrix or not matrix[0]:
return []

m = len(matrix)
n = len(matrix[0])

def process_row(i):
"""
Обработка одной строки для поиска ВСЕХ потенциальных седловых точек
"""
row_results = []

# Находим все минимальные элементы в строке
min_in_row = matrix[i][0]
min_indices = [0]

for j in range(1, n):
if matrix[i][j] < min_in_row:
min_in_row = matrix[i][j]
min_indices = [j]
elif matrix[i][j] == min_in_row:
min_indices.append(j)

# Для каждого минимального элемента проверяем условие
for j in min_indices:
is_saddle = True
for k in range(m):
if matrix[k][j] > matrix[i][j]:
is_saddle = False
break

if is_saddle:
row_results.append((i, j, matrix[i][j]))

return row_results

# Параллельная обработка строк
saddle_points = []
with concurrent.futures.ThreadPoolExecutor(max_workers=min(m, 4)) as executor:
futures = [executor.submit(process_row, i) for i in range(m)]

# Собираем все результаты
for future in concurrent.futures.as_completed(futures):
row_results = future.result()
for result in row_results:
saddle_points.append({
'row': result[0],
'col': result[1],
'value': result[2]
})

return saddle_points

=== 2.3 Результаты прогонов ===
Для всех запусков седловая точка не была найдена (No saddle point found). Значения времени усреднены по трём прогонам. Время показано в секундах.

{| class="wikitable"

! Размер матрицы !! 1 процесс !! 2 процесса !! 4 процесса !! 8 процессов !! 16 процессов !! 32 процесса !! 64 процесса
|-
|1000x1000 || 0.000358 || 0.000233 || 0.000156 ||0.000079 || 0.000064 || 0.000038 || 0.000015
|-
|2000x2000 || 0.001373 || 0.000926 || 0.000701 || 0.000536 || 0.000273 || 0.000090 || 0.000042
|-
|3000x3000 || 0.003451 || 0.002439 || 0.001691 || 0.001200 || 0.000617 || 0.000166 || 0.000085
|-
|4000x4000 || 0.007259 || 0.003992 || 0.002923 || 0.001972 || 0.001029 || 0.000298 || 0.000135
|-
|5000x5000 || 0.011327 || 0.006031 || 0.004380 || 0.002532 || 0.001452 || 0.000439 || 0.000236
|-
|6000x6000 || 0.016217 || 0.008659 || 0.007147 || 0.003346 || 0.002009 || 0.000606 || 0.000326
|-
|7000x7000 || 0.022054 || 0.011617 || 0.008796 || 0.004212 || 0.002220 || 0.000914 || 0.000399
|-
|8000x8000 || 0.028572 || 0.015224 || 0.009939 || 0.005330 || 0.002697 || 0.001254 || 0.000534
|-
|9000x9000 || 0.035642 || 0.019085 || 0.012258 || 0.006447 || 0.003769 || 0.001428 || 0.000769
|-
|10000x10000 || 0.043867 || 0.023461 || 0.012777 || 0.007889 || 0.004756 || 0.002258 || 0.000792
|-
|11000x11000 || 0.052932 || 0.028309 || 0.018155 || 0.009360 || 0.005155 || 0.002243 || 0.001000
|}

=== 2.4 Выводы для классов архитектур ===
=== 2.5 Код на MPI ===
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include <time.h>

typedef struct {
int row;
int col;
} SaddlePoint;

int main(int argc, char* argv[])
{
int rank, size;
int m, n;
int i, j;

MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);

if (argc != 3) {
if (rank == 0) {
fprintf(stderr, "Usage: %s <rows> <cols>\n", argv[0]);
}
MPI_Finalize();
return 1;
}

m = atoi(argv[1]);
n = atoi(argv[2]);

if (m <= 0 || n <= 0) {
if (rank == 0) {
fprintf(stderr, "Matrix dimensions must be positive.\n");
}
MPI_Finalize();
return 1;
}

/* Каждый процесс выделяет память под всю матрицу */
int* A = (int*)malloc(m * n * sizeof(int));
if (A == NULL) {
if (rank == 0) fprintf(stderr, "Memory allocation failed.\n");
MPI_Abort(MPI_COMM_WORLD, 1);
}

/* Процесс 0 генерирует матрицу */
if (rank == 0) {
srand((unsigned int)time(NULL));
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
A[i * n + j] = rand() % 1000;
}
}
}

/* Рассылаем всю матрицу всем процессам */
MPI_Bcast(A, m * n, MPI_INT, 0, MPI_COMM_WORLD);

/* === НАЧАЛО ЗАМЕРА ВРЕМЕНИ === */
MPI_Barrier(MPI_COMM_WORLD);
double t1 = MPI_Wtime();

/* Каждый процесс обрабатывает строки: i % size == rank */
int max_local = (m + size - 1) / size; /* верхняя оценка числа строк на процесс */
SaddlePoint* local_saddles = (SaddlePoint*)malloc(max_local * sizeof(SaddlePoint));
int local_count = 0;

for (i = rank; i < m; i += size) {
/* Уровень 1: найти минимум в строке i */
int min_val = A[i * n + 0];
int min_j = 0;
for (j = 1; j < n; j++) {
if (A[i * n + j] < min_val) {
min_val = A[i * n + j];
min_j = j;
}
}

/* Уровень 2: проверить максимум в столбце min_j */
int is_max = 1;
for (j = 0; j < m; j++) {
if (A[j * n + min_j] > min_val) {
is_max = 0;
break;
}
}

if (is_max) {
local_saddles[local_count].row = i;
local_saddles[local_count].col = min_j;
local_count++;
}
}

double t2 = MPI_Wtime();

/* Собрать результаты */
int* all_counts = NULL;
int total_saddles = 0;

if (rank == 0) {
all_counts = (int*)malloc(size * sizeof(int));
}

MPI_Gather(&local_count, 1, MPI_INT, all_counts, 1, MPI_INT, 0, MPI_COMM_WORLD);

if (rank == 0) {
for (i = 0; i < size; i++) {
total_saddles += all_counts[i];
}
}

SaddlePoint* global_saddles = NULL;
int* displs = NULL;

if (rank == 0) {
global_saddles = (SaddlePoint*)malloc(total_saddles * sizeof(SaddlePoint));
displs = (int*)malloc(size * sizeof(int));
displs[0] = 0;
for (i = 1; i < size; i++) {
displs[i] = displs[i - 1] + all_counts[i - 1];
}
}

MPI_Gatherv(
local_saddles, local_count, MPI_BYTE,
global_saddles, all_counts, displs, MPI_BYTE,
0, MPI_COMM_WORLD
);

/* Вывод */
if (rank == 0) {
FILE* fout = fopen("result.out", "a");
if (fout) {
fprintf(fout, "%d %d %.6f\n", m, size, t2 - t1);
fclose(fout);
}

if (total_saddles == 0) {
printf("No saddle point found.\n");
} else {
printf("Found %d saddle point(s):\n", total_saddles);
for (i = 0; i < total_saddles; i++) {
printf(" (%d, %d)\n", global_saddles[i].row, global_saddles[i].col);
}
}
printf("Matrix: %dx%d, Processes: %d, Time: %.6f seconds\n", m, n, size, t2 - t1);

free(all_counts);
free(displs);
free(global_saddles);
}

free(local_saddles);
free(A);
MPI_Finalize();
return 0;
}

== ''' Литература''' ==

Участник:Zerika

2025-12-09T21:06:03Z

Zerika: /* Программная реализация алгоритма */

'''Седловой элемент матрицы''' <math> A = (a_{i, j})_{i = 1, j = 1}^{m, n}</math> — элемент матрицы <math>a_{k, d}</math>, удовлетворяющий условиям <math>a_{k, d} = \max_{1 \le i \le m} a_{i, d} = \min_{1 \le j \le n} a_{k, j}</math>, то есть элемент матрицы, который одновременно является минимальным элементом в соответствующей строке матрицы и максимальным элементом в соответствующем столбце матрицы. Из определения следует, что <math>a_{k, d} = \max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j}</math>. Более того, для матрицы существует седловой элемент тогда и только тогда, когда <math>\max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j}</math>.
'''Примеры'''
 
Матрица
: <math>\begin{bmatrix}
5 & 6 & 4 & 5\\
-2 & 5 & 3 & 7\\
8 & 7 & -2 & 6\\
\end{bmatrix}
</math>
имеет 1 седловой элемент, равный 4, который расположен в первой строке в третьем столбце матрицы, так как он одновременно является минимальным элементом в соответствующей строке матрицы (в данном случае в первой строке матрицы) и максимальным элементом в соответствующем столбце матрицы (в данном случае в третьем столбце матрицы).

Матрица
: <math>\begin{bmatrix}
2 & 3 & 5 & 2\\
2 & 4 & 6 & 2\\
-2 & 7 & 2 & 0\\
\end{bmatrix}
</math>
имеет 4 седловых элемента, равных 2, которые расположены в первой строке в первом столбце, в первой строке в четвёртом столбце, во второй строке в первом столбце, во второй строке в четвёртом столбце матрицы, соответственно.

Данный пример показывает, что матрица может иметь несколько (более одной) седловых точек.
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для поиска седловой точки в числовой матрице A. Седловой точкой называется элемент матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце. Алгоритм является прямым (не итерационным) и детерминированным. Его суть заключается в последовательном сканировании строк матрицы для поиска минимумов, а затем в проверке этих кандидатов на максимальность в соответствующих столбцах. В матрице может быть несколько седловых точек или не быть ни одной.

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

=== Математическое описание ===
Пусть задана матрица '''A''' размерности '''m x n''' (m строк, n столбцов).

Элемент '''Aij''' является седловой точкой, если выполняются два условия:

Он является минимальным элементом в своей строке i:

'''Aij = min Aik, k от 1 до n'''

Он является максимальным элементом в своем столбце j:

'''Aij = max Adj, d от 1 до m'''

Алгоритм можно описать как поиск таких индексов (i, j), для которых:

'''∀k: Aij ≤ Aik и ∀d: Aij ≥ Adj'''
=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит из двух последовательных этапов:

Поиск минимумов в строках, в котором для каждой строки i матрицы A последовательно сравниваются элементы Aij с текущим минимумом, и при нахождении меньшего значения обновляются минимальный элемент и его позиция столбец (d).

Проверка кандидатов в столбцах d, в котором для каждого найденного минимума строки последовательно сравниваются элементы Aid соответствующего столбца с кандидатом, и при обнаружении большего элемента проверка прекращается.
=== Макроструктура алгоритма ===
Алгоритм состоит из двух последовательных макроопераций:

1. Поиск минимума в каждой строке матрицы. Эта операция представляет собой цикл по всем строкам, внутри которого выполняется сканирование элементов строки.

2. Проверка найденных кандидатов на максимальность в их столбцах. Эта операция представляет собой цикл по всем строкам-кандидатам, внутри которого для каждого кандидата выполняется полный проход по его столбцу.

=== Схема реализации последовательного алгоритма ===
Для каждой строки i:

# Найти индекс позиции j минимального элемента строки.
# Проверить, является ли Ai,j максимальным в столбце j.
# Если да — вернуть (i,j) как седловую точку.
# Если ни для одной строки условие не выполнено — сообщить об отсутствии седловой точки.

=== Последовательная сложность алгоритма ===
Для матрицы размером '''m×n'''
 Поиск минимума в строке занимает — '''O(n)'''
 
Проверка максимума в столбце — '''O(m)'''
 
Итого на каждую строку — '''O(m+n)'''
 
Общая сложность — '''O(m(m+n))''', что при квадратной матрице '''n = m''' равно '''O(n^2)'''

=== Информационный граф ===
Информационный граф отражает две основные операции над каждой строкой: поиск минимума и проверку максимума в столбце. Между итерациями отсутствуют зависимости, параллелизм возможен по строкам.

Граф относительно прост и состоит из двух последовательных уровней вычислений для каждой строки.

* Уровень 1 (Поиск минимумов): m независимых вершин (по одной на каждую строку), каждая из которых выполняет операцию нахождения минимума в своем наборе данных (элементах строки) и номер его столбца d. Эти вершины не связаны между собой.

* Уровень 2 (Проверка кандидатов): m вершин (по одной на каждого кандидата). Каждая вершина i на этом уровне использует результат вершины i с первого уровня (столбец-кандидат) и требует данные всего столбца d из исходной матрицы для проверки на максимум. Вершины этого уровня также независимы друг от друга.

Связь между уровнями: Результат работы вершины i Уровня 1 (значение d) является входным данным для вершины i Уровня 2.

[[Файл: Graf sedl.png |500px|thumb|center|Граф поиска седловой точки матрицы]]

=== Ресурс параллелизма алгоритма ===
* Параллелизм на макроуровне (между строками): Поиск минимумов в строках может выполняться полностью параллельно. Все m задач Уровня 1 независимы. Аналогично, проверка всех m кандидатов на Уровне 2 также может выполняться параллельно.
* Параллельная сложность:
# При наличии m процессоров поиск минимумов во всех строках можно выполнить за O(n) времени (время обработки одной строки).
# Проверку всех кандидатов на наличие максимума в столбцах, при наличии m процессоров, можно выполнить за O(m) времени (время прохода по одному столбцу). Таким образом, общая параллельная сложность составляет O(n + m).
#Параллелизм реализуется на уровне итераций по строкам — независимые проверки каждой строки и связанных с ними операций.
Для матрицы большого размера этот подход позволяет ускорить алгоритм на многопроцессорных системах.
=== Входные и выходные данные алгоритма ===
'''Входные данные:''' Прямоугольная числовая матрица A размером m x n. Тип элементов - целый или вещественный. Особых свойств от матрицы не требуется.

'''Выходные данные:''' Координаты найденных седловых точек (i, j) или индикатор ее отсутствия (например, None).

=== Свойства алгоритма ===
* В матрице может быть несколько седловых точек или ни одной
* Алгоритм устойчив к дублирующимся значениям

== ''' Программная реализация алгоритма''' ==
=== 2.1 Особенности реализации последовательного алгоритма ===
def find_all_saddle_points_optimized(matrix):

if not matrix or not matrix[0]:
return []

m = len(matrix) # количество строк
n = len(matrix[0]) # количество столбцов

saddle_points = []

for i in range(m):
# Шаг 1: Находим все индексы минимальных элементов в строке i
min_in_row = matrix[i][0]
min_indices = [0]

for j in range(1, n):
if matrix[i][j] < min_in_row:
min_in_row = matrix[i][j]
min_indices = [j]
elif matrix[i][j] == min_in_row:
min_indices.append(j)

# Шаг 2: Для каждого минимального элемента проверяем,
# является ли он максимальным в своем столбце
for j in min_indices:
is_saddle = True
for k in range(m):
if matrix[k][j] > matrix[i][j]:
is_saddle = False
break

if is_saddle:
saddle_points.append({
'row': i,
'col': j,
'value': matrix[i][j]
})

return saddle_points

=== 2.2 Возможные способы и особенности параллельной реализации алгоритма===
def find_all_saddle_points_parallel(matrix):
if not matrix or not matrix[0]:
return []

m = len(matrix)
n = len(matrix[0])

def process_row(i):
"""
Обработка одной строки для поиска ВСЕХ потенциальных седловых точек
"""
row_results = []

# Находим все минимальные элементы в строке
min_in_row = matrix[i][0]
min_indices = [0]

for j in range(1, n):
if matrix[i][j] < min_in_row:
min_in_row = matrix[i][j]
min_indices = [j]
elif matrix[i][j] == min_in_row:
min_indices.append(j)

# Для каждого минимального элемента проверяем условие
for j in min_indices:
is_saddle = True
for k in range(m):
if matrix[k][j] > matrix[i][j]:
is_saddle = False
break

if is_saddle:
row_results.append((i, j, matrix[i][j]))

return row_results

# Параллельная обработка строк
saddle_points = []
with concurrent.futures.ThreadPoolExecutor(max_workers=min(m, 4)) as executor:
futures = [executor.submit(process_row, i) for i in range(m)]

# Собираем все результаты
for future in concurrent.futures.as_completed(futures):
row_results = future.result()
for result in row_results:
saddle_points.append({
'row': result[0],
'col': result[1],
'value': result[2]
})

return saddle_points

=== 2.3 Результаты прогонов ===
Для всех запусков седловая точка не была найдена (No saddle point found). Значения времени усреднены по трём прогонам. Время показано в секундах.

{| class="wikitable"

! Размер матрицы !! 1 процесс !! 2 процесса !! 4 процесса !! 8 процессов !! 16 процессов !! 32 процесса !! 64 процесса
|-
|1000x1000 || 0.000358 || 0.000233 || 0.000156 ||0.000079 || 0.000064 || 0.000038 || 0.000015
|-
|2000x2000 || 0.001373 || 0.000926 || 0.000701 || 0.000536 || 0.000273 || 0.000090 || 0.000042
|-
|3000x3000 || 0.003451 || 0.002439 || 0.001691 || 0.001200 || 0.000617 || 0.000166 || 0.000085
|-
|4000x4000 || 0.007259 || 0.003992 || 0.002923 || 0.001972 || 0.001029 || 0.000298 || 0.000135
|-
|5000x5000 || 0.011327 || 0.006031 || 0.004380 || 0.002532 || 0.001452 || 0.000439 || 0.000236
|-
|6000x6000 || 0.016217 || 0.008659 || 0.007147 || 0.003346 || 0.002009 || 0.000606 || 0.000326
|-
|7000x7000 || 0.022054 || 0.011617 || 0.008796 || 0.004212 || 0.002220 || 0.000914 || 0.000399
|-
|8000x8000 || 0.028572 || 0.015224 || 0.009939 || 0.005330 || 0.002697 || 0.001254 || 0.000534
|-
|9000x9000 || 0.035642 || 0.019085 || 0.012258 || 0.006447 || 0.003769 || 0.001428 || 0.000769
|-
|10000x10000 || 0.043867 || 0.023461 || 0.012777 || 0.007889 || 0.004756 || 0.002258 || 0.000792
|-
|11000x11000 || 0.052932 || 0.028309 || 0.018155 || 0.009360 || 0.005155 || 0.002243 || 0.001000
|}

=== 2.4 Выводы для классов архитектур ===
=== 2.5 Код на MPI ===
#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>
#include <time.h>

typedef struct {
int row;
int col;
} SaddlePoint;

int main(int argc, char* argv[])
{
int rank, size;
int m, n;
int i, j;

MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);

if (argc != 3) {
if (rank == 0) {
fprintf(stderr, "Usage: %s <rows> <cols>\n", argv[0]);
}
MPI_Finalize();
return 1;
}

m = atoi(argv[1]);
n = atoi(argv[2]);

if (m <= 0 || n <= 0) {
if (rank == 0) {
fprintf(stderr, "Matrix dimensions must be positive.\n");
}
MPI_Finalize();
return 1;
}

/* Каждый процесс выделяет память под всю матрицу */
int* A = (int*)malloc(m * n * sizeof(int));
if (A == NULL) {
if (rank == 0) fprintf(stderr, "Memory allocation failed.\n");
MPI_Abort(MPI_COMM_WORLD, 1);
}

/* Процесс 0 генерирует матрицу */
if (rank == 0) {
srand((unsigned int)time(NULL));
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
A[i * n + j] = rand() % 1000;
}
}
}

/* Рассылаем всю матрицу всем процессам */
MPI_Bcast(A, m * n, MPI_INT, 0, MPI_COMM_WORLD);

/* === НАЧАЛО ЗАМЕРА ВРЕМЕНИ === */
MPI_Barrier(MPI_COMM_WORLD);
double t1 = MPI_Wtime();

/* Каждый процесс обрабатывает строки: i % size == rank */
int max_local = (m + size - 1) / size; /* верхняя оценка числа строк на процесс */
SaddlePoint* local_saddles = (SaddlePoint*)malloc(max_local * sizeof(SaddlePoint));
int local_count = 0;

for (i = rank; i < m; i += size) {
/* Уровень 1: найти минимум в строке i */
int min_val = A[i * n + 0];
int min_j = 0;
for (j = 1; j < n; j++) {
if (A[i * n + j] < min_val) {
min_val = A[i * n + j];
min_j = j;
}
}

/* Уровень 2: проверить максимум в столбце min_j */
int is_max = 1;
for (j = 0; j < m; j++) {
if (A[j * n + min_j] > min_val) {
is_max = 0;
break;
}
}

if (is_max) {
local_saddles[local_count].row = i;
local_saddles[local_count].col = min_j;
local_count++;
}
}

double t2 = MPI_Wtime();

/* Собрать результаты */
int* all_counts = NULL;
int total_saddles = 0;

if (rank == 0) {
all_counts = (int*)malloc(size * sizeof(int));
}

MPI_Gather(&local_count, 1, MPI_INT, all_counts, 1, MPI_INT, 0, MPI_COMM_WORLD);

if (rank == 0) {
for (i = 0; i < size; i++) {
total_saddles += all_counts[i];
}
}

SaddlePoint* global_saddles = NULL;
int* displs = NULL;

if (rank == 0) {
global_saddles = (SaddlePoint*)malloc(total_saddles * sizeof(SaddlePoint));
displs = (int*)malloc(size * sizeof(int));
displs[0] = 0;
for (i = 1; i < size; i++) {
displs[i] = displs[i - 1] + all_counts[i - 1];
}
}

MPI_Gatherv(
local_saddles, local_count, MPI_BYTE,
global_saddles, all_counts, displs, MPI_BYTE,
0, MPI_COMM_WORLD
);

/* Вывод */
if (rank == 0) {
FILE* fout = fopen("result.out", "a");
if (fout) {
fprintf(fout, "%d %d %.6f\n", m, size, t2 - t1);
fclose(fout);
}

if (total_saddles == 0) {
printf("No saddle point found.\n");
} else {
printf("Found %d saddle point(s):\n", total_saddles);
for (i = 0; i < total_saddles; i++) {
printf(" (%d, %d)\n", global_saddles[i].row, global_saddles[i].col);
}
}
printf("Matrix: %dx%d, Processes: %d, Time: %.6f seconds\n", m, n, size, t2 - t1);

free(all_counts);
free(displs);
free(global_saddles);
}

free(local_saddles);
free(A);
MPI_Finalize();
return 0;
}

== ''' Литература''' ==

Участник:Zerika

2025-12-09T20:16:12Z

Zerika: /* 2.3 Результаты прогонов */

Участник:Zerika

2025-12-09T20:02:13Z

Zerika: /* 2.1 Особенности реализации последовательного алгоритма */

'''Седловой элемент матрицы''' <math> A = (a_{i, j})_{i = 1, j = 1}^{m, n}</math> — элемент матрицы <math>a_{k, d}</math>, удовлетворяющий условиям <math>a_{k, d} = \max_{1 \le i \le m} a_{i, d} = \min_{1 \le j \le n} a_{k, j}</math>, то есть элемент матрицы, который одновременно является минимальным элементом в соответствующей строке матрицы и максимальным элементом в соответствующем столбце матрицы. Из определения следует, что <math>a_{k, d} = \max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j}</math>. Более того, для матрицы существует седловой элемент тогда и только тогда, когда <math>\max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j}</math>.
'''Примеры'''
 
Матрица
: <math>\begin{bmatrix}
5 & 6 & 4 & 5\\
-2 & 5 & 3 & 7\\
8 & 7 & -2 & 6\\
\end{bmatrix}
</math>
имеет 1 седловой элемент, равный 4, который расположен в первой строке в третьем столбце матрицы, так как он одновременно является минимальным элементом в соответствующей строке матрицы (в данном случае в первой строке матрицы) и максимальным элементом в соответствующем столбце матрицы (в данном случае в третьем столбце матрицы).

Матрица
: <math>\begin{bmatrix}
2 & 3 & 5 & 2\\
2 & 4 & 6 & 2\\
-2 & 7 & 2 & 0\\
\end{bmatrix}
</math>
имеет 4 седловых элемента, равных 2, которые расположены в первой строке в первом столбце, в первой строке в четвёртом столбце, во второй строке в первом столбце, во второй строке в четвёртом столбце матрицы, соответственно.

Данный пример показывает, что матрица может иметь несколько (более одной) седловых точек.
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для поиска седловой точки в числовой матрице A. Седловой точкой называется элемент матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце. Алгоритм является прямым (не итерационным) и детерминированным. Его суть заключается в последовательном сканировании строк матрицы для поиска минимумов, а затем в проверке этих кандидатов на максимальность в соответствующих столбцах. В матрице может быть несколько седловых точек или не быть ни одной.

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

=== Математическое описание ===
Пусть задана матрица '''A''' размерности '''m x n''' (m строк, n столбцов).

Элемент '''Aij''' является седловой точкой, если выполняются два условия:

Он является минимальным элементом в своей строке i:

'''Aij = min Aik, k от 1 до n'''

Он является максимальным элементом в своем столбце j:

'''Aij = max Adj, d от 1 до m'''

Алгоритм можно описать как поиск таких индексов (i, j), для которых:

'''∀k: Aij ≤ Aik и ∀d: Aij ≥ Adj'''
=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит из двух последовательных этапов:

Поиск минимумов в строках, в котором для каждой строки i матрицы A последовательно сравниваются элементы Aij с текущим минимумом, и при нахождении меньшего значения обновляются минимальный элемент и его позиция столбец (d).

Проверка кандидатов в столбцах d, в котором для каждого найденного минимума строки последовательно сравниваются элементы Aid соответствующего столбца с кандидатом, и при обнаружении большего элемента проверка прекращается.
=== Макроструктура алгоритма ===
Алгоритм состоит из двух последовательных макроопераций:

1. Поиск минимума в каждой строке матрицы. Эта операция представляет собой цикл по всем строкам, внутри которого выполняется сканирование элементов строки.

2. Проверка найденных кандидатов на максимальность в их столбцах. Эта операция представляет собой цикл по всем строкам-кандидатам, внутри которого для каждого кандидата выполняется полный проход по его столбцу.

=== Схема реализации последовательного алгоритма ===
Для каждой строки i:

# Найти индекс позиции j минимального элемента строки.
# Проверить, является ли Ai,j максимальным в столбце j.
# Если да — вернуть (i,j) как седловую точку.
# Если ни для одной строки условие не выполнено — сообщить об отсутствии седловой точки.

=== Последовательная сложность алгоритма ===
Для матрицы размером '''m×n'''
 Поиск минимума в строке занимает — '''O(n)'''
 
Проверка максимума в столбце — '''O(m)'''
 
Итого на каждую строку — '''O(m+n)'''
 
Общая сложность — '''O(m(m+n))''', что при квадратной матрице '''n = m''' равно '''O(n^2)'''

=== Информационный граф ===
Информационный граф отражает две основные операции над каждой строкой: поиск минимума и проверку максимума в столбце. Между итерациями отсутствуют зависимости, параллелизм возможен по строкам.

Граф относительно прост и состоит из двух последовательных уровней вычислений для каждой строки.

* Уровень 1 (Поиск минимумов): m независимых вершин (по одной на каждую строку), каждая из которых выполняет операцию нахождения минимума в своем наборе данных (элементах строки) и номер его столбца d. Эти вершины не связаны между собой.

* Уровень 2 (Проверка кандидатов): m вершин (по одной на каждого кандидата). Каждая вершина i на этом уровне использует результат вершины i с первого уровня (столбец-кандидат) и требует данные всего столбца d из исходной матрицы для проверки на максимум. Вершины этого уровня также независимы друг от друга.

Связь между уровнями: Результат работы вершины i Уровня 1 (значение d) является входным данным для вершины i Уровня 2.

[[Файл: Graf sedl.png |500px|thumb|center|Граф поиска седловой точки матрицы]]

=== Ресурс параллелизма алгоритма ===
* Параллелизм на макроуровне (между строками): Поиск минимумов в строках может выполняться полностью параллельно. Все m задач Уровня 1 независимы. Аналогично, проверка всех m кандидатов на Уровне 2 также может выполняться параллельно.
* Параллельная сложность:
# При наличии m процессоров поиск минимумов во всех строках можно выполнить за O(n) времени (время обработки одной строки).
# Проверку всех кандидатов на наличие максимума в столбцах, при наличии m процессоров, можно выполнить за O(m) времени (время прохода по одному столбцу). Таким образом, общая параллельная сложность составляет O(n + m).
#Параллелизм реализуется на уровне итераций по строкам — независимые проверки каждой строки и связанных с ними операций.
Для матрицы большого размера этот подход позволяет ускорить алгоритм на многопроцессорных системах.
=== Входные и выходные данные алгоритма ===
'''Входные данные:''' Прямоугольная числовая матрица A размером m x n. Тип элементов - целый или вещественный. Особых свойств от матрицы не требуется.

'''Выходные данные:''' Координаты найденных седловых точек (i, j) или индикатор ее отсутствия (например, None).

=== Свойства алгоритма ===
* В матрице может быть несколько седловых точек или ни одной
* Алгоритм устойчив к дублирующимся значениям

== ''' Программная реализация алгоритма''' ==
=== 2.1 Особенности реализации последовательного алгоритма ===
def find_all_saddle_points_optimized(matrix):

if not matrix or not matrix[0]:
return []

m = len(matrix) # количество строк
n = len(matrix[0]) # количество столбцов

saddle_points = []

for i in range(m):
# Шаг 1: Находим все индексы минимальных элементов в строке i
min_in_row = matrix[i][0]
min_indices = [0]

for j in range(1, n):
if matrix[i][j] < min_in_row:
min_in_row = matrix[i][j]
min_indices = [j]
elif matrix[i][j] == min_in_row:
min_indices.append(j)

# Шаг 2: Для каждого минимального элемента проверяем,
# является ли он максимальным в своем столбце
for j in min_indices:
is_saddle = True
for k in range(m):
if matrix[k][j] > matrix[i][j]:
is_saddle = False
break

if is_saddle:
saddle_points.append({
'row': i,
'col': j,
'value': matrix[i][j]
})

return saddle_points

=== 2.2 Возможные способы и особенности параллельной реализации алгоритма===
def find_all_saddle_points_parallel(matrix):
if not matrix or not matrix[0]:
return []

m = len(matrix)
n = len(matrix[0])

def process_row(i):
"""
Обработка одной строки для поиска ВСЕХ потенциальных седловых точек
"""
row_results = []

# Находим все минимальные элементы в строке
min_in_row = matrix[i][0]
min_indices = [0]

for j in range(1, n):
if matrix[i][j] < min_in_row:
min_in_row = matrix[i][j]
min_indices = [j]
elif matrix[i][j] == min_in_row:
min_indices.append(j)

# Для каждого минимального элемента проверяем условие
for j in min_indices:
is_saddle = True
for k in range(m):
if matrix[k][j] > matrix[i][j]:
is_saddle = False
break

if is_saddle:
row_results.append((i, j, matrix[i][j]))

return row_results

# Параллельная обработка строк
saddle_points = []
with concurrent.futures.ThreadPoolExecutor(max_workers=min(m, 4)) as executor:
futures = [executor.submit(process_row, i) for i in range(m)]

# Собираем все результаты
for future in concurrent.futures.as_completed(futures):
row_results = future.result()
for result in row_results:
saddle_points.append({
'row': result[0],
'col': result[1],
'value': result[2]
})

return saddle_points

=== 2.3 Результаты прогонов ===
=== 2.4 Выводы для классов архитектур ===
== ''' Литература''' ==

Участник:Zerika

2025-12-09T20:02:02Z

Zerika: /* 2.2 Возможные способы и особенности параллельной реализации алгоритма */

'''Седловой элемент матрицы''' <math> A = (a_{i, j})_{i = 1, j = 1}^{m, n}</math> — элемент матрицы <math>a_{k, d}</math>, удовлетворяющий условиям <math>a_{k, d} = \max_{1 \le i \le m} a_{i, d} = \min_{1 \le j \le n} a_{k, j}</math>, то есть элемент матрицы, который одновременно является минимальным элементом в соответствующей строке матрицы и максимальным элементом в соответствующем столбце матрицы. Из определения следует, что <math>a_{k, d} = \max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j}</math>. Более того, для матрицы существует седловой элемент тогда и только тогда, когда <math>\max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j}</math>.
'''Примеры'''
 
Матрица
: <math>\begin{bmatrix}
5 & 6 & 4 & 5\\
-2 & 5 & 3 & 7\\
8 & 7 & -2 & 6\\
\end{bmatrix}
</math>
имеет 1 седловой элемент, равный 4, который расположен в первой строке в третьем столбце матрицы, так как он одновременно является минимальным элементом в соответствующей строке матрицы (в данном случае в первой строке матрицы) и максимальным элементом в соответствующем столбце матрицы (в данном случае в третьем столбце матрицы).

Матрица
: <math>\begin{bmatrix}
2 & 3 & 5 & 2\\
2 & 4 & 6 & 2\\
-2 & 7 & 2 & 0\\
\end{bmatrix}
</math>
имеет 4 седловых элемента, равных 2, которые расположены в первой строке в первом столбце, в первой строке в четвёртом столбце, во второй строке в первом столбце, во второй строке в четвёртом столбце матрицы, соответственно.

Данный пример показывает, что матрица может иметь несколько (более одной) седловых точек.
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для поиска седловой точки в числовой матрице A. Седловой точкой называется элемент матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце. Алгоритм является прямым (не итерационным) и детерминированным. Его суть заключается в последовательном сканировании строк матрицы для поиска минимумов, а затем в проверке этих кандидатов на максимальность в соответствующих столбцах. В матрице может быть несколько седловых точек или не быть ни одной.

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

=== Математическое описание ===
Пусть задана матрица '''A''' размерности '''m x n''' (m строк, n столбцов).

Элемент '''Aij''' является седловой точкой, если выполняются два условия:

Он является минимальным элементом в своей строке i:

'''Aij = min Aik, k от 1 до n'''

Он является максимальным элементом в своем столбце j:

'''Aij = max Adj, d от 1 до m'''

Алгоритм можно описать как поиск таких индексов (i, j), для которых:

'''∀k: Aij ≤ Aik и ∀d: Aij ≥ Adj'''
=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит из двух последовательных этапов:

Поиск минимумов в строках, в котором для каждой строки i матрицы A последовательно сравниваются элементы Aij с текущим минимумом, и при нахождении меньшего значения обновляются минимальный элемент и его позиция столбец (d).

Проверка кандидатов в столбцах d, в котором для каждого найденного минимума строки последовательно сравниваются элементы Aid соответствующего столбца с кандидатом, и при обнаружении большего элемента проверка прекращается.
=== Макроструктура алгоритма ===
Алгоритм состоит из двух последовательных макроопераций:

1. Поиск минимума в каждой строке матрицы. Эта операция представляет собой цикл по всем строкам, внутри которого выполняется сканирование элементов строки.

2. Проверка найденных кандидатов на максимальность в их столбцах. Эта операция представляет собой цикл по всем строкам-кандидатам, внутри которого для каждого кандидата выполняется полный проход по его столбцу.

=== Схема реализации последовательного алгоритма ===
Для каждой строки i:

# Найти индекс позиции j минимального элемента строки.
# Проверить, является ли Ai,j максимальным в столбце j.
# Если да — вернуть (i,j) как седловую точку.
# Если ни для одной строки условие не выполнено — сообщить об отсутствии седловой точки.

=== Последовательная сложность алгоритма ===
Для матрицы размером '''m×n'''
 Поиск минимума в строке занимает — '''O(n)'''
 
Проверка максимума в столбце — '''O(m)'''
 
Итого на каждую строку — '''O(m+n)'''
 
Общая сложность — '''O(m(m+n))''', что при квадратной матрице '''n = m''' равно '''O(n^2)'''

=== Информационный граф ===
Информационный граф отражает две основные операции над каждой строкой: поиск минимума и проверку максимума в столбце. Между итерациями отсутствуют зависимости, параллелизм возможен по строкам.

Граф относительно прост и состоит из двух последовательных уровней вычислений для каждой строки.

* Уровень 1 (Поиск минимумов): m независимых вершин (по одной на каждую строку), каждая из которых выполняет операцию нахождения минимума в своем наборе данных (элементах строки) и номер его столбца d. Эти вершины не связаны между собой.

* Уровень 2 (Проверка кандидатов): m вершин (по одной на каждого кандидата). Каждая вершина i на этом уровне использует результат вершины i с первого уровня (столбец-кандидат) и требует данные всего столбца d из исходной матрицы для проверки на максимум. Вершины этого уровня также независимы друг от друга.

Связь между уровнями: Результат работы вершины i Уровня 1 (значение d) является входным данным для вершины i Уровня 2.

[[Файл: Graf sedl.png |500px|thumb|center|Граф поиска седловой точки матрицы]]

=== Ресурс параллелизма алгоритма ===
* Параллелизм на макроуровне (между строками): Поиск минимумов в строках может выполняться полностью параллельно. Все m задач Уровня 1 независимы. Аналогично, проверка всех m кандидатов на Уровне 2 также может выполняться параллельно.
* Параллельная сложность:
# При наличии m процессоров поиск минимумов во всех строках можно выполнить за O(n) времени (время обработки одной строки).
# Проверку всех кандидатов на наличие максимума в столбцах, при наличии m процессоров, можно выполнить за O(m) времени (время прохода по одному столбцу). Таким образом, общая параллельная сложность составляет O(n + m).
#Параллелизм реализуется на уровне итераций по строкам — независимые проверки каждой строки и связанных с ними операций.
Для матрицы большого размера этот подход позволяет ускорить алгоритм на многопроцессорных системах.
=== Входные и выходные данные алгоритма ===
'''Входные данные:''' Прямоугольная числовая матрица A размером m x n. Тип элементов - целый или вещественный. Особых свойств от матрицы не требуется.

'''Выходные данные:''' Координаты найденных седловых точек (i, j) или индикатор ее отсутствия (например, None).

=== Свойства алгоритма ===
* В матрице может быть несколько седловых точек или ни одной
* Алгоритм устойчив к дублирующимся значениям

== ''' Программная реализация алгоритма''' ==
=== 2.1 Особенности реализации последовательного алгоритма ===
def find_all_saddle_points_optimized(matrix):

if not matrix or not matrix[0]:
return []

m = len(matrix) # количество строк
n = len(matrix[0]) # количество столбцов

saddle_points = []

for i in range(m):
# Шаг 1: Находим все индексы минимальных элементов в строке i
min_in_row = matrix[i][0]
min_indices = [0]

for j in range(1, n):
if matrix[i][j] < min_in_row:
min_in_row = matrix[i][j]
min_indices = [j]
elif matrix[i][j] == min_in_row:
min_indices.append(j)

# Шаг 2: Для каждого минимального элемента проверяем,
# является ли он максимальным в своем столбце
for j in min_indices:
is_saddle = True
for k in range(m):
if matrix[k][j] > matrix[i][j]:
is_saddle = False
break

if is_saddle:
saddle_points.append({
'row': i,
'col': j,
'value': matrix[i][j]
})

return saddle_points

=== 2.2 Возможные способы и особенности параллельной реализации алгоритма===
def find_all_saddle_points_parallel(matrix):
if not matrix or not matrix[0]:
return []

m = len(matrix)
n = len(matrix[0])

def process_row(i):
"""
Обработка одной строки для поиска ВСЕХ потенциальных седловых точек
"""
row_results = []

# Находим все минимальные элементы в строке
min_in_row = matrix[i][0]
min_indices = [0]

for j in range(1, n):
if matrix[i][j] < min_in_row:
min_in_row = matrix[i][j]
min_indices = [j]
elif matrix[i][j] == min_in_row:
min_indices.append(j)

# Для каждого минимального элемента проверяем условие
for j in min_indices:
is_saddle = True
for k in range(m):
if matrix[k][j] > matrix[i][j]:
is_saddle = False
break

if is_saddle:
row_results.append((i, j, matrix[i][j]))

return row_results

# Параллельная обработка строк
saddle_points = []
with concurrent.futures.ThreadPoolExecutor(max_workers=min(m, 4)) as executor:
futures = [executor.submit(process_row, i) for i in range(m)]

# Собираем все результаты
for future in concurrent.futures.as_completed(futures):
row_results = future.result()
for result in row_results:
saddle_points.append({
'row': result[0],
'col': result[1],
'value': result[2]
})

return saddle_points

=== 2.3 Результаты прогонов ===
=== 2.4 Выводы для классов архитектур ===
== ''' Литература''' ==

Участник:Zerika

2025-12-09T14:00:24Z

Zerika: /* 2.2 Возможные способы и особенности параллельной реализации алгоритма */

'''Седловой элемент матрицы''' <math> A = (a_{i, j})_{i = 1, j = 1}^{m, n}</math> — элемент матрицы <math>a_{k, d}</math>, удовлетворяющий условиям <math>a_{k, d} = \max_{1 \le i \le m} a_{i, d} = \min_{1 \le j \le n} a_{k, j}</math>, то есть элемент матрицы, который одновременно является минимальным элементом в соответствующей строке матрицы и максимальным элементом в соответствующем столбце матрицы. Из определения следует, что <math>a_{k, d} = \max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j}</math>. Более того, для матрицы существует седловой элемент тогда и только тогда, когда <math>\max_{1 \le i \le m}\ \min_{1 \le j \le n}a_{i, j} = \min_{1 \le j \le n}\ \max_{1 \le i \le m}a_{i, j}</math>.
'''Примеры'''
 
Матрица
: <math>\begin{bmatrix}
5 & 6 & 4 & 5\\
-2 & 5 & 3 & 7\\
8 & 7 & -2 & 6\\
\end{bmatrix}
</math>
имеет 1 седловой элемент, равный 4, который расположен в первой строке в третьем столбце матрицы, так как он одновременно является минимальным элементом в соответствующей строке матрицы (в данном случае в первой строке матрицы) и максимальным элементом в соответствующем столбце матрицы (в данном случае в третьем столбце матрицы).

Матрица
: <math>\begin{bmatrix}
2 & 3 & 5 & 2\\
2 & 4 & 6 & 2\\
-2 & 7 & 2 & 0\\
\end{bmatrix}
</math>
имеет 4 седловых элемента, равных 2, которые расположены в первой строке в первом столбце, в первой строке в четвёртом столбце, во второй строке в первом столбце, во второй строке в четвёртом столбце матрицы, соответственно.

Данный пример показывает, что матрица может иметь несколько (более одной) седловых точек.
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для поиска седловой точки в числовой матрице A. Седловой точкой называется элемент матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце. Алгоритм является прямым (не итерационным) и детерминированным. Его суть заключается в последовательном сканировании строк матрицы для поиска минимумов, а затем в проверке этих кандидатов на максимальность в соответствующих столбцах. В матрице может быть несколько седловых точек или не быть ни одной.

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

=== Математическое описание ===
Пусть задана матрица '''A''' размерности '''m x n''' (m строк, n столбцов).

Элемент '''Aij''' является седловой точкой, если выполняются два условия:

Он является минимальным элементом в своей строке i:

'''Aij = min Aik, k от 1 до n'''

Он является максимальным элементом в своем столбце j:

'''Aij = max Adj, d от 1 до m'''

Алгоритм можно описать как поиск таких индексов (i, j), для которых:

'''∀k: Aij ≤ Aik и ∀d: Aij ≥ Adj'''
=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит из двух последовательных этапов:

Поиск минимумов в строках, в котором для каждой строки i матрицы A последовательно сравниваются элементы Aij с текущим минимумом, и при нахождении меньшего значения обновляются минимальный элемент и его позиция столбец (d).

Проверка кандидатов в столбцах d, в котором для каждого найденного минимума строки последовательно сравниваются элементы Aid соответствующего столбца с кандидатом, и при обнаружении большего элемента проверка прекращается.
=== Макроструктура алгоритма ===
Алгоритм состоит из двух последовательных макроопераций:

1. Поиск минимума в каждой строке матрицы. Эта операция представляет собой цикл по всем строкам, внутри которого выполняется сканирование элементов строки.

2. Проверка найденных кандидатов на максимальность в их столбцах. Эта операция представляет собой цикл по всем строкам-кандидатам, внутри которого для каждого кандидата выполняется полный проход по его столбцу.

=== Схема реализации последовательного алгоритма ===
Для каждой строки i:

# Найти индекс позиции j минимального элемента строки.
# Проверить, является ли Ai,j максимальным в столбце j.
# Если да — вернуть (i,j) как седловую точку.
# Если ни для одной строки условие не выполнено — сообщить об отсутствии седловой точки.

=== Последовательная сложность алгоритма ===
Для матрицы размером '''m×n'''
 Поиск минимума в строке занимает — '''O(n)'''
 
Проверка максимума в столбце — '''O(m)'''
 
Итого на каждую строку — '''O(m+n)'''
 
Общая сложность — '''O(m(m+n))''', что при квадратной матрице '''n = m''' равно '''O(n^2)'''

=== Информационный граф ===
Информационный граф отражает две основные операции над каждой строкой: поиск минимума и проверку максимума в столбце. Между итерациями отсутствуют зависимости, параллелизм возможен по строкам.

Граф относительно прост и состоит из двух последовательных уровней вычислений для каждой строки.

* Уровень 1 (Поиск минимумов): m независимых вершин (по одной на каждую строку), каждая из которых выполняет операцию нахождения минимума в своем наборе данных (элементах строки) и номер его столбца d. Эти вершины не связаны между собой.

* Уровень 2 (Проверка кандидатов): m вершин (по одной на каждого кандидата). Каждая вершина i на этом уровне использует результат вершины i с первого уровня (столбец-кандидат) и требует данные всего столбца d из исходной матрицы для проверки на максимум. Вершины этого уровня также независимы друг от друга.

Связь между уровнями: Результат работы вершины i Уровня 1 (значение d) является входным данным для вершины i Уровня 2.

[[Файл: Graf sedl.png |500px|thumb|center|Граф поиска седловой точки матрицы]]

=== Ресурс параллелизма алгоритма ===
* Параллелизм на макроуровне (между строками): Поиск минимумов в строках может выполняться полностью параллельно. Все m задач Уровня 1 независимы. Аналогично, проверка всех m кандидатов на Уровне 2 также может выполняться параллельно.
* Параллельная сложность:
# При наличии m процессоров поиск минимумов во всех строках можно выполнить за O(n) времени (время обработки одной строки).
# Проверку всех кандидатов на наличие максимума в столбцах, при наличии m процессоров, можно выполнить за O(m) времени (время прохода по одному столбцу). Таким образом, общая параллельная сложность составляет O(n + m).
#Параллелизм реализуется на уровне итераций по строкам — независимые проверки каждой строки и связанных с ними операций.
Для матрицы большого размера этот подход позволяет ускорить алгоритм на многопроцессорных системах.
=== Входные и выходные данные алгоритма ===
'''Входные данные:''' Прямоугольная числовая матрица A размером m x n. Тип элементов - целый или вещественный. Особых свойств от матрицы не требуется.

'''Выходные данные:''' Координаты найденных седловых точек (i, j) или индикатор ее отсутствия (например, None).

=== Свойства алгоритма ===
* В матрице может быть несколько седловых точек или ни одной
* Алгоритм устойчив к дублирующимся значениям

== ''' Программная реализация алгоритма''' ==
=== 2.1 Особенности реализации последовательного алгоритма ===
def find_all_saddle_points_optimized(matrix):

if not matrix or not matrix[0]:
return []

m = len(matrix) # количество строк
n = len(matrix[0]) # количество столбцов

saddle_points = []

for i in range(m):
# Шаг 1: Находим все индексы минимальных элементов в строке i
min_in_row = matrix[i][0]
min_indices = [0]

for j in range(1, n):
if matrix[i][j] < min_in_row:
min_in_row = matrix[i][j]
min_indices = [j]
elif matrix[i][j] == min_in_row:
min_indices.append(j)

# Шаг 2: Для каждого минимального элемента проверяем,
# является ли он максимальным в своем столбце
for j in min_indices:
is_saddle = True
for k in range(m):
if matrix[k][j] > matrix[i][j]:
is_saddle = False
break

if is_saddle:
saddle_points.append({
'row': i,
'col': j,
'value': matrix[i][j]
})

return saddle_points

=== 2.2 Возможные способы и особенности параллельной реализации алгоритма===
def find_all_saddle_points_parallel(matrix):
if not matrix or not matrix[0]:
return []

m = len(matrix)
n = len(matrix[0])

def process_row(i):
"""
Обработка одной строки для поиска ВСЕХ потенциальных седловых точек
"""
row_results = []

# Находим все минимальные элементы в строке
min_in_row = matrix[i][0]
min_indices = [0]

for j in range(1, n):
if matrix[i][j] < min_in_row:
min_in_row = matrix[i][j]
min_indices = [j]
elif matrix[i][j] == min_in_row:
min_indices.append(j)

# Для каждого минимального элемента проверяем условие
for j in min_indices:
is_saddle = True
for k in range(m):
if matrix[k][j] > matrix[i][j]:
is_saddle = False
break

if is_saddle:
row_results.append((i, j, matrix[i][j]))

return row_results

# Параллельная обработка строк
saddle_points = []
with concurrent.futures.ThreadPoolExecutor(max_workers=min(m, 4)) as executor:
futures = [executor.submit(process_row, i) for i in range(m)]

# Собираем все результаты
for future in concurrent.futures.as_completed(futures):
row_results = future.result()
for result in row_results:
saddle_points.append({
'row': result[0],
'col': result[1],
'value': result[2]
})

return saddle_points

=== 2.3 Результаты прогонов ===
=== 2.4 Выводы для классов архитектур ===
== ''' Литература''' ==

Участник:Zerika

2025-12-09T13:58:57Z

Zerika: /* 2.1 Особенности реализации последовательного алгоритма */

Участник:Zerika

2025-12-09T13:49:37Z

Zerika: /* Свойства алгоритма */

Участник:Zerika

2025-12-09T13:43:20Z

Zerika: /* Свойства алгоритма */

Участник:Zerika

2025-12-09T13:42:39Z

Zerika: /* Свойства алгоритма */

Участник:Zerika

2025-11-04T18:03:29Z

Zerika: /* Входные и выходные данные алгоритма */

Участник:Zerika

2025-11-04T18:01:49Z

Zerika: /* Информационный граф */

Файл:Graf sedl.png

2025-11-04T17:57:03Z

Zerika: Граф алгоритма поиска седловой точки.

== Краткое описание ==
Граф алгоритма поиска седловой точки.

Участник:Zerika

2025-11-04T17:52:34Z

Zerika: /* Информационный граф */

Участник:Zerika

2025-11-04T17:23:47Z

Zerika: /* Схема реализации последовательного алгоритма */

Участник:Zerika

2025-11-04T17:23:07Z

Zerika: /* Схема реализации последовательного алгоритма */

Участник:Zerika

2025-11-04T17:14:42Z

Zerika: /* Свойства и структура алгоритма */

Участник:Zerika

2025-11-04T16:46:16Z

Zerika: /* Макроструктура алгоритма */

Участник:Zerika

2025-11-04T16:42:10Z

Zerika: /* Свойства и структура алгоритма */

Участник:Zerika

2025-10-31T22:37:16Z

Zerika: /* Свойства и структура алгоритма */

== '''Свойства и структура алгоритма''' ==
=== Общее описание алгоритма ===
Данный алгоритм предназначен для поиска седловой точки в числовой матрице A. Седловой точкой называется элемент матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце. Алгоритм является прямым (не итерационным) и детерминированным. Его суть заключается в последовательном сканировании строк матрицы для поиска минимумов, а затем в проверке этих кандидатов на максимальность в соответствующих столбцах. В матрице может быть несколько седловых точек или не быть ни одной.
=== Математическое описание ===
Пусть задана матрица '''A''' размерности '''m x n''' (m строк, n столбцов).

Элемент '''Aij''' является седловой точкой, если выполняются два условия:

Он является минимальным элементом в своей строке i:

'''Aij = min Aik, k от 1 до n'''

Он является максимальным элементом в своем столбце j:

'''Aij = max Adj, d от 1 до m'''

Алгоритм можно описать как поиск таких индексов (i, j), для которых:

'''∀k: Aij ≤ Aik и ∀d: Aij ≥ Adj'''
=== Вычислительное ядро алгоритма ===
Вычислительное ядро алгоритма состоит из двух последовательных этапов:

Поиск минимумов в строках, в котором для каждой строки i матрицы A последовательно сравниваются элементы Aij с текущим минимумом, и при нахождении меньшего значения обновляются минимальный элемент и его позиция столбец (d).

Проверка кандидатов в столбцах d, в котором для каждого найденного минимума строки последовательно сравниваются элементы Aid соответствующего столбца с кандидатом, и при обнаружении большего элемента проверка прекращается.
=== Макроструктура алгоритма ===
Алгоритм состоит из двух последовательных макроопераций:

2. Поиск минимума в каждой строке матрицы. Эта операция представляет собой цикл по всем строкам, внутри которого выполняется сканирование элементов строки.

1. Проверка найденных кандидатов на максимальность в их столбцах. Эта операция представляет собой цикл по всем строкам-кандидатам, внутри которого для каждого кандидата выполняется полный проход по его столбцу.
=== Схема реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
Поиск минимумов в строках: Требуется просмотреть каждый элемент матрицы ровно один раз. Сложность = O(m * n).

Проверка кандидатов: В худшем случае (когда все минимумы строк находятся в разных столбцах) требуется для каждой из m строк проверить m элементов в столбце. Сложность = O(m * m) = O(m^2).

Общая последовательная сложность: O(m * n) + O(m^2). В худшем случае, когда матрица квадратная (m = n), сложность составляет O(n^2) + O(n^2) = O(n^2)
=== Информационный граф ===
=== Ресурс параллелизма алгоритма ===
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма ===

== ''' Программная реализация алгоритма''' ==
=== 2.1 Особенности реализации последовательного алгоритма ===
=== 2.2 Возможные способы и особенности параллельной реализации алгоритма===
=== 2.3 Результаты прогонов ===
=== 2.4 Выводы для классов архитектур ===
== ''' Литература''' ==

Участник:Zerika

2025-10-30T18:49:32Z

Zerika: Создание страницы и внесение первых правок, резервное сохранение

== '''Свойства и структура алгоритма''' ==
=== 1.1 Общее описание алгоритма ===
Данный алгоритм предназначен для поиска седловой точки в числовой матрице A. Седловой точкой называется элемент матрицы, который одновременно является минимальным в своей строке и максимальным в своем столбце. Алгоритм является прямым (не итерационным) и детерминированным. Его суть заключается в последовательном сканировании строк матрицы для поиска минимумов, а затем в проверке этих кандидатов на максимальность в соответствующих столбцах. В матрице может быть несколько седловых точек или не быть ни одной.
=== 1.2 Математическое описание ===
Пусть задана матрица '''A''' размерности '''m x n''' (m строк, n столбцов).

Элемент '''Aij''' является седловой точкой, если выполняются два условия:

Он является минимальным элементом в своей строке i:

'''Aij = min Aik, k от 1 до n'''

Он является максимальным элементом в своем столбце j:

'''Aij = max Adj, d от 1 до m'''

Алгоритм можно описать как поиск таких индексов (i, j), для которых:

'''∀k: Aij ≤ Aik и ∀d: Aij ≥ Adj'''
=== 1.3 Вычислительное ядро алгоритма ===
=== 1.4 Макроструктура алгоритма ===
=== 1.5 Схема реализации последовательного алгоритма ===
=== 1.6 Последовательная сложность алгоритма ===
=== 1.7 Информационный граф ===
=== 1.8 Ресурс параллелизма алгоритма ===
=== 1.9 Входные и выходные данные алгоритма ===
=== 1.10 Свойства алгоритма ===
== ''' Программная реализация алгоритма''' ==
=== 2.1 Особенности реализации последовательного алгоритма ===
=== 2.2 Возможные способы и особенности параллельной реализации алгоритма===
=== 2.3 Результаты прогонов ===
=== 2.4 Выводы для классов архитектур ===
== ''' Литература''' ==