Практикум на ЭВМ

171 (2015/2016) группа

Максим Журавлев

Студент TODO №1 №2 №3 №4 Тест 1
17 1 2 3 4 5 1 2 3 4 5 6 1 2 Парикмахерская 2 Зачет
Калабкин Евгений
Кеворкянц Павел 16
Костицын Михаил
Костюков Юрий
Лебедев Михаил 1
Минаев Александр
Поляков Александр
Тюляндин Иван
Чернов Андрей
Шабанов Владимир

Задачи

Тест 1. 07.12.16
Вопросы к зачету
Короткое введение в многопоточное программирование - выступление на Java конференции
  1. Зачет
Домашняя работа 4. 07.12.16
  1. Парикмахерская

    В парикмахерской N мастеров, в вестибюле диван с K мест. Генерируются M событий "визит посетителя" со случайными промежутками времени.
    Если на диване есть свободные места, то посетитель садится и ожидает вызова к парикмахеру. Если мест нет, то визит не состоялся. Дождавшись вызова, посетитель проходит в зал на стрижку, которая занимает некоторое время, затем по команде парикмахера уходит. Парикмахеры либо ожидают посетителя, либо стригут.
    Примечание: проход прямо в зал при пустом диване и наличии свободного мастера невозможен.
    Для каждого посетителя и парикмахера свой поток.

    Реализовать, не используя готовую очередь. Допустимо использование Lock, Monitor, synchronized, ...

  2. При совершении каждого события добавлять строчку в log-файл.
    В качестве тестов написать программу анализа log-файла на корректность.
    Должны распознаваться, например, ошибки: переполненный диван, переполненный зал, два посетителя в одно время у одного парикмахера. Список не исчерпывающий.

Домашняя работа 3. 23.11.16
  1. В Scala для некоторых коллекций существуют "параллельные" версии. Их методы map, fold, filter и т.п. рассчитаны на исполнение в многопроцессорной среде т.е. в некоторых окружениях работают быстрее.
    Если метод принимает коллекцию типа GenSeq[T], то корректным аргументом будет как Seq[T], так и ParSeq[T].
    Преобразовать Seq в ParSeq можно, вызвав метод _.par.

    Реализовать алгоритм кластеризации k-средних для точек двумерного пространства.
    Сигнатуры методов:
    def generatePoints(k: Int, num: Int): Seq[Point] - генерирует множество точек,
    def initializeMeans(k: Int, points: Seq[Point]): Seq[Point] - выбирает k точек случайным образом для использования в качестве начальных центров кластеров,
    def findClosest(p: Point, means: GenSeq[Point]): Point - для точки находит ближайший из центров кластеров,
    def classify(points: GenSeq[Point], means: GenSeq[Point]): GenSeq[(Point, GenSeq[Point])] - возвращает последовательность из элементов (центр кластера, <точки, для которых этот центр ближайший>),
    def findAverage(oldMean: Point, points: GenSeq[Point]): Point - вычисляет новый центр кластера; если после classify в кластере нет ни одной, возвращается старое значение.
    def update(classified: GenSeq[(Point, GenSeq[Point])]): GenSeq[Point] - вычисляет новые центры кластеров,
    def converged(eta: Double)(oldMeans: GenSeq[Point], newMeans: GenSeq[Point]): Boolean - определяет, сошлись ли итерации (абсолютное изменение положения для каждого меньше eta -> true),
    @tailrec
    final def kMeans(points: GenSeq[Point], means: GenSeq[Point], eta: Double): GenSeq[Point] - вычисляет центры кластеров алгоритмом k-means.

  2. Провести измерения времени работы, использовав Seq[Point], затем ParSeq[Point] в качестве множества точек и начальных центров кластеров; вычислить ускорение.

Домашняя работа 2. 26.10.16
Introduction in parallel and distributed algorithms
  1. Ознакомиться со статьей. Изложен практически тот же материал, что и на предшествующих двух лекциях

  2. Реализовать алгоритм 3.3 (+ однопоточная версия)

  3. Упражнение 8. Найти решение. Реализовать (+ однопоточная версия).

  4. Упражнение 9. Найти решение. Реализовать (+ однопоточная версия).

  5. Упражнение 10. Найти решение. Реализовать (+ однопоточная версия).

  6. Произвести измерения времени работы
    - однопоточных версий,
    - многопоточных (n = 1, 2, 4, 8, ... количество ядер * 2)

Домашняя работа 1. 23.09.16
  1. Реализовать Blur фильтр в соответствие с описанием, которое будет дано в классе.

  2. Применить фильтр к изображению, используя несколько потоков параллельно, разбивая пиксели на горизонтальные и вертикальные полосы.

  3. Проанализировать влияние на ускорение количества потоков и направления разбиения. Для замеров использовать ScalaMeter.

  4. Снабдить реализацию Blur фильтра набором юнит тестов.

  5. Вывести изображение до применения фильтра и после, используя код рисования из прошлого семестра

© 2014-2018 HwProj