Searching for completeness : 27 results found | RSS Feed for this search

1

6.045J Automata, Computability, and Complexity (MIT) 6.045J Automata, Computability, and Complexity (MIT)

Description

This course is offered to undergraduates and introduces basic mathematical models of computation and the finite representation of infinite objects. The course is slower paced than 6.840J/18.404J. Topics covered include: finite automata and regular languages, context-free languages, Turing machines, partial recursive functions, Church's Thesis, undecidability, reducibility and completeness, time complexity and NP-completeness, probabilistic computation, and interactive proof systems. This course is offered to undergraduates and introduces basic mathematical models of computation and the finite representation of infinite objects. The course is slower paced than 6.840J/18.404J. Topics covered include: finite automata and regular languages, context-free languages, Turing machines, partial recursive functions, Church's Thesis, undecidability, reducibility and completeness, time complexity and NP-completeness, probabilistic computation, and interactive proof systems.

Subjects

automata | automata | computability | computability | complexity | complexity | mathematical models | mathematical models | computation | computation | finite representation | finite representation | infinite objects | infinite objects | finite automata | finite automata | regular languages | regular languages | context-free languages | context-free languages | Turing machines | Turing machines | partial recursive functions | partial recursive functions | Church's Thesis | Church's Thesis | undecidability | undecidability | reducibility | reducibility | completeness | completeness | time complexity | time complexity | NP-completeness | NP-completeness | probabilistic computation | probabilistic computation | interactive proof systems | interactive proof systems | 6.045 | 6.045 | 18.400 | 18.400

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see http://ocw.mit.edu/terms/index.htm

Site sourced from

http://ocw.mit.edu/rss/all/mit-allarchivedcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

6.045J Automata, Computability, and Complexity (MIT) 6.045J Automata, Computability, and Complexity (MIT)

Description

This course introduces basic mathematical models of computation and the finite representation of infinite objects. Topics covered include: finite automata and regular languages, context-free languages, Turing machines, partial recursive functions, Church's Thesis, undecidability, reducibility and completeness, time complexity and NP-completeness, probabilistic computation, and interactive proof systems. This course introduces basic mathematical models of computation and the finite representation of infinite objects. Topics covered include: finite automata and regular languages, context-free languages, Turing machines, partial recursive functions, Church's Thesis, undecidability, reducibility and completeness, time complexity and NP-completeness, probabilistic computation, and interactive proof systems.

Subjects

automata | automata | computability | computability | complexity | complexity | mathematical models | mathematical models | computation | computation | finite representation | finite representation | infinite objects | infinite objects | finite automata | finite automata | regular languages | regular languages | context-free languages | context-free languages | Turing machines | Turing machines | partial recursive functions | partial recursive functions | Church's Thesis | Church's Thesis | undecidability | undecidability | reducibility | reducibility | completeness | completeness | time complexity | time complexity | NP-completeness | NP-completeness | probabilistic computation | probabilistic computation | interactive proof systems | interactive proof systems | 6.045 | 6.045 | 18.400 | 18.400

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see http://ocw.mit.edu/terms/index.htm

Site sourced from

http://ocw.mit.edu/rss/all/mit-allarchivedcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

18.404J Theory of Computation (MIT) 18.404J Theory of Computation (MIT)

Description

A more extensive and theoretical treatment of the material in 18.400J, Automata, Computability, and Complexity, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems. A more extensive and theoretical treatment of the material in 18.400J, Automata, Computability, and Complexity, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems.

Subjects

computability | computability | computational complexity theory | computational complexity theory | Regular and context-free languages | Regular and context-free languages | Decidable and undecidable problems | Decidable and undecidable problems | reducibility | reducibility | recursive function theory | recursive function theory | Time and space measures on computation | Time and space measures on computation | completeness | completeness | hierarchy theorems | hierarchy theorems | inherently complex problems | inherently complex problems | oracles | oracles | probabilistic computation | probabilistic computation | interactive proof systems | interactive proof systems | 18.404 | 18.404 | 6.840 | 6.840

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see http://ocw.mit.edu/terms/index.htm

