вторник, 11 марта 2014 г.

Программирование

Сегодня вёл очередную практику по параллельному программированию и занятие по алгоритмам и структурам данных (замещал уехавшего в командировку преподавателя).

На параллельном программировании решали задачи. С заданиями можно ознакомиться тут: http://rain.ifmo.ru/~lukinma/parallel14.htm.

Запись занятия для интересующихся можно найти тут: http://yadi.sk/d/-kCkRivVKKtKh
Мы сначала провели тест на знание алгоритмов поиска в ширину и в глубину, а затем решали задачи по книге Кормен, Ривест, Лейзерсон "Алгоритмы: Построение и анализ".




Если кому интересен тест, то он такой:

Вопрос 1. Требуется определить, связаны ли две заданные вершины ребром. Какой способ представления графа позволяет сделать это быстрее?

(А) Списки смежности
(Б) Матрица смежности
(В) Скорость не зависит от способа представления

Вопрос 2. Какая структура данных занимает меньше памяти в случае хранения разреженных графов (графов, число ребер в которых много меньше квадрата числа вершин)?

(А) Списки смежности
(Б) Матрица смежности
(В) Объем памяти одинаков для обеих структур данных

Вопрос 3. Какова скорость работы поиска в ширину, если V -- число вершин в графе, E -- число ребер?

(А) O(V*E)
(Б) О(V^2)
(В) O(V + E)

Вопрос 4. В процессе поиска в глубину еще не посещенные вершины окрашены в белый цвет, при первом посещении вершина окрашивается в серый цвет, после завершения сканирования списка смежности вершины она становится черной. В каком случае можно сделать вывод о том, что в графе присутствует цикл?

(А) Обнаружено ребро из черной вершины в белую
(Б) Обнаружено ребро из серой вершины в белую
(В) Обнаружено ребро из серой вершины в серую

Вопрос 5. Дан ориентированный невзвешенный граф с циклами. Какой алгоритм можно использовать для поиска кратчайшего пути в таком графе?

(А) Поиск в ширину
(Б) Поиск в глубину
(В) Ни один из названных алгоритмов

Комментариев нет:

Отправить комментарий