20150406_msu06_Sort (1185572)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

МГУ ВМКЛекция 6Сортировка данныхс точки зрения МВСПараллельные алгоритмыЯкобовский Михаил Владимировичпроф., д.ф.-м.н.Институт прикладной математикиим. М.В.Келдыша РАН, Москва1Расположить в порядкенеубыванияN элементов массивачисел,,чиселиспользуя p процессоровМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.2К вопросу оНаилучшем последовательном алгоритме Медленном последовательном алгоритме Высокой степени внутреннего параллелизмаМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.3Две задачи сортировки массива чиселA.

Объём оперативной памяти одного процессорногоузла достаточен для одновременного размещенияв ней всех элементов массиваB. Объём оперативной памяти одного процессорногоузла мал для одновременного размещения в ней всехэлементов массиваМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.4Задача АРасположить N элементов массива a такимобразом, чтобы для любогоi  0,, N  2выполнялось неравенствоai  ai 1Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.5Задача BПусть массив можно разместить на p процессорах. Пусть на процессоре с номером rank размещеноn rank элементов массива a rank.Nrank pranknrank 0Расположить N элементов массивов a rank таким образом,чтобы:rank2– для любых rank  0,,  p  1 и i  0,, nвыполнялось неравенство a rank  a rankii 1– для любого rank  0,,  p  2– выполнялось неравенство a rank  a rank1n rank 1Москва, 2015 г.0Сортировка данных с точки зрения МВС © Якобовский М.В.6Задача BЧасти массива хранятся на несколькихпроцессорах– Каждая часть массива должна быть упорядочена– На процессорах с большими номерами должны бытьразмещены элементы массива с большимизначениями• ПравильноМосква, 2015 г.1,2,3,55,6,7,78,8,9• Ошибка1,2,3,55,7,6,78,8,9• Ошибка1,2,3,55,6,7,87,8,9Сортировка данных с точки зрения МВС © Якобовский М.В.N  11p37Задача BБудем рассматривать только процессупорядочивания элементов:– Перед началом сортировки на каждом из процессоровуже есть часть элементов массива– После окончания сортировки на каждом изпроцессоров должно остаться столько элементов,сколько их было в начале (но, это уже могут бытьдругие элементы, расположенные ранее на другихпроцессорах)Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.8Предлагаемая стратегия: Этапы сортировки– Упорядочивание фрагментов массива на каждом изпроцессоров– Перераспределение элементов массива междупроцессорамиМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.9Конструирование наилучшего последовательногоалгоритмаСравнение последовательных алгоритмов сортировкиM n  Cn 2АлгоритмсортировкиСреднее число операцийМаксимальное числооперацийБыстрая (qsort)11.7 n log2nO(n 2)Пирамидальная(hsort)16 n log2n18 n log2 n+ 38nСлияние списков(lsort)10 n log2nO(n log2n)Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.10Пусть f(N)<C∙g(N), нуи что?g(N)f(N)f(N)g(N)N0NГде тут наши 2 Гигобайта оперативной памяти???Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.11T=10-9Константа времени сортировкиKN log2(N)1409K(n)=10 T(n) / (n log2(n))Исходный массив не упорядоченD sort - слияние130Q sort - библиотечная процедура qsort120L sort - слияние списковH sort - пирамидальная сортировка110W sort - быстрая сортировка100Массив упорядоченWsort - быстраясортировка9080706050403020101001 00010 000100 0001 000 0001E71E8n - Размер массиваМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.12Пирамидальная сортировка: константы времени ичисла операцийисходный массив не упорядочен9K(n)= 10 T(n)/(n log2(n))R(n)= M(n)/(n log2(n))65605550исходный массивупорядочен по убываниюR(n)= M(n)/(n log2(n))45R(n), K(n)40Время работы алгоритмаопределяется:35• Числом операций сравнения иперестановки элементов массива302520T=10-9K1510• Временем обращения коперативной памяти(чтения и записи элементовмассива)n log2(n)M=10-9R n log2(n)501001 00010 000100 0001 000 0001E71E8n - Размер массиваМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.1325232119H17D15q13w119751.E+021.E+03Москва, 2015 г.1.E+041.E+051.E+06Сортировка данных с точки зрения МВС © Якобовский М.В.1.E+071.E+0814252321H_D19H17D15q13DHw119751.E+021.E+03Москва, 2015 г.1.E+041.E+051.E+06Сортировка данных с точки зрения МВС © Якобовский М.В.1.E+071.E+0815Меньше 10^5 - пирамидальная, больше - слияние25232119H_D17H15D13119751.E+021.E+03Москва, 2015 г.1.E+041.E+051.E+06Сортировка данных с точки зрения МВС © Якобовский М.В.1.E+071.E+0816Меньше 100 000 элементов – пирамидальная,иначе – (пирамидальная над фрагментами + слияние упорядоченных фрагментов)25232119H17D15DH13119751.E+021.E+03Москва, 2015 г.1.E+041.E+051.E+06Сортировка данных с точки зрения МВС © Якобовский М.В.1.E+071.E+081725232119q17w15DH13119751.E+021.E+03Москва, 2015 г.1.E+041.E+051.E+06Сортировка данных с точки зрения МВС © Якобовский М.В.1.E+071.E+0818Константа времени сортировки наилучшего алгоритма36Dsort - слияниеHsort - пирамидальнаясортировкаDHsort - оптимизированнаясортировка(слияние+пирамидальная)34302826249K(n)=10 T(n) / (n log2(n))32222018161001 00010 000100 0001 000 0001E71E8n - Размер массиваМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.19Сортировка слиянием методом сдваиванияТребуется 2 + 4 + 8 + 16 = 30 тактов (8 процессоров)5221957334403682исходный массив5221957334403682251259373404362812253759122357903448 процессоров2368023344684 такта8 тактов012223334456789ИТОГОМосква, 2015 г.2 тактаСортировка данных с точки зрения МВС © Якобовский М.В.16 тактов30 тактов20Изящный алгоритм сортировки массива слияниемсортировать ( массив mas, число элементов n ){если (n > 1){// сортировка первой половины массивасортировать ( mas, n/2);// сортировка второй половины массивасортировать ( mas+n/2, n-n/2);// слияние отсортированных половинок массиваслияние ( mas, n/2, mas+n/2,n-n/2);}}Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.21Нерекурсивный алгоритм сортировки массива слияниемDsort(intsort *array, int n){a=array;// сортируемый массивb=array_second;// вспомогательный массивfor(i=1;i<n;i=i*2) // размер объединяемых фрагментов{for(j=0;j<n;j=j+2*i) // начало первого из объединяемых// фрагментов{r=j+i; // начало второго из объединяемых фрагментовn1=max(min(i,n-j), 0);n2=max(min(i,n-r), 0);// слияние упорядоченных фрагментовb = a[r…r+n1] & a[j…j+n2]}c=a;a=b;b=c;}Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.22Слияние упорядоченных фрагментовfor(ia=0,ib=0,k=0;k<n1+n2;k++){if(ia>=n1) b[j+k]=a[r+ib++];elseif(ib>=n2) b[j+k]=a[j+ia++];elseif(a[j+ia]<a[r+ib]) b[j+k]=a[j+ia++];elseb[j+k]=a[r+ib++];}Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.23Слияние одним процессором.

Требуется 16 тактовОбращение к последовательным адресам памяти(1 2 2 3 5 5 7 9)12235579122355791223557912235579122355791223557912235579…Москва, 2015 г.(0 2 3 3 4 4 6 8)023344680233446802334468023344680233446802334468023344680010120122012230122330122333Сортировка данных с точки зрения МВС © Якобовский М.В.24Слияние двумя процессорами. Требуется 8 тактов1223557912235579122355791223557912235579122355791223557912235579Москва, 2015 г.0233446802334468023344680233446802334468023344680233446802334468090189012789012267890122256789012223556789012223345567890122233344556789Сортировка данных с точки зрения МВС © Якобовский М.В.25Ускорение при методе сдваиванияk1 – сортировка, k2 – передача данныхS n, p  T n,1k1n log 2 nT n, p  n  nk1  log 2  2 p  1  k 2 ( p  1)p p99S 10 ,4 41 k21.13 30 k1 3.532S 10 ,32  11k1 k2  3  2 56  31 1k130 k1 Москва, 2015 г.32Сортировка данных с точки зрения МВС © Якобовский М.В.26ПирамидыДерево называют сбалансированным, еслипотомки любого его корня отличаются по высотене более чем на 1 Пирамида – сбалансированное бинарное деревов котором левый потомок любого узла не нижеправого потомкаМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.27Не сбалансированное деревоМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.28Сбалансированное дерево, но не пирамида1248Москва, 2015 г.3569710 11 12 13Сортировка данных с точки зрения МВС © Якобовский М.В.29Пирамидаi1248592i310 1162i+1712Потомки вершины i хранятся в элементах 2i, 2i+1a1 a2 a3 a4 a5 a6 a7 a1 ai a3 a2i a2i 1 a6 a7 Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.30Упорядоченная пирамида9 58Москва, 2015 г.44671203352Сортировка данных с точки зрения МВС © Якобовский М.В.31Поменять корень местами с последним потомком9 58446712033529541Москва, 2015 г.842036572Сортировка данных с точки зрения МВС © Якобовский М.В.32Поменять корень местами с последним потомком2 584467120335[92541Москва, 2015 г.842036579Сортировка данных с точки зрения МВС © Якобовский М.В.33Вернуть остатку пирамиды упорядоченность2 584467120335[92541Москва, 2015 г.842036579Сортировка данных с точки зрения МВС © Якобовский М.В.34Вернуть остатку пирамиды упорядоченность8 524467120335[98541242036579Пирамида стала меньше и перестала быть упорядоченнойМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.35Вернуть остатку пирамиды упорядоченность8 524467120335[98541Москва, 2015 г.242036579Сортировка данных с точки зрения МВС © Якобовский М.В.36Вернуть остатку пирамиды упорядоченность8 574462120335[98541742036259Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.37Поменять корень местами с последним потомком8 574462120335[98541742036259Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.38Поменять корень местами с последним потомком8 574462120335[95541742036289Пирамида стала меньше и перестала быть упорядоченнойМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.39Вернуть остатку пирамиды упорядоченность5 57446212033[89554174206238Москва, 2015 г.9Сортировка данных с точки зрения МВС © Якобовский М.В.40Вернуть остатку пирамиды упорядоченность5 57446212033[89754154206238Москва, 2015 г.9Сортировка данных с точки зрения МВС © Якобовский М.В.41Вернуть остатку пирамиды упорядоченность7 55446212033[89754154206238Москва, 2015 г.9Сортировка данных с точки зрения МВС © Якобовский М.В.42Вернуть остатку пирамиды упорядоченность7 56445212033[89754164205238Москва, 2015 г.9Сортировка данных с точки зрения МВС © Якобовский М.В.43Пирамидальная сортировка – хаотичные обращения к памятименяем местами вершину пирамиды и последний элемент пирамиды9 5844671203352[восстанавливаем упорядоченность пирамиды2 588 5244674467120335[9120335[9меняем местами вершину пирамиды и последний элемент пирамиды8 574462120335[9восстанавливаем упорядоченность пирамиды5 577 557 56Москва, 2015 г.44624462445212033[8912033[8912033[89Сортировка данных с точки зрения МВС © Якобовский М.В.44Оптимальный алгоритмОптимальна комбинация: H алгоритм (пирамидальная сортировка)при n от 10 до 50 000 DH алгоритм (пирамидальная сортировка блоковразмером до 50 000 и их последующее слияние)при n больше 50 000пирамидальнаяпирамидальнаяпирамидальнаяслияниепирамидальнаяслияниеслияниеМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.45Константа времени сортировки наилучшего алгоритма36Dsort - слияниеHsort - пирамидальнаясортировкаDHsort - оптимизированнаясортировка(слияние+пирамидальная)34302826249K(n)=10 T(n) / (n log2(n))32222018161001 00010 000100 0001 000 0001E71E8n - Размер массиваМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.46Сеть сортировки (пузырёк) n=6 s=2n-3=9123456Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.47Сеть сортировки четно-нечетные перестановки n=6 s=n=6123456Шаги: 1Москва, 2015 г.2345Сортировка данных с точки зрения МВС © Якобовский М.В.648Сеть сортировки четно-нечетные перестановки n=6 s=n=6123456Шаги:123456nnnnO log 2  p    O log 2  n   On ppppTp  On Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.49Сеть сортировки n=6 s=6123456Шаги: 1Москва, 2015 г.2345Сортировка данных с точки зрения МВС © Якобовский М.В.650Минимальная сеть сортировки n=6 s=5123456Шаги: 1Москва, 2015 г.2345Сортировка данных с точки зрения МВС © Якобовский М.В.51Минимальные сети сортировкиn=10 s=7n=6 s=5n=12 s=8[Дн.Кнут]n=9 s=8n=16 s=9Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.52Четно-нечетное слияние Бэтчера – масштабируемая сеть2468913213571011121Москва, 2015 г.1146278899111110101112766712453104513532893131312Сортировка данных с точки зрения МВС © Якобовский М.В.1234567891011121353Сортировка массива из 15 элементовна основе четно-нечетного слияния Бэтчера715715782612128812121578346226269105610991091012157811441145139105135131113451112114114131113131433141415упорядоченные фрагменты- сеть четно-нечетного слияния БетчераМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.54Оценка числа тактовB(n)=B(n/2)+S(n)B(n)S(n)B(n/2)S(n/2)ВыполняютсяодновременноS(n)=S(n/2)+1S(n/2)B(n/2)Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.55Оценка числа последовательно расположенных группкомпараторовB(n)=B(n/2)+S(n)S(n)=S(n/2)+1Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.56Оценка числа последовательно расположенных группкомпараторовB(n)=B(n/2)+S(n)S(n)=S(n/2)+1Москва, 2015 г.S(n)=log2(n)Сортировка данных с точки зрения МВС © Якобовский М.В.57Оценка числа последовательно расположенных группкомпараторовB(n)=B(n/2)+S(n)S(n)=S(n/2)+1S(n)=log2(n)B(n)=B(n/2)+log2(n)Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.58Оценка числа последовательно расположенных группкомпараторовB(n)=B(n/2)+S(n)S(n)=S(n/2)+1S(n)=log2(n)B(n)=B(n/2)+log2(n)B(n)= log2(n) (log2(n)+1) / 2Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.59Оценка числа последовательно расположенных группкомпараторовB(n)=B(n/2)+S(n)S(n)=S(n/2)+1S(n)=log2(n)B(n)=B(n/2)+log2(n)B(n)= log2(n) (log2(n)+1) / 2log 2 p  log 2 p   1sp 2Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.60Сортировка восьми элементовили2nnlogp2O log 2 pp2 n элементов восемью процессорами- сеть четно-нечетного слияния БетчераМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.61Пример работы алгоритмаНачало, массив распределен по процессорам874392512406874392512406Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.62Сортируем фрагменты874392512406239125046478239125046478Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.63Первые два компаратора слияния перестановки478239478239125046234Москва, 2015 г.125046234789012456789012456Сортировка данных с точки зрения МВС © Якобовский М.В.64Вторая пара компараторов слияния перестановки234789234789012456012Москва, 2015 г.012456012456234789456234789Сортировка данных с точки зрения МВС © Якобовский М.В.65Последний компаратор слияния перестановки012456234012456234789012789012234456789234456789Массив упорядоченМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.66Ограничение метода:Сортировка блоков – ОДИНАКОВОГО РАЗМЕРА123456Шаги: 1Москва, 2015 г.23456Сортировка данных с точки зрения МВС © Якобовский М.В.67Слияние упорядоченных фрагментов// объединить два упорядоченных массива a,bfor(ia=0,ib=0,k=0;k<n1+n2;k++){if(ia>=n1) c[k]=b[ib++];elseif(ib>=n2) c[k]=a[ia++];elseif(a[ia]<b[ib]) c[k]=a[ia++];elsec[k]=b[ib++];}Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.68Слияние упорядоченных фрагментовfor(ia=0,ib=0,k=0;k<n;k++){if(ia>=n1) c[k]=b[ib++];elseif(ib>=n2) c[k]=a[ia++];elseif(a[ia]<b[ib]) c[k]=a[ia++];elsec[k]=b[ib++];}rank1, a[n]rank2, b[n]// n – число элементов в каждом из массивов a,bМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.69Слияние упорядоченных фрагментовfor(ia=0,ib=0,k=0;k<n;k++){rank1, a[n]rank2, b[n]if(a[ia]<b[ib]) c[k]=a[ia++];elsec[k]=b[ib++];}// n – число элементов в каждом из массивов a,bМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.70Слияние упорядоченных фрагментовJoin(int *a, int *b, int *c, int n,rank1,rank2){if(rank==rank1)for(ia=0,ib=0,k=0;k<n;){if(a[ia]<b[ib]) c[k++]=a[ia++];elsec[k++]=b[ib++];}elsefor(ia=n-1,ib=n-1,k=n-1;k>=0;){if(a[ia]>b[ib]) c[k--]=a[ia--];elsec[k--]=b[ib--];}}Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.rank1rank271Реализация компаратора слияния// взаимодействие процессоров rank и rankCint *a,*b,*c,*tmp;ASend(a,n,rankC);ARecv(b,n,rankC);ASync();Join(a,b,c,n, rank, rankC);tmp=a;a=c;c=tmp;Москва, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.72Сортировка семи элементовМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.73Разделить на две группыМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.74Снова разделить каждую группуМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.75Сортировать каждый короткий фрагментМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.76Сортировать нечетные строки в каждом из фрагментовМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.77Сортировать четные строки в каждом из фрагментовМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.78Объединить отсортированные четные и нечетные строкив каждом фрагментеМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.79Объединить два отсортированных фрагментаМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.80Объединить четные строки отсортированных фрагментовМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.81Объединить нечетные строки отсортированныхфрагментовМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.82Замыкающая цепочка компараторовМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.83Полная сеть сортировкиМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.84Полная сеть сортировки, такты выполненияМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.85Сортировка восьми элементовили2nnlogp2O log 2 pp2 n элементов восемью процессорами- сеть четно-нечетного слияния БетчераМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.86n=108EP123456781627324864128192256384512640Москва, 2015 г.T,сек83.5146.4035.9329.6824.4522.1621.8219.9512.369.327.856.454.923.192.521.991.631.291.21maxlog 2 n1n, p  log 2 n  s p  log 2 p 1  log n p(log 2 p  1) / 2E100.00%90.00%77.48%70.35%68.33%62.80%54.67%52.32%42.22%33.20%33.24%26.97%26.53%20.47%17.29%16.41%13.33%12.64%10.78%S1.001.802.322.813.423.773.834.196.758.9710.6412.9516.9826.2033.1942.0251.2064.7469.02Emax100%100%95%96%91%92%89%90%82%74%73%66%64%56%51%49%49%42%41%Smax1.02.02.83.94.55.56.27.213.120.023.331.940.971.598.2124.6187.0217.4264.7sp013355661014151921283336414547log 2 p  log 2 p   1sp 2Сортировка данных с точки зрения МВС © Якобовский М.В.87ЗаключениеРассмотрен ряд методов сортировки массивов Проиллюстрирована разница междузависимостью от объема данных временисортировки и числа выполняемых операций Построен «наилучший» последовательныйалгоритм сортировки Рассмотрены сети сортировки Построен параллельный масштабируемыйалгоритм сортировкиМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.88КонтактыЯкобовский М.В.проф., д.ф.-м.н.,зав.

сектором«Программного обеспечения многопроцессорныхсистем и вычислительных сетей»Института прикладной математики им.М.В.Келдыша Российской академии наукmail: lira@imamod.ruweb: http://lira.imamod.ruМосква, 2015 г.Сортировка данных с точки зрения МВС © Якобовский М.В.89.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций