📄 http:^^www.lcs.mit.edu^web_project^brochure^toc^theory.html
字号:
Server: Netscape-Commerce/1.12
Date: Tuesday, 26-Nov-96 00:06:13 GMT
Last-modified: Thursday, 15-Jun-95 00:40:49 GMT
Content-length: 18834
Content-type: text/html
<!doctype html public "-//W30//DTD W3 HTML 2.0//EN"><HTML><TITLE>THEORY OF COMPUTATION GROUP</TITLE><center><!WA0><A HREF="http://theory.lcs.mit.edu/"><!WA1><IMG SRC=http://www.lcs.mit.edu/web_project/Brochure/toc/tocline.gif></a></center><p><body><p>As one of the world's largest groups of theoretical computerresearchers, the Laboratory for Computer Science (LCS)pursues nearly every major area of computer technology. Ourinterests range from basic mathematical theory -- such ascomputational geometry, complexity theory, andnumber-theoretic algorithms -- to theoretical work on thefoundations of electronic circuitry, communications,biology, cryptography, and computer architectures.<p>An important goal of theoretical computer science is tocreate formal models of computation, then explore what ispossible within those models. The results not only deepenour understanding of the basics of computer science, butalso alter its practice through more efficient algorithms,novel architectures, and a better understanding of aprogram's "meaning." While many of these models reflectrecent technological advances -- parallel or distributedcomputing, for example -- work also is performed on suchtraditional models as finite automata and ordinarysequential computers.<p><ul> <li><!WA2><a href=#palg>Parallel Algorithms </a><li><!WA3><a href=#alg>Efficient Algorithms</a><li><!WA4><a href=#sc>Scientific Computing</a><li><!WA5><a href=#cdb>Computational Biology</a><li><!WA6><a href=#ml>Machine Learning</a> <li><!WA7><a href=#cc>Computational Complexity</a><li><!WA8><a href=#crypt>Cryptographic Protocols</a><li><!WA9><a href=#psem>Program Semantics </a><li><!WA10><a href=#tds>Distributed Computing</a></ul><p>MIT is the world's leader in <a name=palg><b>parallel algorithms andarchitectures</b>. We thus work closely with architects andsystems designers to create the next generation of parallelsupercomputers. Faculty and students interact with suchleading companies as Thinking Machines and IBM to designand analyze communication networks, parallel computationmodels, efficient parallel algorithms for variousapplications, and methods for making large-scale parallelmachines more fault-tolerant.<p>Not surprisingly, we are deeply involved in the design anduse of the forthcoming "information highway." Efficientnetwork-based communications, in fact, is one of the mostimportant and exciting challenges facing theoryresearchers.<p><center><table border><tr> <td><!WA11><img src=http://www.lcs.mit.edu/web_project/Brochure/toc/leighton.gif></td> <td width=100 rowspan=2><br></td> <td><!WA12><img src=http://www.lcs.mit.edu/web_project/Brochure/toc/goemans.gif></td> </tr><tr><td> <address><b>Tom Leighton</b></a>,<br>Professor of Applied Mathematics<br> (Parallel Algorithms)</address> </td><td><address><b>Michel Goemans</b></a>,<br>Assistant Professor of Applied<br>Mathematics (Efficient Algorithms)</address></td> </tr></table></center><p>LCS also vigorously researches <a name=alg><b>efficient algorithms</b> forsequential computers. Surprisingly, perhaps, improvedalgorithms for well-known problems continue to bediscovered, and new theoretical problems often arise asspin-offs from advances in computer technology. Some of ourwork focuses on algorithms for graph problems,computational geometry, number-theoretic problems, and thelaying out and routing of VLSI circuitry. Other recentprojects include on-line algorithms (which do not know allthe data in advance), randomized algorithms (which userandom numbers to aid decision-making), and approximationalgorithms (which are guaranteed to find near-optimumsolutions).<p>Many fundamental problems that provide insight into thedesign and analysis of efficient algorithms lie in the areaof combinatorial optimization. We recently have seen asurge of exciting developments in approximation algorithmsfor difficult optimization problems, and LCS is a leader inobtaining novel and general techniques for designing suchalgorithms. We have developed improved approximationalgorithms for a variety of problems, including thoserelated to multicommodity flow and network design, as wellas more specific problems such as the graph bisectionproblem or the maximum cut problem.<p><center><table border><tr> <td><!WA13><img src=http://www.lcs.mit.edu/web_project/Brochure/toc/edelman.gif></td> <td width=100 rowspan=2><br></td> <td><!WA14><img hspace=8 src=http://www.lcs.mit.edu/web_project/Brochure/toc/karger.gif></td></tr><tr> <td><!WA15><A HREF="http://theory.lcs.mit.edu/~edelman"><address><b>Alan Edelman</b></a>,<br>Assistant Professor of <br>Applied Mathematics <br>(Scientific Computing)</address></td><td><!WA16><A HREF="http://theory.lcs.mit.edu/~karger"> <address><b>David R. Karger</b></a>,<br>Assistant Professor of<br>Computer Science <br>and Engineering (Algorithms)</address></td></tr></table></center><p>Largely as a result of rapid advances in parallel computingtechnology,<a name=sc><b>scientific computing</b> has become one ofcomputer science's most active areas. Thisinterdisciplinary area bridges numerical analysis, linearalgebra, computer architecture, program analysis andoptimization, software engineering, scientificvisualization, and various scientific applications.<p>Problems in scientific computing often strain the resourcesof modern parallel machines, compelling us to advance newtools and ideas. LCS researchers have pioneered theadaptation of algorithms for the special needs of thesescientific applications.<p>Scientific computing involves various research topics intheoretical computer science, such as finite element andfinite difference mesh generation, sparse and dense matrixcomputations, and the solution of large-scale linearsystems. Some of these problems can be translated into orapproximated by combinatorial and geometric problems,including network optimization, communication networktopology emulation, graph embedding, parallel machinescheduling, dynamic load balancing, geometric modeling, andtriangulations.A fundamental issue in parallel scientific computing ismesh partitioning, in which a large mesh is divided into agiven number of pieces of roughly equal weights so that the"boundary" is "small." Efficient partitioning is vital tobalance the load and reduce communication in parallelsolutions of sparse linear systems. It is also useful inparallel emulation of computational meshes on hypercube andbutterfly architectures and out-of-core algorithms foriterative relaxation.<p><a name=cdb><b>Computational biology</b></a> represents another new andexciting research area. Accordingly, one of our goals is toexpand the computational "toolkit" that is available fornumerous biological problems.<p>Computer science, for example, helps make sense of the vastamount of information now being compiled for the HumanGenome project, such as DNA and amino-acid sequence data.One intra-MITeffort has drawn on the resources of LCS, theWhitehead Institute, and the Biology and Mathematicsdepartments; specific research areas include computationalapproaches to protein folding, physical and geneticmapping, virus shell assembly, AIDS theories, and sequencehomology and alignment.<p>Yet another illustration of computational biology relatesto the so-called "grand challenge" associated with proteinfolding -- that is, the determination of how a protein willfold three-dimensionally when only its amino-acid sequenceis known. An important first step in answering thisquestion is a solution to the motif recognition problem:Given a known 3D structure (or motif), researchers mustdetermine whether the fold occurs in an unknown sequence ofamino acids and, if so, in which positions. Techniques fromtheoretical computer science have been particularlyeffective in solving such problems.<p><p><a name=ml><center><table border><tr> <td><!WA17><img src=http://www.lcs.mit.edu/web_project/Brochure/toc/rivest.gif></td> <td width=100 rowspan=2><br></td> <td><!WA18><img src=http://www.lcs.mit.edu/web_project/Brochure/toc/berger.gif></td> </tr><tr><td> <!WA19><A HREF="http://theory.lcs.mit.edu/~rivest"><address><b>Ronald L. Rivest,</b></a><br>Edwin Sibley Webster<br>Professor of Computer Science<br> and Engineering <br>Associate Director, LCS (Machine Learning)</address> </td><td> <address><b>Bonnie A. Berger</b></a>,<br>Assistant Professor of Mathematics<br> (Computational Biology)</address></td> </tr></table></center><p>On another front, researchers in <a name=ml><b>machine learning</b> studycomputers' ability to "learn" from experience. The resultsof our research have stimulated various formalizations thataddress a range of issues in psychology, artificialintelligence, pattern recognition, and neurobiology. Somerecent research themes include the inference of finiteautomata; learning in the presence of noise; learning anunknown environment "piecemeal" by exploration; learning of"manifest" systems (in which relevant variables are often,but not always, visible to the learner), and models of"teaching."<p>In general, the group's research is "positive" in nature,in that we strive to develop provably efficient learningalgorithms with potentially practical application. In somecases, however, the research leads to equally useful"negative" results by identifying the limits of what isultimately learnable.<p>Another major theme is the development of new models of⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -