مادر تراز...

اسلاید فصل‌های مختلف ساختمان داده الگوریتم دانشگاه پرینستون👇🏻
https://algs4.cs.princeton.edu/lectures/

یه پیشرفت در محاسبه ضرب دو ماتریس. در ده سال گذشته این بهترین بهبود بوده. سه تا پژوهشگر از دانشگاه برکلی تونستند این کار رو انجام بدند. البته ظاهرا این تیپ الگوریتم ها فعلا کاربرد عملی ندارند و بیشتر از جنبه نظری کار اهمیت دارند، چون برای سایزهای معقول و در عمل همون الگوریتم های کلاسیک بهتر عمل می کنه.

https://www.quantamagazine.org/new-breakthrough-brings-matrix-multiplication-closer-to-ideal-20240307/

با یه دوستی توی ناشناس داشتیم در مورد این صحبت می‌کردیم که مرتبه ضرب ماتریس‌ها هنوز 2.3 هست که! پس چه تغییری کرده؟ خلاصه الان یکم در موردش سرچ کردم و همین مقاله رو مجدد خوندم فهمیدم این تیم توی نوامبر 2023 تونستن مرتبه رو از 2.3728596 (از سال 2010 به بعد گویا این بهترین مرتبه بوده) به حدود 2.371866 کاهش بدن.
در ژانویه 2024 هم باز همین تیم تونستن مرتبه رو با کمک همون ایده‌ای که داشتن مرتبه رو مجدد کاهش بدن و به 2.371552 برسونن.

ایده‌ای که برای کاهش مرتبه دارن اینه که میان از ترکیب روش لیزری و Coppersmith–Winograd استفاده می‌کنن. ولی گویا نتایج ثابت کرده این روش نمی‌تونه مرتبه رو به زیر حدود 2.3078 برسونه و اگه دنبال کاهش بیشتری باشن باید توی رویکرد اصلی Coppersmith–Winograd بازنگری کنن.

جک دورسی (توییتر رو داشت قبلا و بیرونش کردن) داره یه سوشال مدیا می‌سازه به اسم BitChat. بعد این شبکه‌ی اجتماعی از طریق اینترنت کار نمی‌کنه. به عبارتی اون شبکه‌ش یا به طور خاص‌تر مش‌اش (Mesh) رو با بلوتوث می‌سازه.

به عبارتی نیاز نیست پیامی که میدین رو سرور به سرور بره تا برسه به سرور اصلی. دیوایس به دیوایس با بلوتوث میره.


لینک خبرش:
https://cointelegraph.com/news/jack-dorsey-launches-bluetooth-relayed-decentralized-messaging-app-bitchat


لینک گیت‌هاب پروژش:

https://github.com/jackjackbits/bitchat

این چیزهای decentralized و بعضا بی‌نیاز از اینترنت داره خیلی زیاد میشه و خب بنظر در آینده تحول خیلی عجیب و باحالی توی این حوزه باشه.

اگر رونمایی آیفون ۱۵ اپل رو هم دیده باشید (اگر ندیدید ببینید)، اپل یه تکنولوژی معرفی کرده بود روی گوشی ۱۵ پرو که اگر شما توی یک بیابونی جایی بودید که خلاصه صدای خر به خدا نمی‌رسید و هیچ دکل مخابراتی وجود نداشت و به عبارتی نه اینترنت داشتید و نه آنتن، منتهی همچنان بتونید از طریق یه سری ماهواره تماس بگیرید یا که پیامتون رو ارسال کنید.

در آینده احتمالا اینجوری بشه که یا دیگه هر دهاتی هم باشید اینترنت دارید. یا که اصلا دیگه نیازی به اینترنت برای برقراری ارتباط ندارید.

داشتم یکم در مورد راماکریشنان (نویسنده کتاب DBMS) می‌خوندم فهمیدم استاد راهنمای دوره دکتراش توی دانشگاه آستن تگزاس جناب سیلبرشاتس بوده. جالبه و کم اتفاق میفته که کسی تونسته رو دست استادش (اونم سیلبرشاتس کبیر) بلند بشه و کتابش به عنوان یکی از رفرنس‌های اصلی در دانشگاه‌ها تدریس شه :)

در مورد هندسه محاسباتی می‌خوندم که به یه مسئله جالب و تقریباً هم پر کاربرد توی دنیای واقعی رسیدم احتمالاً برای شما هم جذاب باشه. اول از همه هم بگم که هندسه محاسباتی جزو چارت گرایش الگوریتم و محاسبات مقطع ارشده و هر چی بیشتر در مورد این گرایش تحقیق می‌کنم بیشتر علاقه‌مند می‌شم بهش.
________________________________________
توی هندسه محاسباتی یه مبحثی داریم به اسم دیاگرام ورونوی (Voronoi diagram). ما میاییم صفحه (یا یه فضای n بعدی) رو بر اساس نزدیکی به یه مجموعه نقاط مشخص تقسیم می‌کنیم. به عنوان مثال فرض کنید یه مجموعه از نقاط (سایت هم گفته می‌شه) داریم به صورت زیر:
P = { p₁, p₂, …, pₙ } ⊂ ℝ²
حالا سلول یا منطقه ورونوی متناظر با هر سایت (نقطه) Pi به صورت زیر تعریف می‌شه:
V(p_i) = { x ∈ R² | d(x, p_i) ≤ d(x, p_j) for all j ≠ i }
که d(0,0) معمولاً فاصله اقلیدسی‌ئه. دیاگرام ورونوی، اجتماع V(pi) نقاط اون مجموعه‌ای هست که بالاتر گفتم که صفحه رو به سلول‌های بدون هم‌پوشی تقسیم می‌کنه.

اگه بخوام ساده‌تر بگم:
فرض کنید حوالی میدون انقلاب با دوستاتون دارید قدم می‌زنید و تصمیم گرفتید برید کافه. دیاگرام ورونوی توی نقشه‌ای که ترسیم می‌کنه مشخصاً بهت می‌گه توی نقطه‌ای که هستی نزدیک‌ترین کافه بهت کدومه. مثلاً جایی که هستید 5تا کافه وجود داره توی نواحی مختلف اون منطقه. حالا دیاگرام ورونوی میاد اون منطقه رو به 5 ناحیه تقسیم می‌کنه و هر ناحیه مربوط به یک کافه‌ست. حالا مرز بین ناحیه‌ها چطوری کشیده می‌شه؟ مرز بین دو ناحیه A و B رو خطی عمود وسط خط اتصال A به B می‌کشیم. مثلاً اگه A و B با هم دیگه 10 متر فاصله داشته باشن، مرز ناحیه‌شون دقیقاً تو 5 متری هر دو ناحیه کشیده می‌شه. چندتا از ویژگی‌های جالبش هم اینه که هر ناحیه یه چند ضلعی می‌شه. هر چقدر این کافه‌ها به هم دیگه نزدیک‌تر باشن منطقه‌شون کوچیک‌تر می‌شه. اون نقاطی هم که روی مرز هستن با دو یا چندتا کافه هم فاصله‌ان.

یکی از کاربردهاش هم طراحی شبکه‌های موبایله. میاییم هر آنتن رو یک نقطه در دیاگرام ورونوی در نظر می‌گیریم. مثلاً فکر کنید توی هر شهر/منطقه چندتا آنتن پایه (BTS) داریم که پخش‌کننده سیگنال موبایل هستن. هر کدوم از این آنتن‌ها منطقه به خصوصی رو سرویس می‌ده که در اون منطقه، آنتن بهترین سرویس رو به کاربرها ارائه می‌ده. با ساختن سلول‌های ورونوی حول هر نقطه، نواحی طبیعی تحت پوشش هر آنتن مشخص می‌شه. حالا از این طریق می‌تونیم در مکان‌یابی و جایگذاری یه آنتن جدید استفاده کنیم که به کاربرها خدمات ارائه بده.

توی این فایل هم اومده توضیحات بیشتری در موردش ارائه داده (فکر کنم برای mit بود)

اینم خواستید بخونید توضیحات خوب و کاملی بود

این رو لازم دیدم بگم شاید بدردتون بخوره و خبر نداشته باشید :)

من اینجا رو وقتی ساختم پرایوت بود و صرفاً حالت یه دفترچه رو برام داشت و مباحثی که در مورد دیتا ساینس و ML توی کورس فناپ آموزش میدیدم رو می‌نوشتم. خلاصه به چندتا از دوست‌ها و هم‌گروهی‌هام توی همون دوره لینک اینجا رو دادم و چون استقبال شد دیگه پابلیک کردم و فعالیت در اینجا رو جدی‌تر ادامه دادم.

خلاصه اینکه اگه برید اوایل کانال یسری نکته و جزوه در مورد دیتا ساینس و ML هست که ممکنه بدردتون بخوره.

لینک اولین پست:
https://news.1rj.ru/str/supersonic_AI/4

باگ Y2K (Year 2000 Bug) که یکی از شناخته‌شده‌ترین مشکلات نرم‌افزاری هست چرا اتفاق افتاد؟

ریشه این باگ توی ساده‌سازی ذخیره‌ی سال‌ها بصورت دو رقمی بود. توی دهه‌های 60 و 70 میلادی بخاطر محدودیت حافظه کامپیوترها (در گذشته حافظه خیلی ارزشمند و محدود بوده و بخاطر همین قیمت بالایی داشت) و برای صرفه‌جویی در حافظه و فضای ذخیره‌سازی خیلی از سیستم‌ها اومدن تاریخ رو با دو رقم آخر سال نگه‌داری می‌کردن. مثلاً سال 1985 بصورت 85 ذخیره می‌شد یا سال 1978 بصورت 78. این روش برای سال‌های 1900 تا 1999 کار می‌کرد و همه‌چی اوکی و گل و بلبل بود تا اینکه رسیدن به یک ژانویه سال 2000 :) سیستم‌هایی که داشتن عدد 00 رو به عنوان سال 1900 تفسیر می‌کردن نه 2000، سر همین توی موارد مختلفی مثل محاسبه سن افراد، اختلافات زمانی، مرتب‌سازی تاریخ‌ها و خیلی فرایندهای دیگه‌ای که وابسته به تاریخ هست دچار خطا میشدن.
این مشکل می‌تونست سبب خرابی سیستم‌های مهم و حیاتی مثل بانکداری، حمل و نقل، و زیرساخت‌های حیاتی بشه. یسری تخمین هم هست که هزینه‌های جهانی برای بر طرف کردن این باگ ساده حدود 300 تا 600 میلیارد دلار بوده.
علاوه بر این هم برنامه‌ها و سیستم‌ها نمی‌تونستن سال 2000 رو به عنوان سال کبیسه (leap year) شناسایی کنن و می‌تونست یسری مشکلات اضافی به همراه داشته باشه.
برای جلوگیری از رخ دادن این فاجعه هم دولت‌ها، سازمان‌ها و... قبل از سال 2000 شروع به بررسی و به‌روزرسانی سیستم‌هاشون کردن. یسری راه‌حل‌ها که استفاده کردن اینا بود:

افزودن دو رقم به فیلدهای تاریخ: اومدن برای ذخیره‌سازی سال دوباره از 4 رقم استفاده کردن. طبیعتاً این روش هزینه‌بر بود و خطر از دست رفتن داده‌ها رو هم داشته.
پنجره‌بندی تاریخ (Date Windowing): توی این روش یه سال به عنوان pivot در نظر گرفته می‌شد (مثلاً 1920)، بعد سال‌های 00 تا 20 به عنوان 2000 تا 2020 و سال‌های 21 تا 29 به عنوان 1921 تا 1929 تفسیر می‌شدن. این روش هم کوتاه مدت بود و توی دهه‌های آینده دوباره مشکل‌ساز می‌شد.
فشرده‌سازی: اومدن از کدگذاری‌های 14 بیتی برای ذخیره تاریخ استفاده کردن که حافظه کمتری مصرف کنه.

یسری نتایج و حوادث مربوط به این باگ که گزارش شد:
دو تا نیروگاه هسته‌ای در ژاپن دچار اختلال موقت شدن ولی سریع برطرف شد.
در دانمارک، نوزاد متولد اول سال 2000 به اشتباه سنش 100 سال ثبت شد :)
در استرالیا، بلیت‌های اتوبوس تاریخ‌های نادرست چاپ کردن و اسکنرها اون‌ها رو رد کردن.
در مصر، آژانس خبری ملی به طور موقت آفلاین شد.

خلاصه حافظه تقریباً یکی از مشکلات جدی برای بشر بوده و هست. قبلاً محدودیت وجود داشت بخاطر قیمت بالای فضاهای ذخیره‌سازی و البته ابعاد بزرگی که داشتن، الان که ابعادشون خیلی کاهش پیدا کرده و مسئله هزینه هم مطرح نیست، درگیر سرعت دسترسی به حافظه‌ها هستیم و سعی داریم سرعت دسترسی به حافظه رو با روش‌هایی که وجود داره کاهش بدیم و از Memory Wall اجتناب کنیم.

خواستم آپلودش کنم دیدم نزدیک 600 مگ حجم کتابه :) اگه خواستید می‌تونید توی لینک زیر بصورت آنلاین کتاب رو بخونید.
https://archive.org/details/godel-escher-bach-an-eternal-golden-braid-1999/mode/2up

مسئله خوبیه برای فکر کردن