Site sourced from

http://ocw.mit.edu/rss/all/mit-allarchivedcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

22.091 Nuclear Reactor Safety (MIT) 22.091 Nuclear Reactor Safety (MIT)

Description

Problems in nuclear engineering often involve applying knowledge from many disciplines simultaneously in achieving satisfactory solutions. The course will focus on understanding the complete nuclear reactor system including the balance of plant, support systems and resulting interdependencies affecting the overall safety of the plant and regulatory oversight. Both the Seabrook and Pilgrim nuclear plant simulators will be used as part of the educational experience to provide as realistic as possible understanding of nuclear power systems short of being at the reactor. Problems in nuclear engineering often involve applying knowledge from many disciplines simultaneously in achieving satisfactory solutions. The course will focus on understanding the complete nuclear reactor system including the balance of plant, support systems and resulting interdependencies affecting the overall safety of the plant and regulatory oversight. Both the Seabrook and Pilgrim nuclear plant simulators will be used as part of the educational experience to provide as realistic as possible understanding of nuclear power systems short of being at the reactor.

Subjects

nuclear | nuclear | reactor | reactor | safety | safety | dryout heat flux | dryout heat flux | preexisting hydrogen | preexisting hydrogen | blowdown gases | blowdown gases | downward propagation limit | downward propagation limit | debris dispersal | debris dispersal | direct containment heating | direct containment heating | gas blowthrough | gas blowthrough | seal table room | seal table room | subcompartment structures | subcompartment structures | compartmentalized geometries | compartmentalized geometries | overlying liquid layer | overlying liquid layer | preexisting atmosphere | preexisting atmosphere | blowdown time | blowdown time | melt generator | melt generator | detonation adiabatic | detonation adiabatic | thermohydraulic codes | thermohydraulic codes | hydrodynamic fragmentation | hydrodynamic fragmentation | vent clearing | vent clearing | combustion completeness | combustion completeness | containment pressurization | containment pressurization | melt retention | melt retention | containment loads | containment loads | melt ejection | melt ejection | containment geometry | containment geometry | hole ablation | hole ablation | Sandia National Laboratories | Sandia National Laboratories | Heat Transfer Conf | Heat Transfer Conf | Nuclear Regulatory Commission Report | Nuclear Regulatory Commission Report | Heat Mass Transfer | Heat Mass Transfer | The Combustion Institute | The Combustion Institute | Combustion Symposium International | Combustion Symposium International | New York | New York | Santa Barbara | Santa Barbara | Argonne National Laboratory | Argonne National Laboratory | Fluid Mech | Fluid Mech | Zion Probabilistic Safety Study | Zion Probabilistic Safety Study | Los Angeles | Los Angeles | Impact of Hydrogen | Impact of Hydrogen | Topical Meeting | Topical Meeting | Water Reactor Safety | Water Reactor Safety | Water Trans | Water Trans | Academic Press All | Academic Press All | American Society of Mechanical Engineers | American Society of Mechanical Engineers | Specialists Meeting | Specialists Meeting | University of California | University of California | Brookhaven National Laboratory | Brookhaven National Laboratory | Calvert Cliffs | Calvert Cliffs | Fourth Int | Fourth Int | International Conference | International Conference | New Trends. | New Trends.

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see http://ocw.mit.edu/terms/index.htm

Site sourced from

http://ocw.mit.edu/rss/all/mit-allcourses-energy.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

6.080 Great Ideas in Theoretical Computer Science (MIT) 6.080 Great Ideas in Theoretical Computer Science (MIT)

Description

This course provides a challenging introduction to some of the central ideas of theoretical computer science. It attempts to present a vision of "computer science beyond computers": that is, CS as a set of mathematical tools for understanding complex systems such as universes and minds. Beginning in antiquity—with Euclid's algorithm and other ancient examples of computational thinking—the course will progress rapidly through propositional logic, Turing machines and computability, finite automata, Gödel's theorems, efficient algorithms and reducibility, NP-completeness, the P versus NP problem, decision trees and other concrete computational models, the power of randomness, cryptography and one-way functions, computational theories of learning, interactive proofs, and q This course provides a challenging introduction to some of the central ideas of theoretical computer science. It attempts to present a vision of "computer science beyond computers": that is, CS as a set of mathematical tools for understanding complex systems such as universes and minds. Beginning in antiquity—with Euclid's algorithm and other ancient examples of computational thinking—the course will progress rapidly through propositional logic, Turing machines and computability, finite automata, Gödel's theorems, efficient algorithms and reducibility, NP-completeness, the P versus NP problem, decision trees and other concrete computational models, the power of randomness, cryptography and one-way functions, computational theories of learning, interactive proofs, and q

Subjects

computer science | computer science | theoretical computer science | theoretical computer science | logic | logic | turing machines | turing machines | computability | computability | finite automata | finite automata | godel | godel | complexity | complexity | polynomial time | polynomial time | efficient algorithms | efficient algorithms | reducibility | reducibility | p and np | p and np | np completeness | np completeness | private key cryptography | private key cryptography | public key cryptography | public key cryptography | pac learning | pac learning | quantum computing | quantum computing | quantum algorithms | quantum algorithms

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see http://ocw.mit.edu/terms/index.htm

Site sourced from

http://ocw.mit.edu/rss/all/mit-allcourses-6.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

6.896 Theory of Parallel Hardware (SMA 5511) (MIT) 6.896 Theory of Parallel Hardware (SMA 5511) (MIT)

Description

6.896 covers mathematical foundations of parallel hardware, from computer arithmetic to physical design, focusing on algorithmic underpinnings. Topics covered include: arithmetic circuits, parallel prefix, systolic arrays, retiming, clocking methodologies, boolean logic, sorting networks, interconnection networks, hypercubic networks, P-completeness, VLSI layout theory, reconfigurable wiring, fat-trees, and area-time complexity. This course was also taught as part of the Singapore-MIT Alliance (SMA) programme as course number SMA 5511 (Theory of Parallel Hardware). 6.896 covers mathematical foundations of parallel hardware, from computer arithmetic to physical design, focusing on algorithmic underpinnings. Topics covered include: arithmetic circuits, parallel prefix, systolic arrays, retiming, clocking methodologies, boolean logic, sorting networks, interconnection networks, hypercubic networks, P-completeness, VLSI layout theory, reconfigurable wiring, fat-trees, and area-time complexity. This course was also taught as part of the Singapore-MIT Alliance (SMA) programme as course number SMA 5511 (Theory of Parallel Hardware).

Subjects

parallel hardware | parallel hardware | computer arithmetic | computer arithmetic | physical design | physical design | algorithms | algorithms | arithmetic circuits | arithmetic circuits | parallel prefix | parallel prefix | systolic arrays | systolic arrays | retiming | retiming | clocking methodologies | clocking methodologies | boolean logic | boolean logic | sorting networks | sorting networks | interconnection networks | interconnection networks | hypercubic networks | hypercubic networks | P-completeness | P-completeness | VLSI layout theory | VLSI layout theory | reconfigurable wiring | reconfigurable wiring | fat-trees | fat-trees | area-time complexity | area-time complexity

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see http://ocw.mit.edu/terms/index.htm

Site sourced from

http://ocw.mit.edu/rss/all/mit-allcourses-6.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

6.844 Computability Theory of and with Scheme (MIT) 6.844 Computability Theory of and with Scheme (MIT)

Description

6.844 is a graduate introduction to programming theory, logic of programming, and computability, with the programming language Scheme used to crystallize computability constructions and as an object of study itself. Topics covered include: programming and computability theory based on a term-rewriting, "substitution" model of computation by Scheme programs with side-effects; computation as algebraic manipulation: Scheme evaluation as algebraic manipulation and term rewriting theory; paradoxes from self-application and introduction to formal programming semantics; undecidability of the Halting Problem for Scheme; properties of recursively enumerable sets, leading to Incompleteness Theorems for Scheme equivalences; logic for program specification and verification; and Hilbert's Tenth Prob 6.844 is a graduate introduction to programming theory, logic of programming, and computability, with the programming language Scheme used to crystallize computability constructions and as an object of study itself. Topics covered include: programming and computability theory based on a term-rewriting, "substitution" model of computation by Scheme programs with side-effects; computation as algebraic manipulation: Scheme evaluation as algebraic manipulation and term rewriting theory; paradoxes from self-application and introduction to formal programming semantics; undecidability of the Halting Problem for Scheme; properties of recursively enumerable sets, leading to Incompleteness Theorems for Scheme equivalences; logic for program specification and verification; and Hilbert's Tenth Prob

Subjects

Scheme | Scheme | programming theory | programming theory | logic of programming | logic of programming | computability | computability | programming language | programming language | Scheme evaluation | Scheme evaluation | algebraic manipulation | algebraic manipulation | term rewriting theory | term rewriting theory | programming semantics | programming semantics | Halting Problem for Scheme | Halting Problem for Scheme | Incompleteness Theorems | Incompleteness Theorems | Hilbert's Tenth Problem | Hilbert's Tenth Problem

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see http://ocw.mit.edu/terms/index.htm

Site sourced from

http://ocw.mit.edu/rss/all/mit-allcourses-6.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

18.404J Theory of Computation (MIT) 18.404J Theory of Computation (MIT)

Description

This graduate level course is more extensive and theoretical treatment of the material in Computability, and Complexity (6.045J / 18.400J). Topics include Automata and Language Theory, Computability Theory, and Complexity Theory. This graduate level course is more extensive and theoretical treatment of the material in Computability, and Complexity (6.045J / 18.400J). Topics include Automata and Language Theory, Computability Theory, and Complexity Theory.

Subjects

Computability | computational complexity theory | Computability | computational complexity theory | Regular and context-free languages | Regular and context-free languages | Decidable and undecidable problems | reducibility | recursive function theory | Decidable and undecidable problems | reducibility | recursive function theory | Time and space measures on computation | completeness | hierarchy theorems | inherently complex problems | oracles | probabilistic computation | and interactive proof systems | Time and space measures on computation | completeness | hierarchy theorems | inherently complex problems | oracles | probabilistic computation | and interactive proof systems

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see http://ocw.mit.edu/terms/index.htm

Site sourced from

http://ocw.mit.edu/rss/all/mit-allcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

18.725 Algebraic Geometry (MIT) 18.725 Algebraic Geometry (MIT)

Description

This course covers the fundamental notions and results about algebraic varieties over an algebraically closed field. It also analyzes the relations between complex algebraic varieties and complex analytic varieties. This course covers the fundamental notions and results about algebraic varieties over an algebraically closed field. It also analyzes the relations between complex algebraic varieties and complex analytic varieties.

Subjects

algebraic varieties over algebraically closed field | algebraic varieties over algebraically closed field | complex algebraic varieties | complex algebraic varieties | complex analytic varieties | complex analytic varieties | curves and surfaces | curves and surfaces | irreducible components | irreducible components | projective space | projective space | topological diversion | topological diversion | sheaves | sheaves | presheaves | presheaves | algebraic geometry | algebraic geometry | fibers | fibers | morphisms | morphisms | varieties | varieties | projective varieties | projective varieties | applications | applications | dimension | dimension | krull dimension | krull dimension | completeness | completeness | complex topology | complex topology | Chow's lemma | Chow's lemma | analytic spaces | analytic spaces | curves | curves

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see http://ocw.mit.edu/terms/index.htm

Site sourced from

http://ocw.mit.edu/rss/all/mit-allcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

24.242 Logic II (MIT) 24.242 Logic II (MIT)

Description

This course begins with an introduction to the theory of computability, then proceeds to a detailed study of its most illustrious result: Kurt Gödel's theorem that, for any system of true arithmetical statements we might propose as an axiomatic basis for proving truths of arithmetic, there will be some arithmetical statements that we can recognize as true even though they don't follow from the system of axioms. In my opinion, which is widely shared, this is the most important single result in the entire history of logic, important not only on its own right but for the many applications of the technique by which it's proved. We'll discuss some of these applications, among them: Church's theorem that there is no algorithm for deciding when a formula is valid in the predicate calculus; This course begins with an introduction to the theory of computability, then proceeds to a detailed study of its most illustrious result: Kurt Gödel's theorem that, for any system of true arithmetical statements we might propose as an axiomatic basis for proving truths of arithmetic, there will be some arithmetical statements that we can recognize as true even though they don't follow from the system of axioms. In my opinion, which is widely shared, this is the most important single result in the entire history of logic, important not only on its own right but for the many applications of the technique by which it's proved. We'll discuss some of these applications, among them: Church's theorem that there is no algorithm for deciding when a formula is valid in the predicate calculus;

Subjects

Logic | Logic | theory of computability | theory of computability | Kurt G?del | Kurt G?del | theorem | theorem | system | system | true | true | arithmetical | arithmetical | statements | statements | axiomatic basis | axiomatic basis | proving | proving | truths of arithmetic | truths of arithmetic | history applications | history applications | technique | technique | Church?s theorem | Church?s theorem | algorithm | algorithm | formula | formula | valid | valid | predicate calculus | predicate calculus | Tarski?s theorem | Tarski?s theorem | G?del?s second incompleteness theorem. | G?del?s second incompleteness theorem.

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see http://ocw.mit.edu/terms/index.htm

Site sourced from

http://ocw.mit.edu/rss/all/mit-allcourses-24.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (MIT) 6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (MIT)

Description

Includes audio/video content: AV lectures. 6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs is a class taking a practical approach to proving problems can't be solved efficiently (in polynomial time and assuming standard complexity-theoretic assumptions like P ≠ NP). The class focuses on reductions and techniques for proving problems are computationally hard for a variety of complexity classes. Along the way, the class will create many interesting gadgets, learn many hardness proof styles, explore the connection between games and computation, survey several important problems and complexity classes, and crush hopes and dreams (for fast optimal solutions). Includes audio/video content: AV lectures. 6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs is a class taking a practical approach to proving problems can't be solved efficiently (in polynomial time and assuming standard complexity-theoretic assumptions like P ≠ NP). The class focuses on reductions and techniques for proving problems are computationally hard for a variety of complexity classes. Along the way, the class will create many interesting gadgets, learn many hardness proof styles, explore the connection between games and computation, survey several important problems and complexity classes, and crush hopes and dreams (for fast optimal solutions).

Subjects

NP-completeness | NP-completeness | 3SAT | 3SAT | 3-partition | 3-partition | Hamiltonicity | Hamiltonicity | PSPACE | PSPACE | EXPTIME | EXPTIME | EXPSPACE | EXPSPACE | games | games | puzzles | puzzles | computation | computation | Tetris | Tetris | Nintendo | Nintendo | Super Mario Bros. | Super Mario Bros. | The Legend of Zelda | The Legend of Zelda | Metroid | Metroid | Pokémon | Pokémon | constraint logic | constraint logic | Sudoku | Sudoku | Nikoli | Nikoli | Chess | Chess | Go | Go | Othello | Othello | board games | board games | inapproximability | inapproximability | PCP theorem | PCP theorem | OPT-preserving reduction | OPT-preserving reduction | APX-hardness | APX-hardness | vertex cover | vertex cover | Set-cover hardness | Set-cover hardness | Group Steiner tree | Group Steiner tree | k-dense subgraph | k-dense subgraph | label cover | label cover | Unique Games Conjecture | Unique Games Conjecture | independent set | independent set | fixed-parameter intractability | fixed-parameter intractability | parameter-preserving reduction | parameter-preserving reduction | W hierarchy | W hierarchy | clique-hardness | clique-hardness | 3SUM-hardness | 3SUM-hardness | exponential time hypothesis | exponential time hypothesis | counting problems | counting problems | solution uniqueness | solution uniqueness | game theory | game theory | Existential theory of the reals | Existential theory of the reals | undecidability | undecidability

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see http://ocw.mit.edu/terms/index.htm

Site sourced from

http://ocw.mit.edu/rss/all/mit-allavcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

24.244 Modal Logic (MIT) 24.244 Modal Logic (MIT)

Description

Modal logic is the logic of necessity and possibility, and by extension of analogously paired notions like validity and consistency, obligation and permission, the known and the not-ruled-out. This a first course in the area. A solid background in first-order logic is essential. Topics to be covered include (some or all of) the main systems of propositional modal logic, Kripkean "possible world" semantics, strict implication, contingent identity, intensional objects, counterpart theory, the logic of actuality, and deontic and / or epistemic logic. The emphasis will be more on technical methods and results than philosophical applications. Modal logic is the logic of necessity and possibility, and by extension of analogously paired notions like validity and consistency, obligation and permission, the known and the not-ruled-out. This a first course in the area. A solid background in first-order logic is essential. Topics to be covered include (some or all of) the main systems of propositional modal logic, Kripkean "possible world" semantics, strict implication, contingent identity, intensional objects, counterpart theory, the logic of actuality, and deontic and / or epistemic logic. The emphasis will be more on technical methods and results than philosophical applications.

Subjects

W. V. Quine's modal logic | W. V. Quine's modal logic | Lewis's S1 and S2 | Lewis's S1 and S2 | propositional modal logic | propositional modal logic | completeness | completeness | frames and models | frames and models | tense logic | tense logic | combining modality and tense | combining modality and tense | epistemic logic | epistemic logic | quantified modal logic | quantified modal logic

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see http://ocw.mit.edu/terms/index.htm

Site sourced from

http://ocw.mit.edu/rss/all/mit-allcourses-24.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

6.045J Automata, Computability, and Complexity (MIT)

Description

This course is offered to undergraduates and introduces basic mathematical models of computation and the finite representation of infinite objects. The course is slower paced than 6.840J/18.404J. Topics covered include: finite automata and regular languages, context-free languages, Turing machines, partial recursive functions, Church's Thesis, undecidability, reducibility and completeness, time complexity and NP-completeness, probabilistic computation, and interactive proof systems.

Subjects

automata | computability | complexity | mathematical models | computation | finite representation | infinite objects | finite automata | regular languages | context-free languages | Turing machines | partial recursive functions | Church's Thesis | undecidability | reducibility | completeness | time complexity | NP-completeness | probabilistic computation | interactive proof systems | 6.045 | 18.400

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allarchivedcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

6.045J Automata, Computability, and Complexity (MIT)

Description

This course introduces basic mathematical models of computation and the finite representation of infinite objects. Topics covered include: finite automata and regular languages, context-free languages, Turing machines, partial recursive functions, Church's Thesis, undecidability, reducibility and completeness, time complexity and NP-completeness, probabilistic computation, and interactive proof systems.

Subjects

automata | computability | complexity | mathematical models | computation | finite representation | infinite objects | finite automata | regular languages | context-free languages | Turing machines | partial recursive functions | Church's Thesis | undecidability | reducibility | completeness | time complexity | NP-completeness | probabilistic computation | interactive proof systems | 6.045 | 18.400

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allarchivedcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

18.404J Theory of Computation (MIT)

Description

This graduate level course is more extensive and theoretical treatment of the material in Computability, and Complexity (6.045J / 18.400J). Topics include Automata and Language Theory, Computability Theory, and Complexity Theory.

Subjects

Computability | computational complexity theory | Regular and context-free languages | Decidable and undecidable problems | reducibility | recursive function theory | Time and space measures on computation | completeness | hierarchy theorems | inherently complex problems | oracles | probabilistic computation | and interactive proof systems

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allportuguesecourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

18.404J Theory of Computation (MIT)

Description

This graduate level course is more extensive and theoretical treatment of the material in Computability, and Complexity (6.045J / 18.400J). Topics include Automata and Language Theory, Computability Theory, and Complexity Theory.

Subjects

Computability | computational complexity theory | Regular and context-free languages | Decidable and undecidable problems | reducibility | recursive function theory | Time and space measures on computation | completeness | hierarchy theorems | inherently complex problems | oracles | probabilistic computation | and interactive proof systems

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allspanishcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

Algorithms

Description

This course focuses on the fundamentals of computer algorithms, emphasizing methods useful in practice. This free course may be completed online at any time. See course site for detailed overview and learning outcomes. (Computer Science 303)

Subjects

computer science | computer | algorithms | programming | analysis | sorting | dynamic | graph theory | graph algorithms | greedy algorithms | np-completeness | Computer science | I100

License

Attribution 2.0 UK: England & Wales Attribution 2.0 UK: England & Wales http://creativecommons.org/licenses/by/2.0/uk/ http://creativecommons.org/licenses/by/2.0/uk/

Site sourced from

http://dspace.jorum.ac.uk/oai/request?verb=ListRecords&metadataPrefix=oai_dc

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

18.404J Theory of Computation (MIT)

Description

A more extensive and theoretical treatment of the material in 18.400J, Automata, Computability, and Complexity, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems.

Subjects

computability | computational complexity theory | Regular and context-free languages | Decidable and undecidable problems | reducibility | recursive function theory | Time and space measures on computation | completeness | hierarchy theorems | inherently complex problems | oracles | probabilistic computation | interactive proof systems | 18.404 | 6.840

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allarchivedcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

18.404J Theory of Computation (MIT)

Description

This graduate level course is more extensive and theoretical treatment of the material in Computability, and Complexity (6.045J / 18.400J). Topics include Automata and Language Theory, Computability Theory, and Complexity Theory.

Subjects

Computability | computational complexity theory | Regular and context-free languages | Decidable and undecidable problems | reducibility | recursive function theory | Time and space measures on computation | completeness | hierarchy theorems | inherently complex problems | oracles | probabilistic computation | and interactive proof systems

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

18.725 Algebraic Geometry (MIT)

Description

This course covers the fundamental notions and results about algebraic varieties over an algebraically closed field. It also analyzes the relations between complex algebraic varieties and complex analytic varieties.

Subjects

algebraic varieties over algebraically closed field | complex algebraic varieties | complex analytic varieties | curves and surfaces | irreducible components | projective space | topological diversion | sheaves | presheaves | algebraic geometry | fibers | morphisms | varieties | projective varieties | applications | dimension | krull dimension | completeness | complex topology | Chow's lemma | analytic spaces | curves

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

22.091 Nuclear Reactor Safety (MIT)

Description

Problems in nuclear engineering often involve applying knowledge from many disciplines simultaneously in achieving satisfactory solutions. The course will focus on understanding the complete nuclear reactor system including the balance of plant, support systems and resulting interdependencies affecting the overall safety of the plant and regulatory oversight. Both the Seabrook and Pilgrim nuclear plant simulators will be used as part of the educational experience to provide as realistic as possible understanding of nuclear power systems short of being at the reactor.

Subjects

nuclear | reactor | safety | dryout heat flux | preexisting hydrogen | blowdown gases | downward propagation limit | debris dispersal | direct containment heating | gas blowthrough | seal table room | subcompartment structures | compartmentalized geometries | overlying liquid layer | preexisting atmosphere | blowdown time | melt generator | detonation adiabatic | thermohydraulic codes | hydrodynamic fragmentation | vent clearing | combustion completeness | containment pressurization | melt retention | containment loads | melt ejection | containment geometry | hole ablation | Sandia National Laboratories | Heat Transfer Conf | Nuclear Regulatory Commission Report | Heat Mass Transfer | The Combustion Institute | Combustion Symposium International | New York | Santa Barbara | Argonne National Laboratory | Fluid Mech | Zion Probabilistic Safety Study | Los Angeles | Impact of Hydrogen | Topical Meeting | Water Reactor Safety | Water Trans | Academic Press All | American Society of Mechanical Engineers | Specialists Meeting | University of California | Brookhaven National Laboratory | Calvert Cliffs | Fourth Int | International Conference | New Trends.

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

24.244 Modal Logic (MIT)

Description

