?? index.htm
字號:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"> <head> <title>MIT OpenCourseWare | Electrical Engineering and Computer Science | 6.856J Randomized Algorithms, Fall 2002 | Lecture Notes </title> <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" /> <meta name="WT.cg_n" content="6-856JRandomized-AlgorithmsFall2002" /> <meta name="WT.cg_s" content="LectureNotes" /> <!-- Begin Automatic Metadata Insertion --><meta name="Title" content="Lecture Notes"/><meta name="Description" content=""/><meta name="Author" content="Karger, David"/><meta name="Keyword" content="Randomized Algorithms, efficient in time and space, computational problems, data structures, graph algorithms, optimization, geometry, Markov chains, estimation, geometric algorithms, randomization, random sampling, random selection of witnesses, symmetry breaking, randomized computational models, hash tables, skip lists, minimum spanning trees, shortest paths, minimum cuts, convex hulls, fixed dimension, arbitrary dimension, approximate counting, online algorithms, derandomization techniques, probabilistic analysis, computational number theory, simplicity, speed, design, basic probability theory, application, randomized complexity classes, game-theoretic techniques, Chebyshev, moment inequalities, limited independence, coupon collection, occupancy problems, tail inequalities, Chernoff bound, conditional expectation, probabilistic method, random walks, algebraic techniques, probability amplification, sorting, searching, combinatorial optimization, linear programming, approximation, counting problems, parallel algorithms, distributed algorithms, 6.856J, 18.416J, 6.856, 18.416"/><meta name="Version" content=""/><!-- End Automatic Metadata Insertion --> <link title="default" href="../../../../OcwWeb/style/common.css" type="text/css" rel="stylesheet"/> <link title="default" href="../../../../OcwWeb/style/courses.css" type="text/css" rel="stylesheet"/> <link rel="metadata" type="application/rdf+xml" href="../../../../OcwWeb/xml/ocwcc.rdf" /> <script type="text/javascript" src="../../../../OcwWeb/js/styleswitch.js"></script> </head> <body id="global" > <div id="container"> <form method="get" action="http://search.mit.edu/search"><input type="hidden" name="__EVENTTARGET" value="" /><input type="hidden" name="__EVENTARGUMENT" value="" /><script language="javascript" type="text/javascript"><!-- function __doPostBack(eventTarget, eventArgument) { var theform; if (window.navigator.appName.toLowerCase().indexOf("microsoft") > -1) { theform = document.CourseHomePage; } else { theform = document.forms["CourseHomePage"]; } theform.__EVENTTARGET.value = eventTarget.split("$").join(":"); theform.__EVENTARGUMENT.value = eventArgument; theform.submit(); }// --></script><script language="javascript" type="text/javascript"><!-- var __CMS_PostbackForm = document.forms['CourseHomePage']; var __CMS_CurrentUrl = "/OcwWeb/templates/section/GenericOther.aspx?NRMODE=Published&NRNODEGUID=%7b0BB579BC-AF2F-4459-909B-D2AE2288062D%7d&NRORIGINALURL=%2fOcwWeb%2fElectrical-Engineering-and-Computer-Science%2f6-856JRandomized-AlgorithmsFall2002%2fLectureNotes%2findex%2ehtm&NRCACHEHINT=Guest";// --></script> <div class="page_header"> <div class="logo"> <h1><a href="http://ocw.mit.edu/OcwWeb/web/home/home/index.htm"><img src="../../../../OcwWeb/images/logo-ocw-home_new.gif" alt="MIT OpenCourseWare" width="289" height="36" /></a></h1> </div> <!-- end header --></div><div id="primary_nav"> <ul id="nav"> <li class=""> <a href="http://ocw.mit.edu/OcwWeb/web/home/home/index.htm">Home</a></li> <li class="first active"> <a href="http://ocw.mit.edu/OcwWeb/web/courses/courses/index.htm">Courses</a></li> <li class=""> <a href="http://ocw.mit.edu/OcwWeb/web/donate/donate/index.htm">Donate</a></li> <li class=""> <a href="http://ocw.mit.edu/OcwWeb/web/about/about/index.htm" class="about_ocw">About OCW</a></li> </ul> <!-- begin search area, inputs are placed inside div blocks to validate xhtml strict --> <div class="searchform"> <div> <input type="hidden" name="site" value="ocw" /> <input type="hidden" name="client" value="mit" /> <input type="hidden" name="getfields" value="*" /> <input type="hidden" name="output" value="xml_no_dtd" /> <input type="hidden" name="proxystylesheet" value="http://ocw.mit.edu/OcwWeb/search/google-ocw.xsl" /> <input type="hidden" name="proxyreload" value="1" /> <input type="hidden" name="as_dt" value="i" /> <input type="hidden" name="oe" value="utf-8" /> <input type="hidden" name="departmentName" value="Electrical Engineering and Computer Science" /> <input type="hidden" name="courseName" value="" /> </div> <div> <input type="text" name="q" id="terms" maxlength="255" class="search" value="Enter search keyword" onfocus="clearSearchBox()" onblur="fillSearchBox()"/> <input type="image" src="../../../../OcwWeb/images/go_new.gif" name="btnG" alt="Go" class="but" /> <a href="../../../../OcwWeb/search/AdvancedSearch.htm">Advanced Search</a> </div> </div> <!-- end search area --> <ul id="secondary_nav"> <li class="first"> <a href="http://ocw.mit.edu/OcwWeb/web/help/help/index.htm">Help</a></li> <li> <a href="../../../../OcwWeb/jsp/feedback.jsp?Referer=">Contact Us</a></li> </ul> <!-- end Primary Nav --></div> <div id="main"> <div id="local_navigation"> <script language="javascript" type="text/javascript"><!--function MM_openBrWindow(theURL,winName,features) { window.open(theURL,winName,features);}// --></script> <!-- AE3305: Commented out: <table id="CourseLeftNav1_tblLeftNav" border="0"></table> --><!-- LeftNav --><div class="left-nav"> <div class= "get_started"><ul><li class="courses"><a href="http://ocw.mit.edu/OcwWeb/web/courses/courses/index.htm">VIEW ALL COURSES</a></li></ul></div><div class="get_started"><ul><li class = "courses"><a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/CourseHome/index.htm">Course Home</a></li><li><a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/Syllabus/index.htm">Syllabus</a></li><li><a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/Calendar/index.htm">Calendar</a></li><li><a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/LectureNotes/index.htm" class = "selected">Lecture Notes</a></li><li><a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/Assignments/index.htm">Assignments</a></li><li><a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/DownloadthisCourse/index.htm">Download this Course</a></li></ul></div></div><!-- End LeftNav --> </div> <div id="content_body"> <div class="page_links"> <div class="breadcrumb"><a href="http://ocw.mit.edu/OcwWeb/web/home/home/index.htm">Home</a> > <a href="http://ocw.mit.edu/OcwWeb/web/courses/courses/index.htm">Courses</a> > <a href="http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/index.htm">Electrical Engineering and Computer Science</a> > <span>Randomized Algorithms</span></div> <span id="switchbutton"></span> </div> <div id="main_content_course"> <div id="courses_inner"> <h1>Lecture Notes</h1> <div class="clear"></div> <div class="clear"></div> <div class="mod8"> <div class="bodycopy" id="BodyCopy1"> <table class="tbloutline" cellspacing="0" cellpadding="1" width="50%" summary="Course Table Outline" border="0"><tbody><tr><td><table class="datatable" cellspacing="0" cellpadding="8" width="100%" summary="Course Table Listing" border="1"><!-- BEGIN TABLE HEADER (for Table Template) --><thead><tr class="tableheader"><th id="col1" scope="col">LEC #</th><th id="col2" scope="col">TOPICS</th></tr></thead><!-- END TABLE HEADER --><tbody><tr class="gray-row"><td headers="col1">1</td><td headers="col2">Introduction to Randomized Algorithms (<a href="../../../../NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/7594FDEB-A1F0-4375-B6DB-69E8EC83F06A/0/n1.pdf">PDF</a>)</td></tr><tr class="white-row"><td headers="col1">2</td><td headers="col2">Min-Cut, Complexity Theory, Game Tree Evaluation (<a href="../../../../NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/EEF0212A-7A05-455C-8134-D70C38A80CE3/0/n2.pdf">PDF</a>)</td></tr><tr class="gray-row"><td headers="col1">3</td><td headers="col2">Adelman's Theorem, Game Theory, Lower Bounds (<a href="../../../../NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/5DA291F5-A5A8-46A5-A9D6-93F5957BA25C/0/n3.pdf">PDF</a>)</td>?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -