📄 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 | Home </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="CourseHome" /> <!-- Begin Automatic Metadata Insertion --><meta name="Title" content="Randomized Algorithms"/><meta name="Description" content="Studies how randomization can be used to make algorithms simpler and more efficient via random sampling, random selection of witnesses, symmetry breaking, and Markov chains. Models of randomized computation. Data structures: hash tables, and skip lists. Graph algorithms: minimum spanning trees, shortest paths, and minimum cuts. Geometric algorithms: convex hulls, linear programming in fixed or arbitrary dimension. Approximate counting; parallel algorithms; online algorithms; derandomization techniques; and tools for probabilistic analysis of algorithms. Alternate years."/><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="1"/><!-- 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 > <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/CourseHomePage.aspx?NRMODE=Published&NRNODEGUID=%7bD727C82D-D7D1-432A-9DBD-ED4C586A4950%7d&NRORIGINALURL=%2fOcwWeb%2fElectrical-Engineering-and-Computer-Science%2f6-856JRandomized-AlgorithmsFall2002%2fCourseHome%2findex%2ehtm&NRCACHEHINT=Guest";// --></script> <a href="#main" class="skip" tabindex="-1">skip to content</a> <a id="top"></a> <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" class = "selected">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">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"> <div id="courses"> <h1>6.856J / 18.416J Randomized Algorithms</h1> <h3 class="term"> Fall 2002</h3> <div class="maincontent"> <div class="course1"> <span id="Singleimageplaceholdercontrol1" title="Unstructured grid for a four element airfoil."><a id="Singleimageplaceholdercontrol1_PresentationModeControlsContainer_PresentationHyperLink"><img id="Singleimageplaceholdercontrol1_PresentationModeControlsContainer_PresentationImage" src="../../../../NR/rdonlyres/Global/A/A3908774-DC8D-473C-BD55-85FC0885BC56/0/chp_algorithm_1.jpg" alt="Unstructured grid for a four element airfoil." border="0" /></a></span> <div class="image-caption" id="Htmlplaceholdercontrol1"> Partitioning algorithms are used to solve complex large scale computational problems, as shown in this unstructured grid for a four element airfoil. (Image is taken from NASA's Web site: <a href="http://www.nasa.gov" target="_blank">http://www.nasa.gov</a>.)</div> <h4>Course Highlights</h4> <div class="coursehighlights" id="Highlights"> <span class="bodycopy">This course site features a full set of <a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/LectureNotes/index.htm">lecture notes</a> and <a href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/Assignments/index.htm">problem sets with solutions</a>.</span></div> <h4>Course Description</h4> <div class="coursedescription" id="Description"> <span class="bodycopy">This course examines how randomization can be used to make algorithms simpler and more efficient via random sampling, random selection of witnesses, symmetry breaking, and Markov chains. Topics covered include: randomized computation; data structures (hash tables, skip lists); graph algorithms (minimum spanning trees, shortest paths, minimum cuts); geometric algorithms (convex hulls, linear programming in fixed or arbitrary dimension); approximate counting; parallel algorithms; online algorithms; derandomization techniques; and tools for probabilistic analysis of algorithms.</span></div> </div> </div> </div> <!-- end courses div --></div> <!-- end of main_content div --> <div id="callout"><a href="http://ocw.mit.edu/OcwWeb/web/donate/donate/index.htm"><img src="../../../../OcwWeb/images/donate-button.gif" alt="Donate Now" width="171" height="25" border="0"></a> <!-- begin right column --> <div class="module"> <h3>Staff</h3> <div class="chpstaff"><div id="Htmlplaceholder2" style="width:190;"> Instructor:<br />Prof. David R. Karger</div></div> <h3>Course Meeting Times</h3> <div class="chpmeetingtimes"><div id="Htmlplaceholder3" style="width:190;"> Lectures:<br />Two sessions / week<br />1.5 hour / session</div></div> <h3>Level</h3> <div class="chpcourselevel"><span id="lblLevel">Graduate</span></div> </div> <p><table id="PanelAdditionalFeature" cellpadding="0" cellspacing="0" border="0" width="100%"><tr><td> <div class="module"> <h3> </h3> <a id="rptVisibleCategory__ctl0_HLCategory" class="dnload" href="../../../../OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/DownloadthisCourse/index.htm">Download this course</a> </div> </td></tr></table></p> <div class="module"> <h3>Feedback</h3> <p><a href="../../../../OcwWeb/jsp/feedback.jsp?Referer=" class="bullet">Send feedback on this course.</a></p> </div> </div> <!--end of callout div --> <div class="clear"></div> </div> <!-- end of content_body div --></div> <!-- end of main div --> <div class="footer"> <div class="footer_logo"> <a href="http://web.mit.edu"><img src="../../../../OcwWeb/images/trans.gif" alt="MIT Logo" width="65" height="35" align="top" title="MIT Logo"></a> <a href="../../../../OcwWeb/web/terms/terms/index.htm"><img src="../../../../OcwWeb/images/trans.gif" alt="Copyright 2002-2007 MIT" width="100" height="13" align="textTop" title="Copyright 2002-2007 MIT"></a> </div> <div class="footer_links"> <ul> <li class="first"> <a href="http://ocw.mit.edu/OcwWeb/web/about/rss/index.htm"><img src="../../../../OcwWeb/images/footer_rss_new.gif" border="0" width="32" height="15" align="absbottom" alt="RSS Feeds"></a><a href="http://ocw.mit.edu/OcwWeb/web/about/rss/index.htm">RSS Feeds</a> <li> <a href="../../../../OcwWeb/web/terms/terms/index.htm">Privacy and Terms of Use</a> <li> <a href="http://ocw.mit.edu/OcwWeb/web/help/sitemap/index.htm">Site Map</a></li> </ul> <p>Your use of the MIT OpenCourseWare site and course materials is subject to our Creative Commons License and other terms of use.</p> <!-- end footer links --> </div> <div class="license"> <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/us/" target="_blank" class="first"><img src="../../../../OcwWeb/images/cc_logo_new.gif" alt="Creative Commons - some rights reserved" border="0" width="80" height="15"></a><br> <a rel="license" href="http://www.ocwconsortium.org/" target="_blank" class="first"> <img src="../../../../OcwWeb/images/ocw-logo_new.gif" alt="OCW Consortium" width="80" height="44"></a></div></div><DIV></DIV><!-- end footer --><!-- Start Webtrends Tracking Tag --><noscript> <div> </div></noscript><!-- End Webtrends Tracking Tag --> </A> </form> </div> </body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -