مساله گالری هنری

نیلوفر آرازخانی — Thu, 01 Apr 2021 18:51:21 +0430

تعریف مسالهبرای آنکه از تابلوهای گران قیمت یک گالری هنری نگهداری شود لازم است که محیط امنی ایجاد شود. زیرا دزدیده شدن این اشیا بسیار محتمل است. حال برای آنکه به هنگام شب بتوان بیشترین امنیت را ایجاد کرد باید بتوان این مساله را حل کرد که: چه تعداد دوربین نیاز است و مکان آن بهتر است کجا باشد؟ ??‍♀️قبلش بگم این مساله خیلی قدیمیه و بر میگرده به ۱۹۷۳ یعنی ۴۸ سال پیش☺️راه حل در این قسمت اول درباره مساله میگیم و قدم به قدم به جواب میرسیم. یک گالری را میتوان به صورت یک سه بعدی در نظر گرفت ولی قسمت کف آن را میتوان تنها در نظر گرفت تا از این طریق به توان گالری را به یک پلیگان یا چند ضلعی مدل کرد. در یک چند ضلعی دوربین ها نقطه ها هستند و هر دوربین میتواند جاهایی از گالری را ببیند که از آن دوربین بتوان به سمت آن خط کشید به طوری که خط کشیده شده جایی از چند ضلعی را قطع نکند. چند ضلعی میتواند به صورت غیر محدب باشد زیرا اگر چند ضلعی محدب باشد تنها یک دوربین برای نگهبانی تمام گالری کافی است. شکل زیر نمونه ای از یک گالری را نشان میدهد.نمونه ای از گالری غیر محدبمثلث بندییکی از ابتدایی ترین راه حل ها استفاده از مثلث بندی است. ثابت شده است که تمام چند ضلعی ها با n راس دارای n-2 مثلث هستند. برای مثلا چند ضلعی فوق را به صورت زیر مثلث بندی میکنیم.مثلث بندیحال میتوان در هر یک از مثلث ها یک دوربین قرار داد و از این طریق گالری را تحت نظر قرار داد! ولی این تعداد دوربین بسایر زیاد است! در واقع باید n-2 دوربین را استفاده کرد که با یکم فکر میتوان فهمید که میتوان یک دوربین را بر روی ضلع مشترک بین دو تا مثلث قرار داد که از این طریق تعداد دوربین ها به نصف کاهش پیدا میکند. ولی اگر باز هم دقیق تر بشیم به این مورد میرسیم که میتوان دوربین را بر روی راس ها قرار داد زیرا ممکن است یک راس راس مشترک چندید مثلث باشد که این ایده بنیان گذار روش زیر است:مساله coloring-3باید راس هایی از چندضلعی انتخاب شود که هر کدام از مثلث های داخل چند ضلعی حداقل دارای یکی از راس ها باشد. برای همین از مساله coloring-3 استفاده میشود و به این شکل است که راس ها را به سه رنگ طوری رنگ میزند که هیچ دو رنگی در دو طرف دو ضلع چند ضلعی و یا خطوطی که برای ساخت مثلث ها کشیده ایم یک رنگ نباشد. با این کار میتوان تعداد دوربین ها را به n/3 کاهش داد!?رنگ کردن چند ضلعی با سه رنگ سیاه سفید و خاکستریحالا سوالی که پیش می آید این است که آیا این رنگبندی برای تمام چندضلعی ها امکان پذیر است؟باید این چند ضلعی را به فضای دو گان آن برد. به این صورت که هر کدام از مثلث ها یک نقطه هستند و اگر بین آن ها ضلع مشترکی وجود داشته باشد باشد بین آنها یک خط رسم کرد که چند ضلعی مورد بحث به این صورت میشود.دوگان چند ضلعیحالا فرض کنید از یک مثلث شروع کردیم و مثلثی که در آن هستیم را با سه رنگ رنک کرده ایم حالا می خواهیم به نقطه بعدی برویم نقطه ای هست که در مثلث کناری قرار دارد که تنها یک راس آن رنگ نشده است و با توجه به آنکه شکل ایجاد شده درخت است و از این روی قبلا آن را ملاقات نکرده ایم میتوان آزادانه آن را رنگ کرد.پس اثبات میشود مساله گالری را میتوان با حد اکثر n/3 دوربین حل کرد.

ضرب دو ماتریس در Cuda

نیلوفر آرازخانی — Tue, 23 Mar 2021 17:02:04 +0430

از الان تا آخر این پست میخوایم دو تا ماتریس رو در هم ضرب کنیم با استفاده از برنامه نویسی موازی!اگر چیزی از برنامه نویسی موازی نمیدونید و یا اصلا با زبان cuda آشنا نیستید بهتره یه سری به دو تا پست قبلی من بزنید... پست اول . پست دوم .ضرب ماتریس به صورت غیر موازی!خب برای اینکه یه شروع خوبی داشته باشیم بهتره که از چیزی که بلد هستیم شروع کنیم!void MatrixMul(int m1[ ][N], int m2[ ][N], int res[ ][N]){ int i, j, k; for(i=0; i

بیشتر راجع به برنامه نویسی Cuda بدونیم

نیلوفر آرازخانی — Sun, 21 Mar 2021 14:45:59 +0330

اگر قبل از خوندن این مطلب مطلب قبلی من با عنوان اولین قدم در محاسبات موازی رو بخونید براتون بهتره...متغیرهای داخلی (internal variable) ها در Cudaیکی از اولین قدم ها در نوشتن برنامه نویسی Cuda دانستن سه تا از متغیرهای داخلی هست که در خود cuda معرفی شده است. که دراین قسمت به معرفی مختصر ولی جامع درباره اش می پردازم. (تناقض شد که!)اولین متغیر blockDim هست که تعداد threadها در هر block را تعریف میکند. متغیر بعدی threadId هست که برای هر thread در یک block مقدار منحصر به فردیه. مثلا اگر blockDim باشه ۲۵۶ اون وقت threadId میشه از ۰ تا ۲۵۵. متغیر سوم و آخری blockId هست که برای هر block مقدار منحصر به فردی هستش.حالا برای اینکه یک مقدار با این تکه کد نویسی ها آشنا بشیم بهتره بریم و یک مثال ساده از Cuda ببینیم. در این مثال میخواهیم دو بردار را با هم جمع کنیم. __global__ void vectorAdd(float *a, float *b, float *c){ int i=blockId.x * blockDim.x + threadId.x; c[i]= a[i] + b[i]; } .... dim3 blocksPergrid(N/256,1,1); dim3 threadsPerBlock(256,1,1); vectorAdd<<>>(a,b,c); در این مثال i به این صورت مقایسه میشود که مثلا اگر blockId برابر با صفر باشد اولین i برابر با 0 میشود و به همین صورت تک تک c[i]ها حساب میشوند. همان طور که در نوشته قبلی اشاره شده __global__ برای این استفاده میشود که نشان دهد این قسمت kernel هست و باید بر روی GPUران شود.حالا بریم ببینیم چطور باید به کامپیوتر بگوییم که این متغیرهایی که به عنوان اشاره گر به صورت a,b,c به تابع vectorAdd فرستاده شده اند به Memory Spaceدر GPU اشاره میکنند نه CPU!از تابع cudaMalloc برای اختصاص دادن حافظه استفاده میشه و برای خالی کردن این میزان از حافظه از cudaFree استفاده میشود.پس در مثال بالا باید این خطوط برای تمام متغیرهای a,b,c اضافه بشوند که :float *a; cudaMalloc(&a, N*sizeof(float));به این معنی ست که آدرسی که پوینتر به آن اشاره میکند برابر با سایز N*sizeof(float) است و این مقدار در حافظه GPU گرفته شده است. بعد از اینکه مقداری در حافظه GPU با استفاده از cudamalloc گرفته شد حالا باید بتوان از آن به حافظه CPU یا از حافظه CPU دیتا کپی کرد برای همین از تابع CudaMemcpy استفاده میشه که این تابع در زیر به صورت یک مثال توضیح داده شده است:cudaMemcpy(array_device, array_host, N*sizeof(float), cudaMemcpyHostToDevice)که در این مثال device یعنی GPU و Host یعنی CPU که هر یک جداگانه تعریف شده اند. اولین مقدار که device است مقصد و مبدا آن host است که یعنی data از CPU به GPU کپی میشوند.synchronizationحالا که بحث کپی کردن از CPU پیش میاد همون طور که تا الان ممکنه حدس زده باشید مشکل synchronization یا همزمانی داریم! چون وقتی که تابع کرنل صدا زده میشه CPU میره ادامه کدها رو اجرا کنه و این ممکنه در کار اختلال ایجاد کنه و باعث ایجاد باگ بشه!برای همین بعد از اینکه تابع کرنل صدا زده میشه از تابع زیر استفاده میشه که به CPU میگه وایستا تا کار GPU تموم بشه داداش :دی!cudaThreadSynchronize( )یک تابع دیگه هم هست به اسم syncthreads() که برای همزمان شدن بین thread ها استفاده میشه.دست به کد شیم!این قسمت رو بزاریم برای پست بعدی! :)اگه تا اینجا خوندید مرسی:) اگه تا اینجا خوندید و هیچی نفهمیدید برید اول این پست رو بخونید :)

اولین قدم در محاسبات موازی

نیلوفر آرازخانی — Fri, 19 Mar 2021 13:23:09 +0330

این بار محاسبات موازی را با جزییات بیشتری باهم نگاه میکنیم. محاسبات موازی برای سریع تر انجام شدن برنامه ها استفاده میشه. حال فرض کنید میخواهیم یک برنامه را به صورت موازی اجرا کنیم. برای اجرای موازی برنامه نیاز هست که کامپیوتر ما دارای GPU باشد. GPU که مخفف Graphics Processing Units هست. GPU کار کرد سریع تری نسبت به CPU دارد ولی برای استفاده از آن نیاز است که CPU همراهی اش کند! یعنی GPUبه تنهایی کار را سریع نمیکند و در ارتباط با CPU است که میتواند کارها را سریع کند. همین طور که در تصویر زیر پیداست GPU بخش هایی از کد را اجرا میکند که اجرای آن سنگین تر است که به این قسمت از کد Kernels گفته میشه. CPU و GPU هر کدام Memory خودشان را دارند و با استفاده از Bus با یکدیگر در ارتباط هستند و Data ردو بدل میکنند.ارتباط بین CPU و GPUخب حالا فرض کنید میخواهیم برنامه ای بنویسیم که به صورت موازی کار کند. در واقع باید این برنامه بتواند برای اجرا شدن از GPU استفاده کند و کدها بر روی ساختار موازی آن اجرا شوند. برای این کار نیاز است که از زبان برنامه نویسی Cuda استفاده شود. این زبان یک زبان برگرفته شده از c/c++ است که به NVIDIA GPU اجازه مدیریت حافظه و تعریف کرنل برای برنامه را میدهد. هر GPUشامل تعدادی Multiprocessor است که هر کدام از این Multiprocessor ها چند coreدارند و به همین دلیل میتوان بر روی این core ها برنامه را به صورت موازی اجرا کرد. تصویر پایین صورت دقیق تری از تصویر بالاست.هر GPUدارای تعدادی multicore است که هر کدام از آنها تعدادی core دارندبرنامه نویسی در Cudaتا اینجا دیدیم ساختار GPU به چه صورته، حالا برای اینکه بتونیم در برنامه نویسی از این multiprocessor ها و core ها استفاده کنیم، نیاز هستش که بتونیم به صورت Abstract این موضوعات سخت افزاری را بر روی برنامه بیاریم. برای همین از Block به عنوان نمادی برای Multiprocessorها استفاده شده و از thread برای بیان coreها استفاده شده.برای دیدن دو تا کد یکی در C++ و یکی در Cuda خودتون رو آماده کنید! در برنامه نویسی C++ میخواهیم یک آرایه را با مقادیری پر کنیم:for( i=0; i>>(result); //call the function in this way! using //<<<>>>شاید اولش که این تکه کد رو میبینید این جوری بشید O_o ولی در واقع زیاد چیز عجیبی نیست! به عنوان آخرین مطلب این پست این تکه کد رو توضیح میدم:خط اول __global__ داره میگه این کد باید روی GPU اجرا بشه! threadIdهم برای هر thread خود برنامه به صورت unique در نظر گرفته و از تایپ dim3 هستش. تعداد بلاک ها و تعداد thread ها هم خودمون تعریف میکنیم و در آخر با توجه به تعداد بلاک و threadهای تعریف شده برنامه اجرا میشه :)اگه تا اینجا خوندید، مرسی :)

هندسه محاسباتی

نیلوفر آرازخانی — Fri, 12 Mar 2021 15:29:02 +0330

یکی از مباحثی که خیلی من رو شیفته خودش کرده هندسه محاسباتی هست. هندسه جزو درس هایی بود که در دوران دبیرستان هم برام شیرین بود. به نظرم هندسه توش یه هنری پنهان است که شاید در باقی جاهای ریاضی نشه اون رو به وضوح دید. یکی دیگه از دلایلی که هندسه به ن‍ظرم جذابه اینه که میشه مساله رو به صورت شهودی دید و روش حرف زد. به نظرم علاقه ام به هندسه یکم بخاطر ژن ایرانیمم هست چون ایرانی ها همیشه توی هندسه خیلی قوی بودن و این رو تاریخ و آثار تاریخیمون نشون میده. به هر حال من با سرچ هایی که کردم محتواهای مناسبی در باره هندسه محاسباتی ندیدم به زبان فارسی برای همین تصمیم گرفتم بیام توی ویرگول و از این دانش براتون بنویسم.معرفی هندسه محاسباتیتعریف هندسه محاسباتی مسایل الگوریتمی در فضای هندسی هستش. مثلا میخوای بدونی که یک ربات را در کجا قرار بدی تا بتونی به یه سری نقطه که در صفحه هست نزدیکترین فاصله را داشته باشه. یکی دیگه از کاربردهای هندسه محاسباتی در نقشه های GIS دیده میشه حتی در زیست و ساخت داروها هم از هندسه محاسباتی استفاده میشه. در ادامه به تعریف های ابتدایی استفاده شده در هندسه محاسباتی پرداخته میشه.پوش محدب!نمیدونم ولی فارسی نوشتن یه سری تعریف ها شاید کلا تعریف رو بر هم بزنه واسه همین بهتره بعد از خوندن این مطلب برید و به انگلیسی سرچش کنید. پوش محدب که میشه convex hull یک تعریف پایه برای مساله هندسه محاسباتی هست. به این صورت تعریف میشه که: کوچکترین کانوکسی که یه سری نقاط در صفحه رو می پوشونه.برای درک بهتر براتون یه عکس گذاشتم. همان طور که در عکس میبینید پوش محدب برای این نقاط میشه عکس سمت راستی.پوش محدبیک تعریف خیلی جالب برای درک کانوکس هال این هست که فرض کنید اون نقاط سمت چپ میخ باشه که زدیم توی یک تخته! مثل صفحه ای که مرتاض های هندی روش میخوابند! بعد یک کش رو بندازیم دور اون میخ ها و هرجا وایستاد میشه همون پوش محدب یا convex hull مون! به اون نقطه هایی که روی شکل با p1 تا p2 نوشته شده هم میگند extreme point (دیگه واقعا فارسی این چی میشه؟?)خب این ها تا الان یه معرفی کلی از هندسه محاسباتی بود که در ادامه به معرفی یکی از حوزه‌های هندسه محاسباتی توضیح می دم.مساله گالری هنرمساله گالری هنر برمیگرده به ۴۰ سال پیش و مساله خیلی قدیمی هست. این مساله دنبال بهینه کردن تعداد نگهبان ها برای نگهبانی از یک محیط هست. در این مساله دنبال این هستیم که نقاط بهینه ای را در چندضلعی پیدا کنیم که نقاط روی چندضلعی و نقاط درون آن قابل رویت باشند.تعریف رویت پذیریدو نقطه در یک چند ضلعی رویت پذیر هستند اگر پاره خطی که این دو را به هم متصل میکنند در داخل چند ضلعی قرار بگیرند. من توی ذهنم این جوری فرض میکنم که این دو تا نقطه بتونن همدیگه رو ببینند یعنی روی خط مستقیم بتونند هم رو ببینند.تعریف رویت پذیری متعامدچون با گذشت زمان و پیشرفت علم ما نگهبانی هامون رو به روباتها میدیم برای همین بهتره که الگوریتم های نگهبانی رو با توجه به محدودیت های حرکتی روبات ها تعریف کنیم. برای همین رویت پذیری متعامد معرفی شده. رویت پذیری متعامد یعنی دو تا نقطه رویت پذیر متعامد هستند که این دو نقطه در روی یک قطر مستطیل گذشته شده از این دو نقطه باشند و این مستطیل کامل در چندضلعی متعامد قرار بگیرد.نتیجه گیریدر این نوشته من مقدماتی درباره هندسه محاسباتی گفتم. اینکه کلا این فیلد از ریاضیات به چه چیزی می پردازه و یه سری تعاریف اصلی و پایه گفتم و دو تا تعریف از رویت پذیری.در نوشته های آینده بیشتر راجع به این مبحث حرف میزنم. یعنی قسمت رویت پذیری متعامد.منابعی که استفاده کردم : فیلم مدرسه زمستانی هندسه محاسباتی از دکتر ضرابی زاده و مقالات نوشته شده درباره رویت پذیری متعامد هست.

نوشته های نیلوفر آرازخانی

مساله گالری هنری

ضرب دو ماتریس در Cuda

بیشتر راجع به برنامه نویسی Cuda بدونیم

اولین قدم در محاسبات موازی

هندسه محاسباتی