Задание 6 (индивидуальное): многопоточность

Указания

  • Необходимо выполнить задание в двух вариантах: при помощи интерфейсов Windows API и POSIX.
  • Необходимо реализовать задание в последовательном и многопоточном варианте, результаты сравнить между собой.

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

  2. Дан массив вещественных чисел, содержащий y0, y1, ..., yN — значения некоторой функции в точках x0, x0 + h, x0 + 2 h, ... (задано h, значение x0 не важно). Вычислить приближённые значения производной функции в этих точках по формулам:

    y'0 = (y1 - y0) / h,
    y'N = (yN - yN-1) / h,
    y'i = (yi+1 - yi-1) / (2 h).

    Разделить работу между n потоками. Каждый поток должен вычислить значения в заданном ему фрагменте массива.

  3. Дана матрица целых чисел, представляющая некоторое изображение. Получить по ней другую матрицу тех же размеров, представляющую размытый вариант изображения. Каждый элемент новой матрицы должен быть получен как среднее арифметическое значений элемента старой с теми же координатами и соседних с ним элементов (координаты которых отличаются от текущего не более, чем на 1). Разделить работу между n потоками. Каждый поток должен вычислить значения в заданной ему полосе матрицы.

  4. Задача "эволюция". Дано двумерное поле клеток, каждая из которых либо содержит организм (1), либо пуста (0). Каждая клетка проверяет состояние своих соседей (их 8) и изменяет своё по правилам:

    1. Живая клетка, вокруг которой < 2 живых клеток, умирает от одиночества.
    2. Живая клетка, вокруг которой есть 2 или 3 живых клеток, выживает.
    3. Живая клетка, вокруг которой > 3 живых клеток, умирает от перенаселения.
    4. Пустая клетка, рядом с которой равно 3 живых соседа, оживает.

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

  5. Заданы две матрицы вещественных чисел размеров N × N. Выполнить операцию умножения двух матриц в n потоках. Каждый поток должен обрабатывать заданный набор строк первой матрицы (и целиком вторую).

  6. Дана матрица, представляющая некоторое бинарное изображение (со значениями 1 — "есть цвет" и 0 — "нет"). Получить по ней другую матрицу тех же размеров, представляющую сглаженное изображение (без "пиков" и "зазубрин"). В новом изображении необходимо затемнить все светлые пиксели, у которых как минимум d соседей не освещены, и осветлить тёмные, у которых как минимум d соседей освещены. Разделить работу между n потоками. Каждый поток должен вычислить значения в заданной ему полосе матрицы.

  7. Даны два массив вещественных чисел одинаковой длины. Вычислить скалярное произведение векторов, представленных этими массивами, разделив работу между n потоками. Каждый поток должен выполнить вычисления в заданном ему фрагменте массивов.

  8. В двумерном массиве заданы значения вещественной функции от двух переменных в некоторой решётке. Выполнить поиск всех локальных максимумов заданной функции (локальным максимумом считать значение, большее своих восьми соседей. Разделить вычисления между n потоками. Каждый поток должен вычислить значения в заданной ему полосе массива.

  9. Для заданной квадратной вещественной матрицы проверить свойство доминирования её главной диагонали:

    | ai i | ≥ ∑ji | ai j | ∀ i

    Разделить вычисления между n потоками. Каждый поток должен вычислить значения в заданном ему диапазоне главной диагонали. Алгоритм можно оптимизировать, прекращая вычисления, когда какой-либо из потоков обнаруживает нарушение условия.

  10. Для заданной квадратной целочисленной матрицы проверить свойство персимметричности (симметричности относительно побочной диагонали):

ai j = an - j + 1, n - i + 1 ∀ i, j

Разделить вычисления между n потоками. Каждый поток должен вычислить значения в заданной ему полосе массива. Алгоритм можно оптимизировать, используя обработку половины матрицы, а также прекращая вычисления, когда какой-либо из потоков обнаруживает нарушение условия.

  1. Для заданной квадратной целочисленной матрицы проверить свойство диагональной постоянности: главная диагональ и все диагонали, параллельные главной, должны состоять из одинаковых (в пределах этой диагонали) значений. Разделить вычисления между n потоками. Каждый поток должен вычислить значения в заданном ему диапазоне диагоналей. Алгоритм можно оптимизировать, прекращая вычисления, когда какой-либо из потоков обнаруживает нарушение условия.

  2. Для заданной квадратной целочисленной матрицы проверить, является ли она магическим квадратом: должны совпадать суммы чисел в каждой её строке, каждом столбце, а также на главной и на побочной диагонали. Разделить вычисления между n потоками. Каждый поток должен вычислить значения в заданной ему горизонтальной и вертикальной полосах матрицы. Также первый поток может вычислять сумму элементов на главной диагонали, а последний "--- на побочной. Алгоритм можно оптимизировать, прекращая вычисления, когда какой-либо из потоков обнаруживает нарушение условия.