Dərs vəsaiti baki -2018 azərbaycan döVLƏt neft və SƏnaye universiteti

0

3	0	7		1
4	6	0	9

4. Sütunlar üzrə minimumların tapılması. Hər bir j nömrəli sütun üzrə minimal elementləri (d_j) tapmalı: d₁= 0, d₂=0, d₃=1, d₄=0.

5.Sütunların reduksiyası. Hər sütunun bütün elementlərindən müvafiq d_j ədədlərinin çıxılması. Nəticədə hər sütunda ən azı bir ədəd sıfırdan ibarət xana olacaq.

Şəhərlər	1	2	3	4
1		0	5	4
2	3		0	0
3	0	7		1
4	6	0	8

6. “0” saxlayan xanaların yenidən qiymətləndirilməsi.

Özündə “0” saxlayan xananın yerləşdiyi sətrin minimal elementi ilə sütunun minimal elementinin cəmi həmin xanada sıfırın yanında mötərizədə qeyd edilir.
Bu xanaya uyğun müvafiq d_i, d_j ədədləri və həmin xananın “0” qiyməti bu hesablamada iştirak etmir.
Nəticədə bütün “0” saxlayan xanalar üçün aşağıdakı cədvəl qurulur:

Şəhərlər	1	2	3	4
1		0(4)	5	4
2	3		0(5)	0(1)
3	0(4)	7		1
4	6	0(6)	8

7. Matrisin reduksiyası.

“0” ədədlərinin yanındakı mötərizələrdə ən böyüyü hansıdırsa, onu « » ilə əvəz etmək. Bu xanaya uyğun (i,j) tilini minimal Hamilton konturuna məxsus element kimi yadda saxlamaq. Bizim misalda bu til (4,2) –dir.

Şəhərlər	1	2	3	4
1		0(4)	5	4
2	3		0(5)	0(1)
3	0(4)	7		1
4	6		8

Özündə iki ədəd « » işarəsi saxlayan sətir və sütunu cədvəldən silmək.

Şəhərlər	1	3	4
1		5	4
2	3	0(5)	0(1)
3	0(4)		1

8. Əgər axtarılan yolun bütün tilləri hələ qurulmayıbsa, biz 2-ci addıma qayıdıb bir sətri və bir sütunu silinmiş matris üzərində əvvəlki iterasiyanı yenidən təkrar edirik, sətirlər və sütunlar üzrə minimumları tapırıq, reduksiya edirik və s. Əgər bütün tillər tapılıbsa və ya aşkar şəkildə hələ tapılmasa da hansıların olacağı məntiqcə aydınlaşıbsa, 9-cu addıma keçirik.
9. Pərakəndə tapılmış tilləri montaj edərək ümumi konturu qururuq. Konturun davamiyyətini qiymətləndirmək üçün ilkin cədvəldə əks olunan informasiyadan istifadə olunmalıdır. Baxdığımız misalın pərakəndə tillərini birləşdirsək, 4 → 2 → 3 → 1 → 4 Hamilton konturu alınar ki, bunun davamiyyəti L = 30. Əgər 4 → 2 → 3 → 1 → 4 konturunun 1 → 4 → 2 → 3 →1 konturuna bərabər olduğunu nəzərə alsaq, bu nəticənin qeyri-aşkar ağac modeli əsasında alınan nəticə ilə eyni olduğunu görərik.


Ədəbiyyat

1. Kərimov V.Ə. Alqoritmlər nəzəriyyəsi. Dərs vəsaiti. Bakı. ADNSU- nun nəşri, 2017, 116 səh.

2.Hüseynov Ə.Ə. Diskret riyaziyyat. Dərs vəsaiti. Bakı, Çaşıoğlu, 2010, 408 səh.
3. Nabiyev V.V. Alqoritmalar: Teoriden Uygulamalara. Ankara: Seçkin, 2011, 829 səh.
4. Андерсон Дж.А. Дискретная математика и комбинаторика. : Пер. С англ.- М.: Издательский дом «Вильямс», 2004, 960 стр.
5. Ахо А., Хопкроп Д. Построение и анализ вычислительных алгоритмов. М.: Мир, 1980, 326 стр.
6. Дасгупта С., Пападимитриу Х., Вазирани У.-М.: МЦНМО, 2014, 320 стр.
7. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981, 368 стр.
8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.- М.: Мир, 1982, 191 стр.
9. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.: Мир, 1983, 456 стр.
10. Керимов В. А., Волкова Ю. В. Разработка и анализ алгоритмов, учебное пособие, Баку, АГНА, 2013, 107 стр.
11. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Р., Штайн К. Алгоритмы: Построение и анализ, 2-e изд. М.: Издательский дом “Вильямс”, 2012, 1296 стр.
12. Левитин А. В. Алгоритмы: введение в разработку и анализ. М.: Издательский дом “Вильямс”, 2006, 576 стр.
13. Мудров В. И. Задача о коммивояжёре. М.: Знание, 1969. 62 стр.
14. Рейнголз Э., Део Н. Комбинаторные алгоритмы. Теория и практика. Пер. с англ.- М.:Мир,1980, 415стр.
15. Седжвик Р. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск, СПб: ДиаСофт, 2001. 688 стр.
16. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford Introduction to Algorithms. Chapter 1: Foundations (Second ed.). Cambridge, MA: MIT Press and McGraw-Hill. pp. 3–122. ISBN 0-262-03293-7, 2001.
17. Donald E. Knuth.The Art of Computer Programming: Volume 1: Fundamental Algorithms. Third Edition xx+650pp. ISBN 0-201-89683-4, Reading, Massachusetts: Addison-Wesley, 1997.
18. Donald Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. ISBN 0-201-89685-0, Section 5.4: External Sorting, pp. 248–379. Addison-Wesley, 1998.
19. Drozdek, Adam Data Structures and Algorithms in C++ (4th ed.), Cengage Learning, p. 197, ISBN 9781285415017, 2012 .
20.Epp, Susanna. Discrete Mathematics with Applications (2nd ed.). pp. 427–430: The Tower of Hanoi,1995 .
21. Felleisen, Matthias. "Developing Interactive Web Programs". In Jeuring, Johan. Advanced Functional Programming: 4th International School. Oxford, UK: Springer. p. 108, 2002.
22.Goldreich, Oded. Computational Complexity: A Conceptual Perspective. Cambridge University Press. ISBN 978-0-521-88473-0, 2010. 
23. Sedgewick, Robert . Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-31452-6, 1998.
24. Steven S. Skiena. The algorithm design manual. ISBN:0387948600, Springer,1998, 504 p.
25. Wirth, Niklaus. Algorithms + Data Structures = Programs. Prentice-Hall, 1976, p. 126.
Nəşriyyatın direktoru: Xanlar Həsənli
Bilgisayar dizayn: İlqar Qədimov
Korrektorlar: Mehparə Baxşalıyeva
Təranə Haciyeva


Vaqif Əsəd oğlu Kərimov
ALQORİTMLƏRIN ANALİZİ VƏ HAZIRLANMASI ÜSULLARI (dərs vəsaiti)


Yığılmağa verilib: 15.12.17. Çapa imzalanıb: 17.01.18
Formatı: 60 90 1/16. Əla növ kağız. Ofset çap üsulu.
Şərti çap vərəqi: 11,5. Tirajı 200 nüsxə. Sifariş № 93
“Ləman Nəşriyyat Poliqrafiya” MMC-də çap edilmişdir