TTT

Ko'paytirish 2!
Ikkita butun sonni ko'paytirish algaritmi haqida gaplashgan edik. Endi matritsalar uchun shu masalani qarab chiqamiz:
Bizga A va B - n×n matritsalar berilgan bo'lsin. Bilamizki A×B ni topish uchun ularning elementlari ustida jami n³ marta ko'paytirish amalini bajarishimiz kerak. Bu esa n 1 ga oshganda ko'paytirish amallari soni 3n²+3n+1 ga oshadi degani (n 2 marta oshganda ko'paytirish amallari soni 8 marta oshadi!)
Yuqoridagidan, n=2 da A×B ni topish uchun 8 ta ko'paytirish amali bajarishimiz kerakligini ko'rishimiz mumkin. Buni 1969 yilda 7 ta amalga tushirishgan, va 1970 yilda ko'paytirishlar sonini 6 va undan kamiga tushirish mumkin emasligi isbotlangan. Bitta kamayganini nima axamiyati bor deysizmi? n=8 da A va B ni 2×2 lik blok matritsalarga ajratib, keyin A×B ni yangi algaritmni ketma-ket 3 marta qo'llash orqali 7³ yoki 343 marta ko'paytirish amali orqali topishimiz mumkinligi kelib chiqadi. Odatiy usulda esa 8³ yoki 512 ta amal edi. Demak ~33% kam ko'paytirish amalini bajaramiz.

TTT

