علی شکیبا

دفتر یادداشت دیجیتال برای هر چیز مفید!

در این یادداشت نسبتا طولانی قصد دارم تا ابتدا دیدی کلی از محاسبات کوانتومی را فارغ از هرگونه فرمول ارائه کرده و سپس مراجعی برای ادامه‌ی مطالعه‌ی علاقه‌مندان فراهم آورم.

۰ نظر موافقین ۰ مخالفین ۰ ۳۰ خرداد ۹۵ ، ۰۰:۳۸
علی شکیبا

در این چالش، کتاب زیبای 

Rolf Niedermeier, "Invitation to Fixed Parameter Algorithms", Oxford University, 2006.

را معرفی می‌کنم. به عنوان یک معارفه‌ی ساده با زمینه‌ی مورد بحث این کتاب می‌توانید این مقاله‌ی ویکی‌پدیا را مطالعه کنید.  این کتاب به خوبی از عهده‌ی دو کار برآمده است. اول، یک مرور کلی بر مطالب ارائه شده تا زمان چاپ است که از آن یک Research Manuscript ساخته است و دیگر، در عین اینکه به مرزهای دانش در این زمینه می‌پردازد، به عنوان یک کتاب آموزشی نیز طراحی شده است. مطمئن هستم دوستانی که به نظریه الگوریتمی گراف و مباحث پیچیدگی محاسباتی علاقه‌مند باشند، از مطالعه‌ی این کتاب لذت خواهند برد. می‌توانید این کتاب را از libgen به رایگان دریافت کنید.

پی نوشت: ایده‌ی چالش کتاب بر مبنای این پست دوست عزیزم، آقای گوهرشادی است.

۰ نظر موافقین ۰ مخالفین ۰ ۲۱ ارديبهشت ۹۵ ، ۲۲:۵۶
علی شکیبا

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

خبری که ذکر آن رفت، در پایگاه خبری دانشگاه MIT آمده است، تحت عنوان «برای مدیریت داده‌ی حجیم، آن را کوچک کن!» و بر مبنای مقاله http://arxiv.org/abs/1412.0588 است که در کنفرانس ACM Symposium of Theory of Computing در ماه ژوئن ارائه شده است. صفحه شخصی یکی از نویسندگان این مقاله، http://math.mit.edu/~rpeng/ است. البته ظاهرا این نویسندگان، مقاله دیگری نیز کار کرده اند http://arxiv.org/abs/1408.5099 که بحثش نمونه گیری یکنواخت از یک ماتریس است.

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

A. Shakiba, M.R. Hooshmandasl, Data volume reduction in covering approximation spaces with respect to twenty-two types of covering based rough sets, International Journal of Approximate Reasoning, Volume 75, August 2016, Pages 13-38, ISSN 0888-613X, http://dx.doi.org/10.1016/j.ijar.2016.04.002.

(http://www.sciencedirect.com/science/article/pii/S0888613X16300433)

اما در مقام مقایسه، کار من روی داده های سمبلیک است در صورتی که این مقاله با داده های عددی کار می کند.

۰ نظر موافقین ۱ مخالفین ۰ ۰۸ ارديبهشت ۹۵ ، ۱۸:۰۰
علی شکیبا

یکی از رویه هایی که در برابر مسائل NP-سخت مورد استفاده قرار می گیرد، بیشتر برای شناخت دلیل و علت دشواری مسائل، Fixed Parameter Tractability یا FPT است. فعلا روی این موضوع تمرکز کرده ام، اما امروز مقاله ای جالب با عنوانی جالب تر دیدم!

Alexander Golovnev, Alexander S. Kulikov, and Ivan Mihajlin. 2016. Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFTACM Trans. Algorithms 12, 3, Article 35 (April 2016), 17 pages. DOI=http://dx.doi.org/10.1145/2847419

این مقاله، الگوریتم هایی برای یافتن پاسخ دقیق سه مساله ی فروشنده ی دوره گرد (Traveling Salesman)، عدد رنگی (Chromatic Number) و شمارش تطابق های کامل (Counting Perfect Matchings) را با استفاده از تبدیل سریع فوریه ارائه می کند. ایده ی جالبی است و البته برای من جدید بود! نسخه ی منتشر شده ی این مقاله از اینجا قابل دریافت است. همچنین نسخه ی نویسندگان را می توانید از صفحه ی شخصی نویسنده و یا arXiv دریافت کنید.

برای آشنایی یا یادآوری با تبدیل فوریه (سریع) می توانید از BetterExplained یا Math@StackXchange استفاده کنید.

 

۱ نظر موافقین ۱ مخالفین ۰ ۰۷ ارديبهشت ۹۵ ، ۲۳:۴۲
علی شکیبا

امروز مطلبی را در خبرنامه ی فنی ACM به نام ACM Technew دیدم درباره ی نوع داده ی جدید unum (یا بهتر است بگویم شیوه ی جدیدی برای نمایش اعداد حقیقی). کمی در این باره کنجکاو شدم! ایده ی جالبی است و البته طراح آن نیز یک قانون در معماری کامپیوتر را نیز به نام خود ثبت کرده است!

مشروح مصاحبه ی ACM با این فرد در مورد نوع داده ی unum و اثرات آن در محاسبات در مجله ی Ubiquity به چاپ رسیده است. کتابی از نویسنده با شرح دقیق unum و کاربردهای آن به عنوان The End of Error: Unum Computing چاپ شده است که البته می توانید نسخه ای از آن را به رایگان از libgen دریافت کنید.

پی نوشت: می توان این مطلب را به عنوان پروژه ی درسی دانشجویان درس اصول سیستم های کامپیوتری منظور کرد تا علاوه بر آشنایی با IEEE-754، با این نوع نیز آشنا شوند. البته پیاده سازی آن ساده است ولی کمی سماجت و ممارست می خواهد. :-)

۰ نظر موافقین ۱ مخالفین ۰ ۰۷ ارديبهشت ۹۵ ، ۰۰:۱۵
علی شکیبا

برای نصب Oracle Java در لینوکس به صورت دستی، ابتدا فایل‌های مربوطه را از آینه http://mirror.sito.ir/ (مخزن آینه‌ای برای اکثر نرم‌افزارهای پرکاربرد که دانلود آن‌ها برای آدرس‌های آی‌پی ایرانی مقدور نیست - البته این مخزن برای Java به روز نیست! :( ) دریافت می‌کنیم.

در گام بعدی، لازم است تا فایل مربوطه را که نامی به صورت jdk-7u51-linux-x64.tar.gz دارد تا از حالت فشرده خارج کنیم. بهتر است که فایل‌های خارج شده از حالت فشرده را در محلی مثل /usr/local یا /opt قرار دهیم.

tar xzf jdk-7u51-linux-x64.tar.gz
sudo mkdir /opt/java
mv jdk1.7.0_51 /opt/java/

سپس نوبت به اضافه کردن دستورات مربوطه می‌رسد (البته می‌توان مسیر /opt/java/jdk1.7.0_51/bin را نیز در متغیر محیطی PATH قرار داد، که این کار را هم انجام می‌دهم. اما ممکن است قبلا شما از OpenJDK یا نسخه متفاوتی از Java استفاده می‌کردید)

sudo update-alternatives --install "/usr/bin/java" "java" "/opt/java/jdk1.7.0_51/bin/java" 1
sudo update-alternatives --install "/usr/bin/javac" "javac" "/opt/java/jdk1.7.0_51/bin/javac" 1 
sudo update-alternatives --install "/usr/bin/javaws" "javaws" "/opt/java/jdk1.7.0_51/bin/javaws" 1

همچنین مسیر پوشه bin جاوا را نیز به متغیر PATH اضافه می‌کنیم. بدین منظور فایل /etc/envorinment را ویرایش کرده و مقادیر زیر را در آن قرار می‌دهیم

PATH="/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/usr/local/texlive/2012/bin/x86_64-linux:/opt/java/jdk1.7.0_51/bin"
JAVA_HOME="/opt/java/jdk1.7.0_51"

حال لازم است تا مجوز اجرایی فایل‌های پوشه bin را نیز برای همه صادر کنیم. بدین منظور

cd /opt/java/jdk1.7.0_51/bin
chmod a+x *

جاوای ما آماده استفاده است! :)

۰ نظر موافقین ۰ مخالفین ۰ ۲۷ تیر ۹۴ ، ۱۵:۰۳
علی شکیبا

امروز قصد داشتم تا Code::Blocks رو با استفاده از فایل‌های توزیع شده در سایت خودش نصب کنم. خوب، مطابق معمول و به سادگی، فایل‌ها رو در یک فولدر قرار داده و بعد دستور زیر رو اجرا کردم

sudo dpkg -i *.deb

و بعد هم مطابق معمول، دستور زیر را برای حل و فصل پیش‌نیازها صادر کردم.

sudo apt-get install -f

اما یه مقدار حجم بسته‌های مورد نیاز زیاد بود، پس تصمیم گرفتم که فرایند نصب رو برعکس کنم! این کار با دستور زیر ممکن است

sudo apt-get remove `find -iname '*.deb' -exec dpkg --info '{}' \; | awk '/Package:/ {print $2}'`

که از اینجا برداشته شده است.

۰ نظر موافقین ۰ مخالفین ۰ ۲۰ تیر ۹۴ ، ۱۴:۱۳
علی شکیبا

یکی از بهترین و مجهزترین کتابخانه‌های پردازش تصویر که متن باز هم باشد، Open CV است. این کتابخانه که به زبان ++C/C نوشته شده است، دارای یک رابط برای زبان Python نیز هست که کار با آن را بسیار ساده‌تر می‌کند و البته سرعت پردازشی بالایی را نیز به نسبت بسیاری از کتابخانه‌هایی که به صورت خالص در Python نوشته شده اند، فراهم می‌کند!

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

اما قبل از نصب، من از موتور تک‌لایو 2012 که به شیوه این پست آن را نصب کرده ام و از توزیع Anaconda Python استفاده می‌کنم که به صورت دستی و نه با استفاده از مخازن Ubuntu نصب شده اند. شاید یکی از مهمترین دلایل سخت بودن این فرایند برای من، همین دو موضوع بود! بگذریم ...

ابتدا لازم است تا به سایت رسمی OpenCV به آدرس http://opencv.org/downloads.html رفته و از آنجا نسخه مورد نظر خود را دریافت کنیم. در زمانی که این متن را می‌نویسم، نسخه 3 در مرحله Release Candidate 1 قرار داشت. من از نسخه 2.4.11 استفاده کردم!

سپس نوبت به نصب پیش‌نیازها می‌رسد. برای نصب موفق این بسته، این بسته‌ها را نصب کردم:

sudo apt-get install build-essential libgtk2.0-dev libjpeg-dev libtiff4-dev libjasper-dev libopenexr-dev cmake libtbb-dev libeigen3-dev yasm libfaac-dev libopencore-amrnb-dev libopencore-amrwb-dev libtheora-dev libvorbis-dev libxvidcore-dev libx264-dev libqt4-dev libqt4-opengl-dev sphinx-common libv4l-dev libdc1394-22-dev libavcodec-dev libavformat-dev libswscale-dev default-jdk ant libvtk5-qt4-dev qt5-default libqt5x11* libx11-xcb1* pkg-config libxcb1-dev libxcb1 xcb

البته به احتمال خیلی زیاد، تعدادی از این بسته‌ها لازم نیستند، اما این تمام بسته‌هایی است که نصب شدند (در مراحل مختلف که خطایابی نصب انجام می‌شد) تا مثال‌ها به درستی نصب شدند.

پس از آن، فایل دانلود شده در مرحله اول را از حالت فشرده باز کرده 

unzip opencv-2.4.11.zip

و سپس پوشه‌ای برای نگهداری اطلاعات build به نام build می‌سازیم (نام پوشه اصلا مهم نیست!)

cd opencv-2.4.11
mkdir build

پس از آن به پوشه مربوطه رفته

cd build

و دستور زیر را اجرا می‌کنیم. دقت کنید که مسیر‌های مربوط به پایتون را در این دستور مطابق شرایط نصب خود تغییر دهید

cmake -D CMAKE_BUILD_TYPE=RELEASE -D PYTHON_LIBRARY=/opt/anaconda/lib/python2.7/ -D PYTHON_INCLUDE_DIR=/opt/anaconda/include/python2.7/ -D PYTHON_PACKAGES_PATH=/opt/anaconda/lib/python2.7/site-packages/ -D BUILD_EXAMPLES=ON -D BUILD_NEW_PYTHON_SUPPORT=ON -D WITH_TBB=ON -D BUILD_NEW_PYTHON_SUPPORT=ON -D WITH_V4L=ON -D INSTALL_C_EXAMPLES=ON -D INSTALL_PYTHON_EXAMPLES=ON -D BUILD_EXAMPLES=ON -D WITH_QT=ON -D WITH_OPENGL=ON -D WITH_VTK=ON ..

پس از اینکه خروجی را کنترل کرده و مطمئن شدیم همه چیز درست است (یعنی رابط پایتون نصب می‌شود :) )، آنگاه نوبت به فرایند build و سپس نصب می‌رسد

make -j 4
sudo make install

پس از آن، در فایل (ممکن است فایل وجود نداشت باشد، اگر نبود، یکی بسازید)

/etc/ld.so.conf.d/opencv.conf

آدرس

/usr/local/lib

را درج کرده و فایل را ذخیره می‌کنیم. سپس، برای پیکربندی کتابخانه‌ها دستور

sudo ldconfig

را اجرا کرده و در فایل bashrc. موارد زیر را قرار می‌دهیم

export QT_QPA_PLATFORM_PLUGIN_PATH=/usr/lib/x86_64-linux-gnu/qt5/plugins
export PKG_CONFIG_PATH=$PKG_CONFIG_PATH:/usr/local/lib/pkgconfig

با بازکردن یک کنسول جدید، یا خارج و وارد شدن مجدد به محیط کاربری، می‌توانیم از صحت نصب با مراجعه به پوشه samples در پوشه opencv-2.4.11 و اجرای موفق مثال‌ها، مطمئن شویم که نصب به درستی صورت پذیرفته است!

۰ نظر موافقین ۰ مخالفین ۰ ۰۷ خرداد ۹۴ ، ۱۷:۳۹
علی شکیبا

برای تایپ از TeX Studio استفاده می‌کنم، اما تایپ متن فارسی با آن زجرآور است! به همین دلیل، ترجیح می‌دهم تا متن فارسی را در gedit تایپ کنم و خروجی آن را هم در evince ببینم. اما اجرای دستی xelatex زجرآور است، گرچه خیلی کمتر از زجر تایپ فارسی در TeX Studio است! اولین تلاش برای خودکار کردن به صورت زیر بود که هر دقیقه یکبار xelatex را اجرا می‌کرد!

while $( sleep 60s )
do
xelatex -synctex=-1 -interaction=nonstopmode report.tex
   bibtex report
   xelatex -synctex=-1 -interaction=nonstopmode report.tex
   xelatex -synctex=-1 -interaction=nonstopmode report.tex
done

این موضوع خوب بود تا اینکه زمان پایان اجرای xelatex کمی بیش از یک دقیقه شد! این بار دست به دامن اینترنت شدم! بسته inotify-tools دقیقا این کار را انجام می‌دهد!

while inotifywait -e close_write report.tex
do
xelatex -synctex=-1 -interaction=nonstopmode report.tex
   bibtex report
   xelatex -synctex=-1 -interaction=nonstopmode report.tex
   xelatex -synctex=-1 -interaction=nonstopmode report.tex
done

البته طبق آنچه که در اینجا آمده است، در صورتی که ویرایشگر شما به جای تغییر فایل، کل فایل را بازنویسی کند، gedit این گونه نیست!، باید از راهکار زیر استفاده کنید و پوشه را تحت مانیتور قرار دهید.

while true
do
change = $( inotifywait -e close_write,moved_to,create . )
change = ${change#./ *}
if [ "$change" = "report.tex" ]
then
xelatex -synctex=-1 -interaction=nonstopmode report.tex
    bibtex report
   xelatex -synctex=-1 -interaction=nonstopmode report.tex
   xelatex -synctex=-1 -interaction=nonstopmode report.tex
fi
done
۰ نظر موافقین ۰ مخالفین ۰ ۰۱ ارديبهشت ۹۴ ، ۱۱:۱۴
علی شکیبا

بسیاری از اوقات پیش می‌آید که خروجی یک بلوک کد بسیار طولانی است. به صورت طبیعی، هنگامی که پردازش به صورت دسته‌ای و در کنسول صورت می‌گیرد، چنین خروجی‌هایی معمولا در یک فایل ذخیره می‌شوند، اما در مورد IPython Notebook وضعیت کمی متفاوت است! در این وضع تمایل داریم خروجی را در ذیل بلوک کد ببینیم!

اما مشکل جایی آغاز می‌شود که خروجی بسیار طولانی است و این گونه فایل‌ها در مرورگر وب بارگذاری می‌شوند. برای من بسیار پیش آمده است که بارگذاری یک فایل منجر به هنگ و در نهایت کرش کردن مرورگر شود. به همین دلیل پاک کردن خروجی‌ها قبل از بازکردن فایل، راهکار مناسبی به نظر می‌رسد. بدین منظور کافی است در همان مسیر یک Notebook جدید را باز کرده و قطعه کد ذیل را در آن اجرا کنیم! فایلی هم نام با فایل مورد نظر که عبارت _removed به انتهای آن اضافه شده است، در همان مسیر تولید شده که شامل محتویات فایل مزبور منهای خروجی ها است. این راهکار از اینجا برداشته شده است.

import sys
import io
import os
from IPython.nbformat.current import read, write
def remove_outputs(nb):
"""remove the outputs from a notebook"""
for ws in nb.worksheets:
for cell in ws.cells:
if cell.cell_type == 'code':
cell.outputs = []

fname = "اسم فایل مورد نظر.ipynb"
with io.open(fname, 'r') as f:
nb = read(f, 'json')
remove_outputs(nb)
base, ext = os.path.splitext(fname)
new_ipynb = "%s_removed%s" % (base, ext)
with io.open(new_ipynb, 'w', encoding='utf8') as f:
write(nb, f, 'json')
print "wrote %s" % new_ipynb
۰ نظر موافقین ۰ مخالفین ۰ ۲۴ فروردين ۹۴ ، ۲۲:۳۲
علی شکیبا