اشکال تمرین تقریبی ۲

سوال ۳ تمرین را با روش وزیرانی نمی‌شود حل کرد چون اینجا الآن نمی‌توانیم مطمئن باشیم که دقیقاً ۲ تا متغیر داریم! (فکر کنم سوالش غلط است)

همین مسأله را به روش دیگری LP برایش نوشته و حل شده است اما در صورت سوال ما گفته است که این طوری باید بنویسید.

عالی ۲

بعد از اینکه با کلی زحمت تمرین هندسه را حل کردم دیدم یک هفته دیگر وقت دارد.

The Szemerédi-Trotter theorem and the cell decomposition

دریافت
حجم: 475 کیلوبایت

عالی!

http://maktabkhooneh.org/course?course=abam266

اصلاحیه ترجمه!

additive رو ترجمه می‌کنند خطی نه جمعی! :))

خوشه‌بندی بر مبنای چگالی

دریافت
حجم: 2.14 مگابایت

جزوه..

*اگر از گراف G به ازای هر تقاطع انقدر یال حذف کنیم که دیگر تقاطع نباشد به گراف G' می‌رسیم که مسطح است. چون گراف مسطح است تعداد یالهای آن از مرتبه‌ی تعداد رأسهای آن است. پس m' < m+x است که x تعداد تقاطع‌های گراف G است.

*روش احتمالاتی: هر رأس را با احتمال p در گراف نگه می‌داریم. در نتیجه متوسط تعداد رأسها pn، متوسط تعداد یالها p^2 n و متوسط تعداد تقاطع‌ها p^4 n می‌شود. طبق قضیه قبلی تعداد یالها به صورت متوسط جمع تعداد رأسها و تعداد تقاطع‌ها است.

تقاطع پاره‌خط‌ها

منبع: clarkson 89 applications of random sampling in CG

Algorithms and Data Structures Fall 2007

http://www.cs.princeton.edu/~rs/AlgsDS07/

Overview

Union-Find Algorithms

Stacks and Queues

Sorting Algorithms

Advanced Topics in Sorting

Priority Queues

Symbol Tables

Binary Search Trees

Balanced Trees

Hashing

Undirected Graphs

Directed Graphs

Minimum Spanning Trees

Shortest Paths

Geometric Algorithms

Search and Intersection

Radix Sorts

Tries

Data Compression

Pattern Matching

Linear Programming

Reductions

Combinatorial Search

Feedback vertex set

http://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec9.pdf

http://www.sciencedirect.com/science/article/pii/S0022000008000500