Assalomu alaykum azizlar!
Telegramda matematikaga doir ma'lumot yozmoqchi bo'lsam, uni dastlab boshqa dasturda zarur ko'rinishga keltirib keyin rasm yoki pdf yoki video ko'rinishida e'lon qilishim kerak edi. Bundan tashqari materiallarni unumli guruhlash imkoniyati yo'q (albatta Telegramni vazifasi boshqa). Shuning uchun aynan fan doirasida ma'lumotlar uchun mo'ljallangan mobil dastur yaratishga qaror qilgandik. Bu orqali Respublika bo'yicha professional mutaxassislarni bitta universal platformaga yig'ishni niyat qilganmiz (buning samarasini yuqorida keltirib o'tganman).
Umid qilaman boshlagan ishimiz barchamizga manfaatli bo'ladi!

Foydali materiallarga havolalar:
> Aniq integrallarga doir tengsizliklar;
> Aniq integral uchun Koshi-Shvarz tengsizligi Ex3;
> Aniq integral uchun Koshi-Shvarz tengsizligi Ex4;
> Aniq integral uchun Koshi-Shvarz tengsizligi Ex5-6;
> Aniq integrallar uchun Gyolder, Chebishev tengsizliklari;
> The Chebyshev Polynomials;
> Sonli ketma-ketliklarda ikkita hadi uchun berilgan munosabatga ko'ra uning umumiy hadini topish;
> Sonli ketma-ketliklarda ikkita hadi uchun berilgan munosabatga ko'ra uning umumiy hadini topish 2.b;
> Mantiqiy masalalarni yechishning bir usuli;
> To'plamlarga doir bazi olimpiada masalalari;
> Ptolomey va Paskal teoremalarining turli isbotlari;
> Coefficients and roots of polynomials;
> Uchburchak ichida olingan nuqtaga ko'ra hosil qilingan tenglik va tengsizliklarni isbotlash;
> Density of a set in an interval;
> To'rtta nuqtaning o'zaro garmonik munosabatiga doir xossalarni geometrik masalalarni isbotlashda qo'llanilishi;
> 2015 yil olimpiadalari;
> Matrix problems;
> 2008-2017 yillarda viloyat, Respublika, XMO saralash olimpiadalari masalalari;
> Viloyat olimpiadasi testlari;
> Uchburchak va aylanalar;
> Trigonometrik tengsizliklarni vektorlar yordamida isbotlash;
> Qavariq to'rtburchakning diagonallari perpendikulyar bo'lishi uchun zarur va yetarli shartlar;
> To'rtta nuqtaning bitta aylanada yotishini isbotlashga doir masalalar;
> Ichki-tashqi aylana radiuslari uchun bir nechta munosabatlar;
> Masalalarni blok matritsa qurish yordamida yechish;
> Ko'phadning haqiqiy ildizga ega bo'lishiga doir masalalarni yechish;
> FMI maqolalar;

Quyida o'zim foydalangan kitoblar, video darslar, veb saytlar va youtube kanallar (ustiga chizilgani tugatilmagan, Udemyda kurslar 11-15$ atrofida, LinkedIn da lab studentlari uchun tekin edi):

1. Y. Daniel Liang - Introduction to Java programming, Tenth Edition (book)

2. Herbert Schildt - Java: The Complete Reference, Eleventh Edition (book)

3. Tim Buchalka - Java Programming Masterclass covering Java 11 & Java 17 (80.5 hours, Udemy)

4. Jose Portilla - The Complete SQL Bootcamp 2022: Go from Zero to Hero (9 hours, Udemy)

5. Miki Tebeka - Learning Vim (1 hour 16 min, LinkedIn)

6. Kevin Skoglund - Git Essential Training: The Basics (2 hours 55 min, LinkedIn)

7. Kevin Skoglund - Git Intermediate Techniques (2 hours 53 min, LinkedIn)

8. Kevin Skoglund - Git: Branches, Merges, and Remotes (3 hours 3 min, LinkedIn)

9. Benjamin Muschko - Learning Groovy (1 hour 10 min, LinkedIn)

10. Benjamin Muschko - Learning Gradle (51 min, LinkedIn)

11. Benjamin Muschko - Gradle for Java-Based Applications and Libraries (57 min, LinkedIn)

12. Chad Darby - Spring & Hibernate for Beginners (includes Spring Boot) (42.5 hours, Udemy)

13. Chad Darby - JSP, Servlets and JDBC for Beginners: Build a Database App (9 hours, Udemy)

14. Ketkee Aryamane - Spring: Spring MVC (5 hours 30 min, LinkedIn)

15. Shonna Smith - Spring: Test-Driven Development with JUnit (1 hour 12 min, LinkedIn)

16. David Gassner - Java: Database Integration with JDBC (2 hours 51 min, LinkedIn)

17. Angie Jones - Java: Automated API Testing with REST Assured (1 hour 16 min, LinkedIn)

18. Dan Sullivan - Advanced SQL for Query Tuning and Performance Optimization (1 hour 44 min, LinkedIn)

19. Matt Greencroft - Java Memory Management (3 hours, LinkedIn)

20. Jeremy Villeneuve - AWS Essential Training for Developers (3 hours 17 min, LinkedIn)

Asosiy veb saytlat:

21. baeldung.com

22. javatpoint.com

23. thorben-janssen.com

24. stackoverflow.com

Youtube kanallar:

25. Thorben Janssen

26. Amigoscode

Izoh. Menga asosan kitob o'qish ma'qul, lekin oldin mavzu haqida qisqacha tushunchaga ega bo'lish uchun video dars ko'raman. Youtube ni esa tavsiya qilish qiyin, chunki u yerda chalg'ituvchi ko'p va shuning uchun "ko'ngli bo'shlarni" uncha munchaga qo'yib yubormaydi - o'qiyman deb kirasiz va ... .

#New_Job 🎉🎉🎉
Junior Software Engineer at EPAM Systems

Yechim 12. n ta urinishda qavatni aniqlash mumkin bo'lsin. Dastlab n-qavatdan birinchi tuxumni tashlab ko'ramiz:
- agar u sinsa endi ikkinchi tuxumni 1-qavatdan tashlab ko'ramiz, agar sinsa demak bizga kerak qavat 1 bo'ladi va urinishlar soni 2, agar sinmasa 2-qavatdan tashlab ko'ramiz, ... bunda eng ko'pi bilan n-1-qavatgacha kelamiz va shuning uchun ham urinishlar soni =< 1+(n-1)=n;
- agar u sinmasa endi ikkinchi tuxumni n+(n-1) = 2n-1 qavatdan tashlab ko'ramiz (bitta urinishdan allaqachon foydalandik shuning uchun bu safar qadamni n-1 qilamiz):
-- agar u sinsa n+1-qavatdan boshlab tekshiramiz, ... bunda ko'pi bilan n-2 urinish bo'ladi (2n-2 gacha) va shuning uchun jami urinishlar soni =

#Medium
Savol 12. Faraz qiling biz 100 qavatli binoning qaysi qavatidan tuxum tashlanganida sinishini topmoqchimiz. Bunda quyidagi shartlar o'rinli:
> tuxum k-qavatdan tashlanganida sinsa, u istalgan m>k uchun m-qavatdan tashlanganida ham sinadi;
> tuxum k-qavatdan tashlanganida sinmasa, u istalgan m sinmagan tuxumni qayta ishlatish mumkin;
> singan tuxumni qayta ishlatib bo'lmaydi;
> barcha tuxumlar uchun natija bir xil;
Agar bizda ikkita tuxum bo'lsa, ular tashlanganida sinadigan eng kichik qavatni aniqlashimiz uchun eng kamida nechta urinishni amalga oshirishimiz kerak?

#Easy
Savol 11. Tasavvur qiling, siz do'stingiz bilan quyidagicha o'yin o'ynamoqchisiz:
> Dastlab stol ustiga n ta tanga joylanadi;
> Siz va do'stingiz navbat bilan shartni bajarasizlar, va siz birinchi boshlaysiz;
> Har bir ishtirokchi o'zini navbatida 1 tadan 3 tagacha (1, 2, 3) tangani olishi mumkin;
> So'ngi marta tangani olgan ishtirokchi o'yinda g'olib hisoblanadi.
Agar ikkala ishtirokchi ham optimal o'ynasa, n ni bilgan holda kim yutishini topish mumkinmi?

#Easy
Savol 10. Sport musobaqasida n nafar ishtirokchi bor. Har bir bosqichda sportchilar quyidagicha guruhlarga ajratiladi:
> Agar n juft bo'lsa, sportchilar 2 nafardan guruhlarga ajratiladi va har bir guruh g'olibi keyingi bosqichga o'tadi;
> Agar n toq bo'lsa, 1 nafar sportchi g'olib hisoblanadi va keyingi bosqichga o'tkaziladi, qolgan n-1 nafar sportchi esa 2 nafardan guruhlarga ajratiladi va har bir guruh g'olibi keyingi bosqichga o'tadi;
Musobaqa g'olibi aniqlangunga qadar necha marta guruh tuziladi?

#Medium
Savol 9. Tasavvur qiling sizda 25 ta ot bor, va siz ularning eng tezkor 3 tasini aniqlashni xohlaysiz. Buning uchun siz ko'pi bilan 5 ta ot o'rtasida poyga o'tkazishingiz mumkin va bu poyga orqali faqatgina ularning nisbiy tezligini aniqlay olasiz (5 tani ichida qaysi biri eng tezkor, ..., eng sekin), hech qanday holatda siz poygada otning haqiqiy tezligini topa olmaysiz. Shu holatda 3 ta eng tezkor otni aniqlash uchun eng kamida nechta poyga o'tkazishingiz kerak?

Yechim 8. 1- kalkulyatorda yozilgan qiymatni K1 deb belgilaylik, (shunga o'xshash qolganlarini K2, K3 kabi belgilaymiz) keyinchalik agar K1=K1-1 deb yozilsa demak birinchi kalkulyatordagi sondan 1 ni ayirgan bo'lamiz, huddi shunday K1=K1÷2 yozilsa qiymatni 2 ga bo'lgan bo'lamiz.
Quyidagi 3 ta amallar guruhini "qadam" deb nomlaylik:
1) agar K1 toq bo'lsa: K3=K3×K2 va K1=K1-1 (demak K1 juft bo'lsa bu bosqich bajarilmaydi)
2) K2=K2×K2;
3) K1=K1÷2;

Endi har bir kalkulyatorga quyidagi qiymatlarini yozib olamiz:
K1 = n;
K2 = x;
K3 = 1;
va K1>0 bo'lsa yuqoridagi "qadam"ni takrorlayveramiz. Bundan yakuniy natija K3 da hosil bo'ladi. Jami "qadam"lar soni esa taxminan [log(n)]+1 ga teng bo'ladi (bu yerda log - ikki asosga ko'ra logarifm).
Izoh: Asosiy g'oya ikkilik sanoq sistemasi: Istalgan natural sonni ikkilik sanoq sistemasida yozishimiz mumkin, bu esa o'sha sonni 2 ning qaysidir darajalari yig'indisi yordamida ifodalash mumkin degani. Masalan 7 = "111" = 2^2 + 2^1 + 2^0. Demak biz x^7 uchun x, x^2 va x^4 ni bilishimiz yetarli ekan, bular esa o'zidan bitta oldingisini o'ziga ko'paytirilishi orqali hosil bo'ladi. Biz K1 dan n ni ikkilik sanoq sistemasiga yoyishda, K2 dan x ni 1, 2, 4, 8, 16, ..., 2^k darajalarini hosil qilishda va K3 dan natijani saqlashda foydalanayapmiz.

Savol 8.
Tasavvur qiling sizda 3 ta kalkulyator bor va ular 4 ta arifmetik amalni (+, -, ×, ÷) istalgan honali sonlar ustida bajara oladi. Bu kalkulyatorlar yordamida "x" haqiqiy sonini natural "n"-darajasini nechta qadamda topish mumkin?

Ushbu telegram kanaldan istalgan dasturlash tiliga doir kitob topishingiz mumkin.

Ko'paytirish!
Kompyuter takomillashgani sari ko'pgina yangi imkoniyatlar paydo bo'ldi, shu sababli nazariyalarni boshidan qurishga qiziqish kuchaygan:
Bilamizki, ikkita butun sonni ko'paytirishni odatiy, maktabda o'rgatilgan, usulidan foydalansak "n" xonali sonlarni ko'paytmasini hisoblash uchun "n^2" ga ekvivalent sonda individual amal bajarishimiz kerak. 1960-yilda yangi algoritm orqali bu ishni "n^1.58" qadamda bajarish mumkinligi isbotlangan. 1971-yilda esa yondashuvni o'zgartirish orqali yanayam yaxshi "n×log(n)×log(log(n))" chegaraga kelishgan. Qanchalik foydasi bor deysizmi: hamma biladigan usul orqali 2 milliard xonali ikkita butun sonni ko'paytirishga kompyuter 6 oy vaqt sarflasa, eng so'ngisida 26 sekund sarflaydi! Bu chegarani "n×ln(n)" ga olib kelishga yondashuv bor, lekin yakunlanmagan.