My Course

یادگیری های من در شریف!

My Course

یادگیری های من در شریف!

یادگیری های من در دوران تحصیل در رشته کامپیوتر در دانشگاه شریف.

۲۷
بهمن

Ref.
  1. C. Baier and J.P. Katoen, “Model Checking”, The MIT Press, Cambridge, MA, 2009.
  2. E.M. Clarke, O Grumberg, and D.A. Peled, “Model Checking”, The MIT Press, Cambridge, MA, U.S.A, 2001.
  3. M. Huth and M. Ryan, “Logic in Computer Science: Modeling and Reasoning about Systems”,2nd Ed., Cambridge University Press, 2004.
استاد درس: دکتر موقر


Some Similar Recent courses in North America:

  1. Bug Catching: Automated Program Verification and Testing, SCS15-414, Fall 2014, Carnegie Mellon University, School of Computer Science. Taught by E.M. Clarke.
  2. Graduate Verification Seminar: Automated Theorem Proving, SCS15-817, Spring 2013, Carnegie Mellon University, School of Computer Science. Being taught by E.M. Clarke.
  3. Program Verification, CS476, Fall 2013-4, University of Illinois at Urbana-Champaign, Department of Computer Science. Being taught by Jose Meseguer.
  4. Techniques for Program Analysis and Verification , CS357, Fall 2013-4, Stanford University, Department of Computer Science. Taught by Dill and Aiken.
  5. Computer-Aided Verification, CS745, Fall 2009, University of Waterloo, School of Computer Science. Taught by Joe Atlee.
  6. Abstraction: Fighting State Explosion in Model Checking , CS 846, Winter 2010, University of Waterloo, School of Computer Science. Taught by Richard Trefler.
  7. Software Verification and Testing, CSC410, Winter 2013, University of Toronto, Department of Computer Science. Being taught by Azadeh Farzan.
  8. Topics in Verification (Game Theory in Formal Verification), CSC2226H, Winter 2014, University of Toronto, Department of Computer Science. Being taught by Azadeh Farzan.

T.A. :   Shirin Baghoolizadeh   
           baghoolizadeh@gmail.com


Grading Policy
  1. Programming Assignments: 10%
  2. Research Presentations: 10%
  3. Final Research Paper: 20%
  4. Midterm Exam: 20%
  5. Final Exam: 40%

  • سمیه زارعی مرادی
۰۶
مهر
  • سمیه زارعی مرادی
۰۵
مهر
  • سمیه زارعی مرادی
۰۵
مهر
  • سمیه زارعی مرادی
۳۱
شهریور

نرم افزار R رو از آدرس زیر:

http://cran.r-project.org/


و نرم افزار RStudio  رو از آدرس زیر دانلود میکنیم:


http://www.rstudio.com/

  • سمیه زارعی مرادی
۳۱
شهریور

سلام.

برای درس داده کاوی باید R  یاد بگیریم. اینم چند تا آدرس برای یادگیری R:


http://tryr.codeschool.com/

https://www.coursera.org/

http://sentimentmining.net/StatisticsWithR/

http://www.stat.cmu.edu/~cshalizi/statcomp/14/

https://class.coursera.org/datasci-002



و کتاب های رایگان:

R For Beginners

R Tips

R Inferno


و کتاب های مفید دیگر:

The Art of R Programming by 




R in a Nutshell by 


  • سمیه زارعی مرادی
۳۰
شهریور

Data Mining. Concepts and Techniques, 3rd Edition
Jiawei Han, Micheline Kamber, Jian Pei

استاد درس: دکتر بیگی

نحوه ارزیابی:

میان ترم:                       1393/08/08                   30%
پایان ترم:                       1393/10/20                   30%


ارائه یک مقاله در موضوع داده کاوی:                          10%
تعیین موضوع:           تا   1393/08/08  

تمرین + پروژه + کوییز                                          30%

TA: آقای برآانی

برای این درس از پکیج آماری R استفاده خواهد شد.


  • سمیه زارعی مرادی
۳۰
شهریور
  • سمیه زارعی مرادی
۰۷
تیر
سلام.
برای درس معماری نرم افزار نیاز به نصب این برنامه داشتم.  نرم افزار خوبی برای رسم دیاگرام هاست. در ضمن رایگان هم هست.
آدرس دانلود:
برای نصبش هم Next ها رو بزنید و در آخر Launch رو تیک بزنید و تمام! 
این فیلم هم هست:
برای نحوه استفاده و دانلود تمپلیت ها و ماژول ها هم برید اینجا:
امیدوارم مفید بوده باشه!
  • سمیه زارعی مرادی
۳۱
فروردين

سوال 1:

برای اینکه از عدم وجود دور در گراف مطمئن باشیم از این روش استفاده می کنیم که به یک رأس یا وارد می شویم یا از آن خارج می شویم. در ایصورت در گراف جهت دار دوری نخواهیم داشت. 

طبق راهنمایی سؤال رئوس را به ترتیب دلخواه شماره گذاری می کنیم و و به این ترتیب کل یال ها را به دو دسته تقسیم می کنیم :

دسته اول یال هایی که از رأس با شماره بزرگتر به رأس با شماره کوچکتر می روند و یال هایی که از رأس با شماره کوچکتر به رأس با شماره بزرگتر می روند . از بین این دو دسته دسته بزرگتر را انتخاب می کنیم. بدیهی است که در اینصورت دور نداریم. 

و چون دست کم نصف یال ها را با این الگوریتم انتخاب خواهیم کرد و تعداد بهینه یال ها برای این الگوریتم حداکثر برابر کل تعداد یال ها در گراف اصلی است به وضوح این الگوریتم از فاکتور 1/2 است.


سؤال 2:

یک تطابق از گراف پیدا می کنیم. به این ترتیب که از یک رأس شروع می کنیم و با یکی از همسایگانش تطبیق می دهیم و از گراف حذف می کنیم. و به همین ترتیب ادامه می دهیم. این یک تطابق maximal از گراف می دهد که طبق راهنمایی سؤال از نصف تطابق ماکزیمم بیشتر است یعنی تطابق ماکزیمم از 2 برابر تطابق بیشینه کمتر است و از تطابق بیشینه بیشتر است( بدیهی است!) یعنی الگوریتمی با فاکتور 2

البته توجه کنید که این یک الگوریتم پیدا کردن کمینه است و مقداری که ما ممکن است پیدا کنیم ماکزیمم تطابق است که چون از 2 برابر هر ماکزیمال تطابقی کمتر است ( حتی جواب بهینه ما در اینجا یعنی تطابق ماکزیمال با کمترین کاردینالیتی ) بنابراین طبق نامساوی هایی که در بالا گفته شد فاکتر 2 می شود این الگوریتم! :)


سؤال 3:

ابتدا نشان می دهیم که مجموعه انتخاب شده یک vertex cover برای گراف هست. با توجه به اینکه در پیمایش عمقی گراف برگ ها فقط به پدرشان یا به گره های جدشان یال دارند بنابراین با توجه به اینکه تمام گره های غیر برگ در این مجموعه قرار گرفته اند بنابراین نیازی به انتخاب برگ ها نیست چون برای تمام یال ها یک سرشان در این مجموعه قرار گرفته است و این یک VC است. 


حالا فاکتور 2 را اثبات می کنیم. برای این می دانیم که گره ها فقط به پدر یا اجدادشان یال دارند. بنابراین کافیست گره های غیر برگ در عمق های فرد را با گره های غیر برگ در عمق زوج تطابق دهیم و دو سر این تطابق را ( که یک تطابق ماکزیمال است ) به عنوان جواب گزارش کنیم. تعداد این تطابق حداکثر برابر نصف گره های غیر برگ است. ( این در حالتی اتفاق می افتد که تعداد گره ها در عمق زوج و فرد با هم برابر باشد.) که می دانیم تعداد این تطابق ها همیشه از کاردینالیتی کمتر است.( lower bound)  بنابراین فاکتور 2 اثبات می شود.

مثال tight : گراف دو بخشی است.  که به صورت زیگزاگ به هم یال دارند. 


سؤال 4: 

مثال tight  رو سر کلاس دکتر آبام گفتن. اما شکلش رو میذارم بعداً. حتماًً................. :)


سؤال 5: 




سؤال 9:

فرض کنید k  برابر OPTVC روی گراف با گره هایی با وزن 1 باشد. راه حلی از مرتبه چند جمله ای برای پیدا کردن اینکه گراف دارای این VC هست یا نه نداریم. که بعد از آن بخواهیم می نیمم هزینه را برای این دربیاوریم! راه حل چند جمله ای ما در بهترین حالت از فاکتور 2 است. 

بنابراین این مسأله هم NP-optimization  است. در واقع این مسئله همان ورژن تصمیم گیری مسئله VC است. 






  • سمیه زارعی مرادی