Параллельное программирование.

Список задач для цикла лабораторных работ.

1. Сортировка пузырьковая

2. Сортировка вставками

3. Сортировка выбором

4. Сортировка слиянием

5. Быстрая сортировка

6. Сортировка Шелла

7. Пирамидальная сортировка

8. Поразрядная сортировка

9. Вычисление определителя заданной матрицы

10. Вычисление обратной матрицы

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

12. Найти разреженную подматрицу заданного размера с максимальной суммой элементов в заданной матрице (разреженной называется подматрица, в которой индексы соседних элементов могут различаться более, чем на единицу, например, подматрица размерностью 3 строки на 4 столбца может быть задана совокупностью пар индексов: {{2:3, 2:5, 2:7, 2:8}, {3:3, 3:5, 3:7, 3:8}, 6:3, 6:5, 6:7, 6:8}}; в этих двухразрядных числах первая цифра пары – индекс строки охватывающей матрицы, вторая – индекс ее столбца)

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

14. Найти разреженную треугольную подматрицу заданного размера с минимальной суммой элементов в заданной матрице (разреженной называется подматрица, в которой индексы соседних элементов могут различаться более, чем на единицу, например, треугольная подматрица размерностью 4 строки на 4 столбца может быть задана совокупностью пар индексов: {{1:3},{2:3, 2:5}, {5:3, 5:5, 5:7}, 8:3, 8:5, 8:7, 8:8}}; в этих двухразрядных числах первая цифра пары – индекс строки охватывающей матрицы, вторая – индекс ее столбца)

15. Решение системы линейных алгебраических уравнений методом Гаусса

16. Решение системы линейных алгебраических уравнений методом Якоби

17. Решение системы линейных алгебраических уравнений методом Гаусса-Зейделя

18. Решение задачи движения N тел на плоскости с учетом сил гравитационного притяжения между ними; при упругих соударениях количество тел не меняется. Массы, радиусы, начальные координаты и векторы скоростей всех тел считать заданными. Вычислить координаты всех тел через время T.

19. Решение задачи движения N тел на плоскости; при некоторых упругих соударениях количество тел увеличивается (одно из тел разделяется на 2) с заданной вероятностью, иначе не меняется. Массы, радиусы, начальные координаты и векторы скоростей всех тел считать заданными. Вычислить координаты всех тел через время T.

20. Решение задачи движения N тел на плоскости с учетом сил гравитационного притяжения между ними; при неупругих соударениях количество тел уменьшается (тела слипаются) с заданной вероятностью. Массы, радиусы, начальные координаты и векторы скоростей всех тел считать заданными. Вычислить координаты всех тел через время T.

21. Решение задачи движения N тел в трехмерном пространстве с учетом сил гравитационного притяжения между ними; при упругих соударениях количество тел не меняется. Массы, радиусы, начальные координаты и векторы скоростей всех тел считать заданными. Вычислить координаты всех тел через время T.

22. Решение задачи движения N тел в трехмерном пространстве с учетом сил гравитационного притяжения между ними; при некоторых упругих соударениях количество тел увеличивается (одно из тел разделяется на 2) с заданной вероятностью, иначе не меняется. Массы, радиусы, начальные координаты и векторы скоростей всех тел считать заданными. Вычислить координаты всех тел через время T.

23. Решение задачи движения N тел в трехмерном пространстве; при неупругих соударениях количество тел уменьшается (тела слипаются) с заданной вероятностью. Массы, радиусы, начальные координаты и векторы скоростей всех тел считать заданными. Вычислить координаты всех тел через время T.

24. Вычислить распределение значений температуры в плоской прямоугольной области размером m * n. Теплопроводность материала области не равна нулю. Левая и нижняя граница области имеют температуру 0. Правый верхний угол имеет температуру T, значения температур правой и верхней границ равномерно убывают от T до 0.

25. Вычислить распределение значений температуры в плоской прямоугольной области размером m * n. Левая, нижняя и правая граница области имеют температуру 0. Точка, находящаяся в середине верхней грани, имеет температуру T. Температура точек верхней границы равномерно убывает от ее середины до краев. Теплопроводность материала области не равна нулю.

26. Вычислить распределение значений температуры в параллелепипеде размером k * m * n. Теплопроводность материала не равна нулю. Нижняя грань параллелепипеда имеет температуру 0. Геометрический центр верхней грани имеет температуру T₁, температура сторон этой грани равна T₂.

27. Вычислить распределение значений температуры в параллелепипеде размером k * m * n. Теплопроводность материала не равна нулю. Нижняя грань параллелепипеда имеет температуру 0. Одна из сторон верхней грани имеет температуру T₁, противоположная - температуру T₂.

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

29. Определить, изоморфны ли два заданных графа

30. Вычислить произведение двух заданных полиномов N переменных (например при N=4 вычислить результат умножения (x³yz²u⁴+2xy⁵z²–x⁴y²z²u) на (3y⁴zu – x⁷y³zu²+2x²y³zu²–5xz²u) )

31. Найти количество всех вхождений заданной подстроки в заданной строке (порядок следования символов важен, но символы подстроки в исходной строке не обязательно должны следовать друг за другом; например, в строке xxyzy подстрока xy встречается 4 раза, подстрока xz - 2 раза, подстроки xx, zy, yy и yz - по одному разу, а подстроки yx, zx и zz - ни разу)

32. Найти количество всех различных подстрок заданного размера в заданной строке с учетом порядка следования символов (например, строка xyxxz содержит подстроки x (3), y (1), z (1) размера 1, xy (1), xx (3), xz (3), yx (2), yz (1) размера 2, xyx (2) , xyz (1), xxx (1), xxz (3), yxz(2) размера 3, xyxx (1), xyxz (2), xxxz (1), yxxz (1) размера 4, xyxxz (1) размера 5; в скобках указано количество подстрок; других подстрок нет; таким образом, подстрок размера 1 ровно 5, размера 2 – 10, размера 3 – 9 и т.д.)

33. Любое число n, большее единицы, порождает последовательность вида:

n_i+1 = (n_i % 2 == 0? n_i / 2 : 3 * n_i + 1),

последним элементом которой является 1 (например: 13->40->20->10->5->16->8->4->2->1). Найти наибольшее, меньшее заданного N, число, порождающее самую длинную такую последовательность.

34. Любое число n, большее единицы, порождает последовательность вида:

n_i+1 = (n_i % 2 == 0? n_i / 2 : 3 * n_i + 1),

последним элементом которой является 1 (например: 13->40->20->10->5->16->8->4->2->1). Найти наибольшее, меньшее заданного N, число, порождающее последовательность заданной длины.

35. Любое число n, большее единицы, порождает последовательность вида:

n_i+1 = (n_i % 2 == 0? n_i / 2 : 3 * n_i + 1),

последним элементом которой является 1 (например: 13->40->20->10->5->16->8->4->2->1). Вычислить распределение длин таких последовательностей для чисел заданного интервала от N до M.

36. Любое число n, большее единицы, порождает последовательность вида:

n_i+1 = (n_i % 2 == 0? n_i / 2 : 3 * n_i + 1),

последним элементом которой является 1 (например: 13->40->20->10->5->16->8->4->2->1). Вычислить количество последовательностей заданной длины n среди чисел заданного интервала от N до M.

37. Найти максимальное число, меньшее заданного N, которое может быть представлено как сумма степеней 2, 3 и 4 различных простых чисел (минимальное такое число есть 50 = 5²+3³+2⁴)

38. Найти наименьшее число, большее заданного N, такое, что сумма всех компактных подпоследовательностей его десятичных цифр равна другому числу, возведенному в степень, большую 1 (для числа 1234 имеются следующие компактные подпоследовательности: 1, 2, 3, 4, 12, 23, 34, 123 и 234)

39. Найти наименьшее число, большее заданного N, такое, что произведение его десятичных цифр равно другому числу, возведенному в степень, большую 1

40. Найти первые N последовательно возрастающих на величину k чисел, больших заданного числа, все нетривиальные делители которых различны (например, два таких числа, возрастающих на 1 – это 14=2*7 и 15=3*5)

41. Найти максимальное простое число, меньшее заданного N, которое является суммой нескольких последовательно возрастающих простых чисел

42. Для заданного положительного числа N найти количество различных способов его получения в результате суммирования заданного количества k положительных целых чисел (например, 5=1+1+3=1+2+2 – итого 2 способа выразить 5 как сумму 3-х чисел).

43. Найти минимальное число, которое может быть разложено в сумму простых чисел не менее, чем N различными способами (например, для числа 10 существует ровно 5 таких способов: 10 = 7+3 = 5+5 = 5+3+2 = 3+3+2+2 = 2+2+2+2+2)

44. Для любого целого числа n обозначим через p(n) количество способов представления n в виде суммы целых положительных чисел (например, p(5) = 6, потому что 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1). Найти минимальное число n, для которого p(n) больше заданного N.

45. Найти максимальное число, меньшее заданного N, которое может быть представлено как сумма степеней 2, 3 и 4 простых чисел (минимальное такое число есть 28 = 2²+2³+2⁴)

46. Найти максимальное число, меньшее заданного N, которое равно сумме его десятичных цифр, возведенных в степень, большую 1

47. Найти наибольший палиндром (число, одинаково читающееся слева направо и справа налево), меньший заданного числа N, который является суммой квадратов последовательно расположенных чисел (например, число-палиндром 595 = 6²+7²+8²+9²+10²+11²+12²)

48. Близнецами называются простые числа, разница между которыми равна двум (например: 29 и 31, 41 и 43, …). Найти две соседние пары близнецов, расстояние между серединами которых больше заданного N (соседними называются такие пары, между которыми нет других близнецов)

49. Найти наименьшие целые числа x>y>z, большие заданного N, такие, что 5 из 6 значений вида x+y, x-y, x+z, x-z, y+z, y-z являются полными квадратами других чисел

50. Найти наибольшее простое число, меньшее заданного N, такое, что последовательность его десятичных цифр, записанных в каком-либо другом порядке, тоже является простым числом (таковыми являются, например, числа 31, 71, 137, …)

51. Найти наименьшее число, большее заданного N, такое, что сумма квадратов его десятичных цифр есть полный квадрат (например, таким является число 442: 4²+4²+2² = 36 = 6²)

52. Найти наименьшее число n, большее заданного M, имеющее точно такое же количество различных простых делителей, какое имеет число n+1

53. Найти в заданном диапазоне от N₁ до N₂ (N₂ > N₁) два простых числа, имеющие минимальное и максимальное значения произведений начала и конца своего десятичного представления (учитывать все возможные способы разбиения этого представления на две части)

54. Найти минимальное, большее заданного, число, которое равно сумме его десятичных цифр, возведенной в степень, большую 1 (например, 4913 = (4+9+1+3)³)

55. Найти наименьший палиндром (число, одинаково читающееся слева направо и справа налево), больший заданного N, который является произведением двух различных n-значных чисел

56. Найти минимальное число, большее заданного N, которое может быть представлено как сумма заданных (например 2, 3, 4, 5 или 3, 5, 7) степеней простых чисел (для первого набора степеней наименьшее такое число есть 60 = 2²+2³+2⁴+2⁵)

57. Найти наименьшее простое число, большее заданного N, которое является суммой заданного количества k последовательно возрастающих простых чисел

58. Найти минимальное число, большее заданного, которое может быть представлено как сумма степеней 2, 3, 4 и 5 различных простых чисел (наименьшее такое число есть 287 = 7²+5³+3⁴+2⁵)

59. Найти наименьшее число n, большее заданного N, для которого сумма любого его делителя d с результатом деления n/d является простым числом (таково число 30, имеющее делители 1, 2, 3, 5, 6, 10, 15, 30)

60. Найти наименьшие целые числа x и y, большие заданного N, такие, что значения вида x+y и x-y являются какими-либо степенями других чисел

(x - y = p^q и x + y = mⁿ).