Все материалы

http://disk.tom.ru/sdftf3t

С 1-5 раньше выкладывала, если кто-то не скачал, http://disk.tom.ru/dbj7zjh

№1 

Написать программу выход из лабиринта с помощью алгоритма А*.

На экране произвольное поле с клеточками. Мышкой щелкаешь начало--конец, и находишь путь.

Должна быть возможнолсть отрисовки поля из текстового файла. Если чего еще вспомню по этой задаче напишу.

Задачи делать на любом языке.

№2 Дерево решений по набору данных с отсечением. На экране рисуем дерево. Берем a,b,c,d и находим решение на дереве, показать путь решения.

№3 Кластеризация данных

1. Реализовать алгоритм k-Means

-Из файла загружаем множесто точек (x, y). Отображаем их на экране.

-С клавиатуры ввели количество кластеров.

-Нашли N кластеров, раскрасили, центр кластера выделить.

-Вывели силуэт (простейшая мера).

-Ввели оценку качества диапозоном [N1;N2] и выводим наилучший кластер

2. Реализовать алгоритм иерархической кластеризации

как выражается Петраков, типо ползунка...На верху все кластеры видны...снизу один большой кластер.

№4 Нейронные сети, распознавание символов

Окошко, рисуем поле...

Мышкой рисуем букву и распознаем ее. Каждой букве будет соответсвовать  достоверность.

Система должна обучаться: подготавливаем  файлик, символу соответствует файлик с изображением.

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

Учитывать масштабирование (введенную букву нужно вписать и масштабировать, то есть размер обущающей и введенной должен совпадать в итоге)

+ нужно строить график в процессе обучения (количество итераций, уровень ошибок)

Всего будет 4 лабораторных работы.

Были:

1) Пожидаева Рената: 5

2) Штафун Александр: 4

Кто не был - 0.

Каждый сдает 3 лабораторные работы.

Договоритесь друг с другом кто какую делает так, чтобы задачи не повторялись.

ЛАБОРАТОРНЫЕ РАБОТЫ

ПО КУРСУ «ПАРАЛЛЕЛЬНОЕ И РАСПРЕДЕЛЕННОЕ ПРОГРАММИРОВАНИЕ»

1.  СИНХРОНИЗАЦИЯ ПОТОКОВ 

ЯЗЫКИ: С++, С#

1.1.  Задача обедающих философов.

За круглым столом сидят N философов. Между соседями лежит по вилке (всего N штук). Философ – это поток, который поочередно делает 2 действия: думает (функция think()) и ест (eat()). Чтобы поесть необходимо ложки (одна слева, одна справа).

Необходимо запрограммировать поведение потоков-философов так, чтобы они работали по возможности параллельно, не возникало тупиков, не возникало дискриминации (кто-то не может поесть очень долгое время). Функции think(), eat() могут занимать существенно разное время (для простоты, можно сделать там сортировку массива с случайной – каждый раз заново вычисляемой длиной).

1.2.  Задача «читатели-писатели»

N потоков «писателей» и M потоков-«читателей» обмениваются данными (сообщениями – фиксированной длины) через сравнительно небольшой буфер размером K сообщений. Для простоты – сообщение может быть одним целым числом.

int prepare_data() – подготовка данных «писателем» - возвращает сообщение (целое число).

void process_data(int data) – обработка данных «читателем».

Предполагается, что Prepare_data() и process_data() занимает значительное время, а процесс записи-чтения в буфер – сравнитеьлно небольшое.

Необходимо запрограммировать поведение потоков читателей-писателей, так чтобы они работали максимально параллельно (чтобы несколько читателей и писателей параллельно подготавливали и обрабатывали данные).

1.3.  Задача «спящий парикмахер»

Есть поток-парикмахер, который стрижет клиентов. Если в парикмахерской никого нет – парикмахер засыпает (от усталости). Приходит клиент – если парикмахер свободен - будит парикмахера. Если парикмахер занят – садится в кресло (таких K штук)и ждет своей очереди. Если все кресла заняты – уходит (от разочарования).

Запрограммировать повдение такой системы (поток парикмахер, N-потоков клиентов, которые «приходят» в парикмахерскую время от времени).

1.4.Команда потоков

Реализовать управление команды из N «рабочих» потоков и одного управляющего потока. Каждый рабочий поток может выполнять два задания taskOne(int x), taskTwo(int x). Выполнение каждого задания может занять существенно различное время, в зависимости от параметра x.

Управляющий поток генерирует набор независимых заданий размером K (состоящих из заданий taskOne(), taskTwo() со случайными параметрами) и выполняет их с помощью команды рабочих потоков за минимальное время.

2. OpenMP

ЯЗЫКИ: С/С++

2.1. Найти максимальный и минимальный элемент в массиве

2.2. Найти сумму элементов в массиве

2.3. Найти скалярное произведение двух векторов a и b длины N.

X = a[0]*b[0]+a[1]*b[1]+…+a[N]*b[N]

2.4.Линейный фильтр «размытие».

Дан исходный вектор a. На выходе получаем вектор b. b[i] = (a[i] + a[i+1] + … a[i+k])/k. Здесь k – параметр фильтра.

3. MPI

ЯЗЫКИ: С/C++

Сдается на кластере Cyberia.

Для удобства разработки и отладки дома можно использовать реализацию MPI в виде библиотеки MPICH2.

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

3.2. Умножение матрицы на вектор

3.3. Умножение матрицы на матрицу

3.4. Задача коммивояжера (полный перебор).

Пожидаева 1-4

Щукова 5-6

Коваленко 7-8

Штафун 9-10

Лежат здесь до 9 ноября

http://hdd.tomsk.ru/desk/xlauqofz

Пароль вы знаете :-)

Здравствуйте, Маги :-)

Для выполнения лабораторных заданий нужно получить доступ к кластеру SKIF Cyberia.

Заявление можно взять у меня, либо скачать:

http://skif.tsu.ru/doc/zayavlenie.doc

Потом - распечатываем, заполняем и принесим мне в ближайшую лекцию (2 ноября).

Кому нужно посмотреть, что вообще за предмет, http://disk.tom.ru/pw7y4rw

Написать программу выход из лабиринта с помощью алгоритма А*.

На экране произвольное поле с клеточками. Мышкой щелкаешь начало--конец, и находишь путь.

Должна быть возможнолсть отрисовки поля из текстового файла. Если чего еще вспомню по этой задаче напишу.

Задачи делать на любом языке.

На лекции (сказал Петраков) можно не ходить, зачет по лабораториям. Только вот одна проблемка, отловить его нет так просто:) Две пары, на которых была, заканчивались в пять.