Задача по распараллеливанию операций и не только

[Dianelli]

Пожалуйста, помогите решить задачи для 11 класса:

Задача 1)
Дан следующий пример:
есть массив из 100 чисел: a1, a2, ..... a100. Решаем классом из 25 человек.
Последовательность действий:
1) Объединить числа в пары - по 2 на каждого ученика (итого распределим 50 чисел)
2) Дать команду "Складывай" - Каждый записывает свои числа.
3) Дать команду "Записывай!" - Каждый записывает мелом на классной доске свой результат.
4) Т.К. осталось 50 необработанных чисел, повторить пп. 1-3. После этого имеем на доске 50 чисел: b1=a1+a2,...b50=a99+a100.
5) Объединить в пары числа Bi и повторить пп. 2-4, пока не останется одно число.

Для примера со сложением чисел 25 учениками попробуйте проанализировать следующие ситуации: в классе всего 1 кусок мела; в классе 5 кусков мела; в классе 25 кусков мела. Оцените, как от этого зависит время решения задачи (учтите ещё ширину доски и время перемещения учеников по классу) Попробуйте построить модель такого процесса. Переведите эту ситуацию на язык компьютерной терминологии для многопроцессорных систем.

Задача 2)
Попробуйте привести примеры алгоритмов поиска информации в массиве и сортировки массива, которые допускают распараллеливание операций. Опишите процедуру распараллеливания. Сколько процессоров необходимо для эффективного распараллеливания в приведённом вами примере?

Я в информатике не понимаю вообще ничего, поэтому буду очень благодарна за помощь. На вас надеется весь 11"А")))

[Dianelli]

Это очень срочно =(((

[Abstraction]

Если очень срочно, то вот достойная книжка. Быстрее консультироваться с книгой, чем с форумом.

Если не очень, то приведите свои рассуждения - как Вы представляете действия и расклады в задаче 1; скажите, какие алгоритмы сортировки Вам известны (это уже насчёт задачи 2).

[Dianelli]

Я написала про сам процесс. что ученики это процессоры. мел - шины, а доска и кабинет - оперативная память. Понятно, что, к-во мела и скорость процесса находятся в прямо пропорциональной зависимости: чем меньше мела, тем медленнее пойдёт процесс, т.к.если считать, что все ученики подойдут к доске одновременно (можно ли так считать??), если у каждого будет по куску мела, они запишут цифры в 25 раз быстрее, чем если бы был 1 кусок, и в 5 раз быстрее, чем если бы было 5 кусков.

[Dianelli]

Как построить модель, я не очень представляю, требуется блок-схема.

[Dianelli]

Методы внутренней сортировки
1. Сортировка включением
2. Обменная сортировка
3. Сортировка выбором
4. Сортировка разделением (Quicksort)
5. Сортировка с помощью дерева (Heapsort)
6. Сортировка со слиянием
7. Сравнение методов внутренней сортировки

Методы внешней сортировки

1. Прямое слияние
2. Естественное слияние
3. Сбалансированное многопутевое слияние
4. Многофазная сортировка
5. Улучшение эффективности внешней сортировки за счет использования основной памяти

[Dianelli]

Сортировка с помощью дерева (Heapsort)
Сортировка со слиянием

Сбалансированное многопутевое слияние
Многофазная сортировка

допускают распараллеливание операций, так?

[Son Of Pain]

Обычная quick sort распараллеливается. Ну еще сортировка Бэтчера, например.
Поиск можно взять даже обычный линейный, разбив диапазон на куски.

Вообще плохо понятно, что тебе нужно. Если просто написать много страшных названий алгоритмов в столбик - берешь любую толстую книжку, находишь там раздел parallel sort и переписываешь оглавление. Если же про эти алгоритмы еще и вопросы задавать будут - тогда случится фэйл, конечно; потому лучше взять пару самых простых и разобраться в них.

Теперь во всех школах такая суровая программа по информатике?

[Dianelli]

У нас просто информатичка сперва ничего не объясняет, а потом вот такое спрашивает...

у меня нет толстой книжки(( похоже, нужен просто примитивный пример. Я уже всё облазила, но везде пишут слишком сложно. не могу продраться сквозь страшную терминологию и запутанные объяснения... Если есть время, накидайте, плизззззззз, примерный ответ, или можно ссылку на то, как описать распараллеливание операций

[Dianelli]

задавать вопросы вряд ли будут. И потом, как определить, сколько процессоров необходимо для эффективного распараллеливания в приведённом примере...