Ma'lumotlarning samarali turlari va algoritmlari kutubxonasi - Library of Efficient Data types and Algorithms

The Ma'lumotlarning samarali turlari va algoritmlari kutubxonasi (LEDA) a mulkiy litsenziyaga ega dasturiy ta'minot kutubxonasi ta'minlash C ++ turli xil dasturlarni amalga oshirish algoritmlar uchun grafik nazariyasi va hisoblash geometriyasi.[1] Bu dastlab tomonidan ishlab chiqilgan Maks Plank nomidagi informatika instituti Saarbruken.[2] 2001 yildan beri LEDA Algorithmic Solutions Software GmbH tomonidan yanada rivojlantirilib tarqatilmoqda.

LEDA bepul, tadqiqot va professional nashr sifatida mavjud. Bepul nashr bepul dastur, sotib olish uchun manba kodidan foydalanish imkoniyati mavjud. Tadqiqot va Professional nashrlar har qanday foydalanish uchun litsenziya to'lovlarini to'lashni talab qiladi. 2017 yil oktyabr oyidan boshlab LEDA grafik algoritmlari ham mavjud Java ishlab chiqish muhiti.

Texnik ma'lumotlar

Ma'lumot turlari

Raqamli tasvirlar

LEDA C ++ ga o'rnatilgan to'rtta qo'shimcha raqamlarni taqdim etadi: tamsayı, oqilona, katta dengizva haqiqiy. LEDA tamsayı turi o'rnatilgan narsalarga nisbatan yaxshilanishni taklif qiladi int muammoni yo'q qilish orqali ma'lumotlar turi toshib ketish tobora ko'payib borayotgan raqamlar uchun cheksiz xotiradan foydalanish evaziga. Shundan kelib chiqadiki, LEDA oqilona ning to'kilishiga qarshilik bir xil, chunki u to'g'ridan-to'g'ri matematik ta'rifiga asoslanadi oqilona ikkitasi sifatida tamsayıs. The katta dengiz turi C ++ suzuvchi nuqta turlariga ruxsat berish orqali yaxshilanadi mantissa quyidagilarga rioya qilish o'rniga o'zboshimchalik bilan aniqlik darajasiga o'rnatilishi kerak IEEE standarti. LEDA haqiqiy turi aniq tasvirlashga imkon beradi haqiqiy raqamlar, va radikal ifoda belgisini hisoblash uchun ishlatilishi mumkin.[1]

Tekshirishda xatolik yuz berdi

LEDA foydalanadi sertifikatlash algoritmlari funktsiya natijalarining matematik jihatdan to'g'ri ekanligini namoyish etish. Funktsiyaning kiritilishi va chiqishiga qo'shimcha ravishda, LEDA funktsiya natijasini tasdiqlash uchun tekshiruvchi dasturlarga kirish sifatida ishlatilishi mumkin bo'lgan uchinchi "guvoh" qiymatini hisoblab chiqadi. LEDA tekshiruvi dasturlari Simpl, an majburiy dasturlash tili va yordamida tasdiqlangan Izabel / HOL, matematik isbotlarning to'g'riligini tekshirish uchun dasturiy ta'minot.[3]

Guvoh qiymatining tabiati ko'pincha bajarilayotgan matematik hisoblash turiga bog'liq. LEDA-ning rejali sinash funktsiyasi uchun, agar grafik shunday bo'lsa planar, kombinatorial ko'mish guvoh sifatida ishlab chiqarilgan. Agar yo'q bo'lsa, a Kuratovskiy subgrafasi qaytariladi. Keyinchalik, ushbu qiymatlar tekshiruv funktsiyalariga to'g'ridan-to'g'ri ularning haqiqiyligini tasdiqlash uchun uzatilishi mumkin. Natija to'g'ri ekanligiga ishonch hosil qilish uchun ishlab chiquvchi faqat ushbu tekshirgich funktsiyalarining ichki ishlarini tushunishi kerak, bu esa LEDA ning planaritik sinov algoritmini to'liq anglash bilan taqqoslaganda o'rganish egri chizig'ini ancha pasaytiradi.[4]

Ishlardan foydalaning

LEDA bu sohada foydalidir hisoblash geometriyasi ning aniq vakolatxonalarini qo'llab-quvvatlashi tufayli haqiqiy raqamlar orqali leda_real ma'lumotlar turi. Bu aniqlikda ustunlikni ta'minlaydi suzuvchi nuqta arifmetikasi. Masalan, radikallar ishtirokidagi hisob-kitoblar yordamida hisoblashda ancha aniqroq leda_real. Kabi algoritmlar Parametrik qidirish, optimallashtirish muammolari to'plamini hal qilish texnikasi va boshqalar Haqiqiy RAM hisoblash modeli aniq natijalarga erishish uchun haqiqiy son parametrlariga tayanadi.[5]

Shu bilan bir qatorda

Boost va LIMON fundamental algoritmlar va ma'lumotlar tuzilmalarining turli xil tatbiq etilishi tufayli samaradorligi bo'yicha bir qator afzalliklarga ega bo'lgan muqobil kutubxonalar. Biroq, ikkalasida ham, masalan, suzuvchi nuqta arifmetikasi bilan ishlashda, to'g'riligini tekshirishning o'xshash to'plami ishlatilmaydi.[3]

Adabiyotlar

  1. ^ a b Mehlxorn, Kurt; Naxer, Stefan (1999), LEDA: Kombinatorial va geometrik hisoblash uchun platforma, Kembrij universiteti matbuoti, ISBN  978-0-521-56329-1.
  2. ^ "LEDA - Ma'lumotlarning samarali turlari va algoritmlari kutubxonasi". Stoni Bruk universiteti. Olingan 21 fevral 2019.
  3. ^ a b Abdulaziz, Muhammad; Mehlxorn, Kurt; Nipkov, Tobias (2019). "Ishonchli grafik algoritmlari". Rossmanitda Piter; Heggernes, Pinar; Katoen, Joost-Pieter (tahrir). 44-Xalqaro informatika matematik asoslari bo'yicha simpozium, MFCS 2019, 26-30 avgust, 2019, Axen, Germaniya. LIPIcs. 138. Schloss Dagstuhl - Leybnits-Zentrum für Informatik. 1-bet: 1-1: 22. arXiv:1907.04065. doi:10.4230 / LIPIcs.MFCS.2019.1.
  4. ^ Mehlxorn, Kurt; Näher, Stefan (1998), Brim, Lubosh; Gruska, Yozef; Zlatushka, Jiři (tahr.), "Algoritmlardan ishchi dasturlarga: LEDA da dastur tekshiruvidan foydalanish to'g'risida", Kompyuter fanining matematik asoslari 1998 yil, Springer Berlin Heidelberg, 1450, pp.84–93, doi:10.1007 / bfb0055759, ISBN  978-3-540-64827-7, olingan 2019-11-22
  5. ^ Mehlxorn, Kurt; Schirra, Stefan (2001). "Leda_real bilan aniq hisoblash - nazariya va geometrik qo'llanmalar" (PDF). Ramziy algebraik usullar va tekshirish usullari. Vena: Springer Verlag: 163–172. doi:10.1007/978-3-7091-6280-4_16. ISBN  978-3-211-83593-7.

Tashqi havolalar