Modal logic is the logic of necessity and possibility, and by extension of analogously paired notions like validity and consistency, obligation and permission, the known and the not-ruled-out. This a first course in the area. A solid background in first-order logic is essential. Topics to be covered include (some or all of) the main systems of propositional modal logic, Kripkean "possible world" semantics, strict implication, contingent identity, intensional objects, counterpart theory, the logic of actuality, and deontic and / or epistemic logic. The emphasis will be more on technical methods and results than philosophical applications.

Subjects

W. V. Quine's modal logic | Lewis's S1 and S2 | propositional modal logic | completeness | frames and models | tense logic | combining modality and tense | epistemic logic | quantified modal logic

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (MIT)

Description

6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs is a class taking a practical approach to proving problems can't be solved efficiently (in polynomial time and assuming standard complexity-theoretic assumptions like P ≠ NP). The class focuses on reductions and techniques for proving problems are computationally hard for a variety of complexity classes. Along the way, the class will create many interesting gadgets, learn many hardness proof styles, explore the connection between games and computation, survey several important problems and complexity classes, and crush hopes and dreams (for fast optimal solutions).

Subjects

NP-completeness | 3SAT | 3-partition | Hamiltonicity | PSPACE | EXPTIME | EXPSPACE | games | puzzles | computation | Tetris | Nintendo | Super Mario Bros. | The Legend of Zelda | Metroid | mon | constraint logic | Sudoku | Nikoli | Chess | Go | Othello | board games | inapproximability | PCP theorem | OPT-preserving reduction | APX-hardness | vertex cover | Set-cover hardness | Group Steiner tree | k-dense subgraph | label cover | Unique Games Conjecture | independent set | fixed-parameter intractability | parameter-preserving reduction | W hierarchy | clique-hardness | 3SUM-hardness | exponential time hypothesis | counting problems | solution uniqueness | game theory | Existential theory of the reals | undecidability

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

6.080 Great Ideas in Theoretical Computer Science (MIT)

Description

This course provides a challenging introduction to some of the central ideas of theoretical computer science. It attempts to present a vision of "computer science beyond computers": that is, CS as a set of mathematical tools for understanding complex systems such as universes and minds. Beginning in antiquity—with Euclid's algorithm and other ancient examples of computational thinking—the course will progress rapidly through propositional logic, Turing machines and computability, finite automata, Gödel's theorems, efficient algorithms and reducibility, NP-completeness, the P versus NP problem, decision trees and other concrete computational models, the power of randomness, cryptography and one-way functions, computational theories of learning, interactive proofs, and q

Subjects

computer science | theoretical computer science | logic | turing machines | computability | finite automata | godel | complexity | polynomial time | efficient algorithms | reducibility | p and np | np completeness | private key cryptography | public key cryptography | pac learning | quantum computing | quantum algorithms

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata

24.242 Logic II (MIT)

Description

This course begins with an introduction to the theory of computability, then proceeds to a detailed study of its most illustrious result: Kurt Gdel's theorem that, for any system of true arithmetical statements we might propose as an axiomatic basis for proving truths of arithmetic, there will be some arithmetical statements that we can recognize as true even though they don't follow from the system of axioms. In my opinion, which is widely shared, this is the most important single result in the entire history of logic, important not only on its own right but for the many applications of the technique by which it's proved. We'll discuss some of these applications, among them: Church's theorem that there is no algorithm for deciding when a formula is valid in the predicate calculus;

Subjects

Logic | theory of computability | Kurt G?del | theorem | system | true | arithmetical | statements | axiomatic basis | proving | truths of arithmetic | history applications | technique | Church?s theorem | algorithm | formula | valid | predicate calculus | Tarski?s theorem | G?del?s second incompleteness theorem.

License

Content within individual OCW courses is (c) by the individual authors unless otherwise noted. MIT OpenCourseWare materials are licensed by the Massachusetts Institute of Technology under a Creative Commons License (Attribution-NonCommercial-ShareAlike). For further information see https://ocw.mit.edu/terms/index.htm

Site sourced from

https://ocw.mit.edu/rss/all/mit-allcourses.xml

Attribution

Click to get HTML | Click to get attribution | Click to get URL

All metadata

See all metadata