Главная страница
Контакты

    Басты бет


Қазақстан Республикасы білім және ғылым министрлігі

жүктеу 438.69 Kb.



жүктеу 438.69 Kb.
бет4/4
Дата30.03.2017
өлшемі438.69 Kb.

Қазақстан Республикасы білім және ғылым министрлігі


1   2   3   4

сыйымдылығы қаншалықты.

Сыйымдылық (Емкость; capacity) - 1) компьютер жадына, сақтау құрылғыларына жазуға болатын мәліметтердің ең көп мөлшері (өлшем бірліктері: бит, байт, сөз немесе таңба). Биттермен, байттармен (Кб, Мб, Гб), символдармен немесе сөздермен өлшенеді; 2) байланыс арнасында - мәліметтер жеткізу (өткізу) мүмкіндігі (бір секундта өткізілетін мәліметтер көлемі); 3) машиналық сөздің немесе регистрдің ұзыңдығы.



  • Флойда алгоритмінің паралельдеу тәсілі неден тұрады?

  • Ағаштың минималды қамту тыпсырмасы неден тұрады? Тәжірибеда қолданылған тапсырмалар мысалын келтіріңдер.

  • Прима алгоритімінің жалпы схемасын келтіріңдер. Алгоритмнің жұмыс сыйымдылығы қаншалықты?

  • Прима алгоритімінің паралельдеу тәсілі неден тұрады?

  • Графтарды комбинатрикалық және геометриялық бөлудің айырмашылығы неде?

    Геометрия (көне грекше: γεωμετρία; көне грекше: γῆ - жер и көне грекше: μετρέω - «өлшеу») - математиканың кеңістіктік пішіндер (формалар) мен қатынастарды, сондай-ақ, оларға ұқсас басқа да пішіндер мен қатынастарды зерттейтін саласы.

    Қандай әдістер ерекше? Неге?

  • Координат бойынша бөлшектеу әдісіне және алгоритмдерді бөлуді байланысын ескере отырып, сипаттама бер. Бұл тәсілдердің қайсысы жүзеге асыру үшін қарапайым блып табылады?

    Тақырыптың қысқаша мазмұны (тезистер).

    Дәрісте графтарды өңдеуде типтік тапсырмаларды шешу үшін алгоритмдер қатары қарастырылған. Сонымен қатар, графтрады бөлу әдісіне шолу жасалған.

    Флойда алгоритіміне – келесі нұсқа әдісіне жалпы есептеу схемасы беріледі, оларды паралельдеу тәсілі талқыланады, алынған паралель есептеулерге эффектілік анализі жасалынады, әдістің бағдарламалық жүзеге асырылуы қарастырылып, есептелген тәжірибелер нәтижелері келтірілген. Қарастырылған Флойда алгоритіміне қолданылатын жақындаулар, процессорлар арасындағы граф төбелерін бөлуден тұрады, ал ақпараттық әрекет ету қажеттілігі, әрбір итерация әдісінде есептеу жүйесінің бір процессорынан барлық процессорға бір матрица жолының араласып берілуінен тұрады.

    Ағашты жаулаған, бейімделмеген өлшенген графтың минималды іздеу тапсырмасын шешу үшін Прима алгоритімі қарастырылған. Граф негізі деп қандай да бір минималды салмағы бар, ағымдағы граф пен қабырғаларының биіктігі анықталған және циклсіз байланысқан ішкі графтарды айтады. Алгоритмдер үшін оның келесі нұсқаларына жалпы сипаттамалар беріледі де, оның паралель орындау мүмкін тәсілдері, паралель есептеу эффектілігі және жылдамдығының теориялық бағалары анықталады; сонымен қатар, жасалған эксперимент есептеулерінің нәтижелері де қарастырылады. Прима алгортімінің паралель нұсқасы, алдыңғы жағдайдағы секілді ақпараттық әрекеттерге қатысты бірнеше үлкен көлемдерінде - әрбір алгоритм итерациясына бір процессорда мәліметтерді жинақтау операциясы және есептеу жүйесінің барлық процессоріне таңдалған граф биіктігін жіберу қажет болып табылатын, процессорлар арасындағы граф биіктігін бөлуге негіделген.

    Графтарды бөлу есебінің жалпы шешімі, паралель есептеуді қолданатын көптеген ғылыми зертеулер үшін маңызды болып саналады. Мысал ретінде бөлімде, бір өлшемді немесе екі өлшемді желіден сәйкес графқа есептеудің модельдеу процесіне көшудің жалпы тәсілі келтірілген. Графтарды бөлу тапсырмасын шешу үшін желіліреді бөлу кезінде тек желі туралы координаттық мәліметтерді қолданатын, геометриялық әдістер және граф төбелерін қиылыстырмайтын комбинаторикалық алгоритмдер қарастырылған.

    Координаттар (лат. co – бірге және ordіnatus – тәртіптелген, анықталған) - жазықтықтағы, кез келген беттегі не кеңістіктегі нүктенің орнын анықтайтын сандар. Ғылымға, ең әуелі, аспан сферасындағы не Жер шары бетіндегі нүктенің орнын (ендік пен бойлық) анықтайтын астрономиялыһ және географиялық кординаттар енді (қараңыз ).

    Қарастырылған геометриялық әдістер қатарына: координат бойынша бөлшектеу(the coordinate nested dissection method), тең бөлу әдісінің рекурсивті инерциясы(the recursive inertial bisection method), Пиано қисықтарын қолданумен желілерді бөлу (the space-filling curve techniques) жатады.

    Рекурсия (лат.recursioкейін кайту) - дыбыс артикуляциясынын үшінші сонғы фазасы, яғни сөйлеу мүшелерінін дыбыс жасау позициясынан айрылып, бастапқы бейтарап калпына кайта оралуы.. Жалпы мағынасында рекурсия - элементтерін өзіне ұқсас түрде қайталайтын процестер.

    Стырылған аогоритмдер қатарына: байланысты ескере отырып бөлу (the levelized nested dissection) және Кернигана – Лина алгоритімі(the Kernighan – Lin algorithm) жатады. Қарастырылған әдістерді реттеу үшін, орындалу уақыты бойынша, алынған шешімдердің дәлдігі, паралельдеу мүмкіндіктері және т.б алгоритмдердің жалпы салыстыру сипаттамалары жүргізіледі.
    Өзін - өзі тексеру сұрақтары:

    1. Бағдарламамен берілген кодтты қолдана отырып, Флойда паралельдеу алгоритімінің жүзеге асырылуын орындаңыз. Есептеу тәжірибелерін жүргізіңіз. Қолданған есептеу жүйесінің параметрлерін ескере отырып, теориялық бағалар жасаңыз. Тәжірибелік мәліметтер мен алынған бағаларды салыстырыңыз.

    2. Прима алгоритімінің паралельденуін жүзеге асырыңыз. Есептеу тәжірибелерін жүргізіңіз. Қолданған есептеу жүйесінің параметрлерін ескере отырып, теориялық бағалар жасаңыз. Тәжірибелік мәліметтер мен алынған бағаларды салыстырыңыз.

    3. Кернинг – Лина алгоритімінң жүзеге асырылу бағдарламасын құрыңыз. Бұл алгоритмнің паралельдеу мүкіндіктеріне баға беріңіз.
    Әдебиеттер:

    Флойда және Прима алгоритмдері бойынша ақпарат мысалы, [26] алынуы мүмкін.

    Графтарды бөлу мәселесімен байланысты қарастырылған сұрақтар, [21, 36, 37, 44, 53, 55, 58, 61, 65, 67] жұмысының құрамында.



    Графтарды бөлудің паралель алгоритімі [20, 38, 44, 48, 49, 65, 74] жұмыстарында қарастырылады.

  • 1   2   3   4


    жүктеу 438.69 Kb.