- 1987 yilda Stiv Forchun O (n * log (n)) diagramma algoritmini taklif qildi. Albatta, bu asimptotikalar bilan yagona qurilish algoritmi emas, lekin uni amalga oshirish juda aniq (va bundan tashqari, bu juda chiroyli va matematik!).
- Forchun algoritmiga oid materiallarni bu yerda topish mumkin.
- Shunday qilib, algoritmning asosiy g'oyasi "supurish chizig'i“ (sweep line) deb nomlangan. U hisoblash geometriyasining ko'plab algoritmlarida qo'llaniladi, chunki u sizga to'g'ri chiziqning harakatini ma'lum bir ob'ektlar to'plami bo'ylab qulay tarzda simulyatsiya qilishga imkon beradi (masalan, n segmentlarni kesish algoritmida ham supurish chizig'i qo'llaniladi).
Qanday qilib va nima qilishimiz haqida suhbatni boshlashdan oldin, keling, sweep line qanday harakatlanishini ko'rib chiqaylik. - Qanday qilib va nima qilishimiz haqida suhbatni boshlashdan oldin, keling, sweep line qanday harakatlanishini ko'rib chiqaylik.
- Amalga oshirishda hamma narsa bir xil, faqat sweep line odatda chapdan o'ngga emas, balki yuqoridan pastga qarab harakat qiladi va aslida hamma narsa unchalik silliq emas, balki hodisadan hodisaga o’tadi, ya'ni , diskret ravishda.
Foydalanilgan adabiyotlar
Asosiy:
- Кормен Т., Лейзерсон Ч., Ривест Р. «Алгоритмы.
Построение и анализ», 2013 г.
Qo’shimcha:
1. Г.Шилтд Самоучитель С++. 5-е издание. “БХВ Петербург” 2010 г.
2. Колдаев Основы_алгоритмизации_и программирования. 2013 г.
3. Род Хаггарти «Дискретная математика для программистов» 2012 г.
4. Томас Х. Кормен «Алгоритмы. Вводный курс» 2014 г.
5. Г.Уоррен «Алгоритмические трюки для программистов», 2014 г.
THANK YOU
that you took the time to watch
ALGORITMLARNI LOYIHALASH
Algorithm Design
Do'stlaringiz bilan baham: |
