NP-complete

32 results back to index


pages: 236 words: 50,763

The Golden Ticket: P, NP, and the Search for the Impossible by Lance Fortnow

Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, Andrew Wiles, Claude Shannon: information theory, cloud computing, complexity theory, Donald Knuth, Erdős number, four colour theorem, Gerolamo Cardano, Isaac Newton, Johannes Kepler, John von Neumann, linear programming, new economy, NP-complete, Occam's razor, P = NP, Paul Erdős, Richard Feynman, Rubik’s Cube, smart grid, Stephen Hawking, traveling salesman, Turing machine, Turing test, Watson beat the top human players on Jeopardy!, William of Occam

Beyond Karp After Karp’s paper, an industry in computer science arose showing the NP-completeness of a large variety of search problems. Over the next several years, many professors and grad students took a number of known search problems (as well as some new ones) and showed them to be NP-complete. A classic 1979 book* lists over three hundred major NP-complete problems. NP-complete problems continually arise in computer science, physics, biology, economics, and many other areas that reach that pinnacle of hardness. A Google Scholar search on “NP-Complete” returns over 138,000 scientific articles from 1972 to 2011, nearly 10,000 in 2011 alone. We can’t list all of them here, but let me give you a flavor of some of them. Dominating Set Are there fifty people in Frenemy such that everyone else is friends with at least one of them? NP-complete. Partition into Triangles The dorm rooms of the Frenemy Institute can each hold three students.

Now a computer search will start to take significant time, and 100 × 100 games can defeat today’s fastest machines. Large Sudoku games are NP-complete. Think you are good at Sudoku? If you can reliably solve large puzzles, then you can solve satisfiability, traveling salesman problems, and thousands of other NP-complete problems. Sudoku is hardly the only NP-complete solitaire game. Consider the Minesweeper game built into Microsoft Windows. Figure 4-5. Minesweeper. Each number in a square tells how many mines are within one square (horizontally, vertically, or diagonally) from that square. Click on a square and you will reveal that number. Set a flag if you think there are bombs there. Click on a bomb and you lose the game. Determining whether one can win a large Minesweeper game is also NP-complete. Here are the remaining bombs in the above game. Figure 4-6.

Knuth got many write-in suggestions, some straightforward, like “intractable” and “obstinate,” and others a bit more tongue-in-cheek, like “hard-boiled” (in honor of Cook) and “hard-ass” (“hard as satisfiability”). The winning write-in vote was for “NP-complete,” which was proposed by several people at Bell Labs in New Jersey after considerable discussion among the researchers there. The word “complete” comes from mathematical logic, where a set of facts is complete if it can explain all the true statements in some logical system. Analogously, “NP-complete” means those problems in NP powerful enough that they can be used to solve any other problem in NP. Knuth was not entirely happy with this choice but was willing to live with it. He truly wanted a single English world that captured the intuitive meaning of hard search problems, a term for the masses. In a 1974 wrap-up of his survey, Knuth wrote “NP-complete actually smacks of being a little too technical for a mass audience, but it’s not so bad as to be unusable.”


Algorithms Unlocked by Thomas H. Cormen

bioinformatics, Donald Knuth, knapsack problem, NP-complete, optical character recognition, P = NP, Silicon Valley, sorting algorithm, traveling salesman

—is the question that has perplexed computer scientists for all these years. We often call it the “P D NP‹ problem.” The NP-complete problems are the “hardest” in NP. Informally, a problem is NP-complete if it satisfies two conditions: (1) it’s in NP and (2) if a polynomial-time algorithm exists for the problem, then there is a way to convert every problem in NP into this problem in such a way as to solve them all in polynomial time. If a polynomial-time algorithm exists for any NP-complete problem—that is, if any NP-complete problem is in P—then P D NP. Because NP-complete problems are the hardest in NP, if it turns out that any problem in NP is not polynomial-time solvable, then none of the NP-complete problems are. A problem is NP-hard if it satisfies the second condition for NP-completeness but may or may not be in NP. Here’s a handy list of the pertinent definitions: P: problems solvable in polynomial time, i.e., we can solve the problem in time polynomial in the size of the input to the problem.

To take the frustration to a whole new level, here’s the most amazing fact: if there were an algorithm that ran in O.nc / time for any of these problems, where c is a constant, then there would be an algorithm that ran in O.nc / time for all of these problems. We call these problems NP-complete. An algorithm that runs in time O.nc / on an input of size n, where c is a constant, is a polynomial-time algorithm, so called because nc with some coefficient would be the most significant term in the running time. We know of no polynomial-time algorithm for any NP-complete problem, but nobody has proven that it’s impossible to solve some NP-complete problem in polynomial time. And there’s even more frustration: many NP-complete problems are almost the same as problems that we know how to solve in polynomial time. Just a small tweak separates them. For example, recall from Chapter 6 that the Bellman-Ford algorithm finds shortest paths from a single source in a directed graph, even if the graph has negative-weight edges, in ‚.nm/ time, where the graph has n vertices and m edges.

But if we ask whether a connected, undirected graph has a hamiltonian cycle, that’s NP-complete. Notice that the question is not “what is the order of vertices on a hamiltonian cycle in this graph?” but just the more basic “yes or no: is it possible to construct a hamiltonian cycle on this graph?” NP-complete problems come up surprisingly often, which is why I’m including material on them in this book. If you are trying to find a polynomial-time algorithm for a problem that turns out to be NPcomplete, you are likely to be in for a big helping of disappointment. (But see the section on perspective, pages 208–211.) The concept of NP-complete problems has been around since the early 1970s, and people were trying to solve problems that turned out to be NP-complete (such as the traveling-salesman problem) well before then.


pages: 396 words: 117,149

The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World by Pedro Domingos

Albert Einstein, Amazon Mechanical Turk, Arthur Eddington, basic income, Bayesian statistics, Benoit Mandelbrot, bioinformatics, Black Swan, Brownian motion, cellular automata, Claude Shannon: information theory, combinatorial explosion, computer vision, constrained optimization, correlation does not imply causation, creative destruction, crowdsourcing, Danny Hillis, data is the new oil, double helix, Douglas Hofstadter, Erik Brynjolfsson, experimental subject, Filter Bubble, future of work, global village, Google Glasses, Gödel, Escher, Bach, information retrieval, job automation, John Markoff, John Snow's cholera map, John von Neumann, Joseph Schumpeter, Kevin Kelly, lone genius, mandelbrot fractal, Mark Zuckerberg, Moneyball by Michael Lewis explains big data, Narrative Science, Nate Silver, natural language processing, Netflix Prize, Network effects, NP-complete, off grid, P = NP, PageRank, pattern recognition, phenotype, planetary scale, pre–internet, random walk, Ray Kurzweil, recommendation engine, Richard Feynman, scientific worldview, Second Machine Age, self-driving car, Silicon Valley, social intelligence, speech recognition, Stanford marshmallow experiment, statistical model, Stephen Hawking, Steven Levy, Steven Pinker, superintelligent machines, the scientific method, The Signal and the Noise by Nate Silver, theory of mind, Thomas Bayes, transaction costs, Turing machine, Turing test, Vernor Vinge, Watson beat the top human players on Jeopardy!, white flight, zero-sum game

Because of NP-completeness, all it takes to answer it is to prove that one NP-complete problem is efficiently solvable (or not). NP is not the hardest class of problems in computer science, but it’s arguably the hardest “realistic” class: if you can’t even check a problem’s solution before the universe ends, what’s the point of trying to solve it? Humans are good at solving NP problems approximately, and conversely, problems that we find interesting (like Tetris) often have an “NP-ness” about them. One definition of artificial intelligence is that it consists of finding heuristic solutions to NP-complete problems. Often, we do this by reducing them to satisfiability, the canonical NP-complete problem: Can a given logical formula ever be true, or is it self-contradictory? If we invent a learner that can learn to solve satisfiability, it has a good claim to being the Master Algorithm.

Figuring out how proteins fold into their characteristic shapes; reconstructing the evolutionary history of a set of species from their DNA; proving theorems in propositional logic; detecting arbitrage opportunities in markets with transaction costs; inferring a three-dimensional shape from two-dimensional views; compressing data on a disk; forming a stable coalition in politics; modeling turbulence in sheared flows; finding the safest portfolio of investments with a given return, the shortest route to visit a set of cities, the best layout of components on a microchip, the best placement of sensors in an ecosystem, or the lowest energy state of a spin glass; scheduling flights, classes, and factory jobs; optimizing resource allocation, urban traffic flow, social welfare, and (most important) your Tetris score: these are all NP-complete problems, meaning that if you can efficiently solve one of them you can efficiently solve all problems in the class NP, including each other. Who would have guessed that all these problems, superficially so different, are really the same? But if they are, it makes sense that one algorithm could learn to solve all of them (or, more precisely, all efficiently solvable instances). P and NP are the two most important classes of problems in computer science. (The names are not very mnemonic, unfortunately.) A problem is in P if we can solve it efficiently, and it’s in NP if we can efficiently check its solution. The famous P = NP question is whether every efficiently checkable problem is also efficiently solvable. Because of NP-completeness, all it takes to answer it is to prove that one NP-complete problem is efficiently solvable (or not).

If there’s a limit to what Bayes can learn, we haven’t found it yet. The argument from computer science When I was a senior in college, I wasted a summer playing Tetris, a highly addictive video game where variously shaped pieces fall from above and which you try to pack as closely together as you can; the game is over when the pile of pieces reaches the top of the screen. Little did I know that this was my introduction to NP-completeness, the most important problem in theoretical computer science. Turns out that, far from an idle pursuit, mastering Tetris—really mastering it—is one of the most useful things you could ever do. If you can solve Tetris, you can solve thousands of the hardest and most important problems in science, technology, and management—all in one fell swoop. That’s because at heart they are all the same problem.


pages: 523 words: 143,139

Algorithms to Live By: The Computer Science of Human Decisions by Brian Christian, Tom Griffiths

4chan, Ada Lovelace, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Albert Einstein, algorithmic trading, anthropic principle, asset allocation, autonomous vehicles, Bayesian statistics, Berlin Wall, Bill Duvall, bitcoin, Community Supported Agriculture, complexity theory, constrained optimization, cosmological principle, cryptocurrency, Danny Hillis, David Heinemeier Hansson, delayed gratification, dematerialisation, diversification, Donald Knuth, double helix, Elon Musk, fault tolerance, Fellow of the Royal Society, Firefox, first-price auction, Flash crash, Frederick Winslow Taylor, George Akerlof, global supply chain, Google Chrome, Henri Poincaré, information retrieval, Internet Archive, Jeff Bezos, Johannes Kepler, John Nash: game theory, John von Neumann, Kickstarter, knapsack problem, Lao Tzu, Leonard Kleinrock, linear programming, martingale, Nash equilibrium, natural language processing, NP-complete, P = NP, packet switching, Pierre-Simon Laplace, prediction markets, race to the bottom, RAND corporation, RFC: Request For Comment, Robert X Cringely, Sam Altman, sealed-bid auction, second-price auction, self-driving car, Silicon Valley, Skype, sorting algorithm, spectrum auction, Stanford marshmallow experiment, Steve Jobs, stochastic process, Thomas Bayes, Thomas Malthus, traveling salesman, Turing machine, urban planning, Vickrey auction, Vilfredo Pareto, Walter Mischel, Y Combinator, zero-sum game

The intractable scheduling problems that Eugene Lawler encountered in chapter 5 fall into this category. An NP-hard problem that is itself in NP is known as “NP-complete.” See Karp, “Reducibility Among Combinatorial Problems,” for the classic result showing that a version of the traveling salesman problem is NP-complete, and Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible, for an accessible introduction to P and NP. most computer scientists believe that there aren’t any: In a 2002 survey of one hundred leading theoretical computer scientists, sixty-one thought P ≠ NP and only nine thought P = NP (Gasarch, “The P =? NP Poll”). While proving P = NP could be done by exhibiting a polynomial-time algorithm for an NP-complete problem, proving P ≠ NP requires making complex arguments about the limits of polynomial-time algorithms, and there wasn’t much agreement among the people surveyed about exactly what kind of mathematics will be needed to solve this problem.

What’s more, many other optimization problems: This includes versions of vertex cover and set cover—two problems identified as belonging to NP in Karp, “Reducibility Among Combinatorial Problems,” where twenty-one problems were famously shown to be in this set. By the end of the 1970s, computer scientists had identified some three hundred NP-complete problems (Garey and Johnson, Computers and Intractability), and the list has grown significantly since then. These include some problems that are very familiar to humans. In 2003, Sudoku was shown to be NP-complete (Yato and Seta, “Complexity and Completeness”), as was maximizing the number of cleared rows in Tetris, even with perfect knowledge of future pieces (Demaine, Hohenberger, and Liben-Nowell, “Tetris Is Hard, Even to Approximate”). In 2012, determining whether there exists a path to the end of the level in platformer games like Super Mario Brothers was officially added to the list (Aloupis, Demaine, and Guo, “Classic Nintendo Games are (NP-) Hard”).

(With n = 3, this involves figuring out the path a knife would have to travel to cut three sets of points in half; if those sets of points correspond to two pieces of bread and a piece of ham, the result is a perfectly bisected sandwich.) Finding Nash equilibria is actually PPAD-complete, meaning that if there were an efficient algorithm for solving it then all other problems in the class could also be solved efficiently (including making the world’s neatest sandwiches). But being PPAD-complete is not quite so bad as being NP-complete. P, the class of efficiently solvable problems, could be equal to PPAD without being equal to NP. As of this writing the jury is still out: it’s theoretically possible that somebody could devise an efficient algorithm for finding Nash equilibria, but most experts aren’t holding their breath. “much of its credibility as a prediction”: Christos Papadimitriou, “The Complexity of Finding Nash Equilibria,” in Nisan et al., Algorithmic Game Theory.


Applied Cryptography: Protocols, Algorithms, and Source Code in C by Bruce Schneier

active measures, cellular automata, Claude Shannon: information theory, complexity theory, dark matter, Donald Davies, Donald Knuth, dumpster diving, Exxon Valdez, fault tolerance, finite state, invisible hand, John von Neumann, knapsack problem, MITM: man-in-the-middle, NP-complete, P = NP, packet switching, RAND corporation, RFC: Request For Comment, software patent, telemarketer, traveling salesman, Turing machine, web of trust, Zimmermann PGP

If any DNA survives this screening, it is examined to find the sequence of roads that it represents: This is the solution to the directed Hamiltonian path problem. By definition, an instance of any NP-complete problem can be transformed, in polynomial time, into an instance of any other NP-complete problem, and therefore into an instance of the directed Hamiltonian path problem. Since the 1970s, cryptologists have been trying to use NP-complete problems for public-key cryptography. While the instance that Adleman solved was very modest (seven cities on his map, a problem that can be solved by inspection in a few minutes), the technique is in its infancy and has no forbidding obstacles keeping it from being extended to larger problems. Thus, arguments about the security of cryptographic protocols based on NP-complete problems, arguments that heretofore have begun, “Suppose an adversary has a million processors, each of which can perform a million tests each second,” may soon have to be replaced with, “Suppose an adversary has a thousand fermentation vats, each 20,000 liters in capacity.”

Steven Cook [365] proved that the Satisfiability problem (given a propositional Boolean formula, is there a way to assign truth values to the variables that makes the formula true?) is NP-complete . This means that, if Satisfiability is solvable in polynomial time, then P = NP. Conversely, if any problem in NP can be proven not to have a deterministic polynomial-time algorithm, the proof will show that Satisfiability does not have a deterministic polynomial-time algorithm either. No problem is harder than Satisfiability in NP. Since Cook’s seminal paper was published, a huge number of problems have been shown to be equivalent to Satisfiability; hundreds are listed in [600], and some examples follow. By equivalent, I mean that these problems are also NP-complete; they are in NP and also as hard as any problem in NP . If their solvability in deterministic polynomial time were resolved, the P versus NP question would be solved.

To access the contents, click the chapter and section titles. Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C (cloth) Go! Keyword Brief Full Advanced Search Search Tips (Publisher: John Wiley & Sons, Inc.) Author(s): Bruce Schneier ISBN: 0471128457 Publication Date: 01/01/96 Search this book: Go! Previous Table of Contents Next ----------- NP-Complete Problems Michael Garey and David Johnson compiled a list of over 300 NP-complete problems [600]. Here are just a few of them: — Traveling Salesman Problem. A traveling salesman has to visit n different cities using only one tank of gas (there is a maximum distance he can travel). Is there a route that allows him to visit each city exactly once on that single tank of gas? (This is a generalization of the Hamiltonian Cycle problem—see Section 5.1.) — Three-Way Marriage Problem.


pages: 71 words: 14,237

21 Recipes for Mining Twitter by Matthew A. Russell

en.wikipedia.org, Google Earth, natural language processing, NP-complete, social web, web application

Example 1-29 illustrates an approach for taking a NetworkX graph and discovering the cliques in it. Example 1-29. Analyzing friendship cliques (see http://github.com/ptwobrussell/Recipes-for-Mining -Twitter/blob/master/recipe__clique_analysis.py) # -*- coding: utf-8 -*import sys import json import networkx as nx 50 | The Recipes G = sys.argv[1] g = nx.read_gpickle(G) # # # # Finding cliques is a hard problem, so this could take a while for large graphs. See http://en.wikipedia.org/wiki/NP-complete and http://en.wikipedia.org/wiki/Clique_problem cliques = [c for c in nx.find_cliques(g)] num_cliques = len(cliques) clique_sizes = [len(c) for c in cliques] max_clique_size = max(clique_sizes) avg_clique_size = sum(clique_sizes) / num_cliques max_cliques = [c for c in cliques if len(c) == max_clique_size] num_max_cliques = len(max_cliques) max_clique_sets = [set(c) for c in max_cliques] people_in_every_max_clique = list(reduce(lambda x, y: x.intersection(y), max_clique_sets)) print print print print print print print print print print 'Num 'Avg 'Max 'Num cliques:', num_cliques clique size:', avg_clique_size clique size:', max_clique_size max cliques:', num_max_cliques 'People in all max cliques:' json.dumps(people_in_every_max_clique, indent=4) 'Max cliques:' json.dumps(max_cliques, indent=4) For purposes of illustration, Mining the Social Web (O’Reilly) included an analysis conducted in mid-2010 that determined the following statistics for Tim O’Reilly’s ~700 friendships: Num Avg Max Num Num cliques: 762573 clique size: 14 clique size: 26 max cliques: 6 people in every max clique: 20 Some of the more interesting insight from the analysis was that there are six different cliques of size 26 in Tim O’Reilly’s friendships, which means that those six variations of 26 people all “know” one another to the point that they were at least interested in receiving each other’s status updates in their tweet stream.

As an example of practical application, if you wanted to get Tim’s attention at a conference or Maker event, but can’t seem to track him down, you might start looking for one of 1.18 Analyzing Friendship Cliques | 51 these other people since there’s more than a reasonable likelihood that they’re closely connected with him. As a more technical aside, be advised that finding cliques is a hard problem in both a figurative sense, but also in the computational sense that it’s a problem that belongs to a class of problems that are known as NP-Complete. In layman’s terms, being NPComplete means that the combinatorics of the problem, whether it be finding cliques or otherwise, grow explosively as the size of the input for the problem grows. Practically speaking, this means that for a very large graph, you either need to wait a very long time to get an exact answer to the problem of finding cliques, or you need to be willing to settle for an approximate solution.


pages: 391 words: 71,600

Hit Refresh: The Quest to Rediscover Microsoft's Soul and Imagine a Better Future for Everyone by Satya Nadella, Greg Shaw, Jill Tracie Nichols

"Robert Solow", 3D printing, Amazon Web Services, anti-globalists, artificial general intelligence, augmented reality, autonomous vehicles, basic income, Bretton Woods, business process, cashless society, charter city, cloud computing, complexity theory, computer age, computer vision, corporate social responsibility, crowdsourcing, Deng Xiaoping, Donald Trump, Douglas Engelbart, Edward Snowden, Elon Musk, en.wikipedia.org, equal pay for equal work, everywhere but in the productivity statistics, fault tolerance, Gini coefficient, global supply chain, Google Glasses, Grace Hopper, industrial robot, Internet of things, Jeff Bezos, job automation, John Markoff, John von Neumann, knowledge worker, Mars Rover, Minecraft, Mother of all demos, NP-complete, Oculus Rift, pattern recognition, place-making, Richard Feynman, Robert Gordon, Ronald Reagan, Second Machine Age, self-driving car, side project, Silicon Valley, Skype, Snapchat, special economic zone, speech recognition, Stephen Hawking, Steve Ballmer, Steve Jobs, telepresence, telerobotics, The Rise and Fall of American Growth, Tim Cook: Apple, trade liberalization, two-sided market, universal basic income, Wall-E, Watson beat the top human players on Jeopardy!, young professional, zero-sum game

Graph coloring is part of computational complexity theory in which you must assign labels, traditionally called colors, to elements of a graph within certain constraints. Think of it this way: Imagine coloring the U.S. map so that no state sharing a common border receives the same color. What is the minimal number of colors you would need to accomplish this task? My master’s thesis was about developing the best heuristics to accomplish complex graph coloring in nondeterministic polynomial time, or NP-complete. In other words, how can I solve a problem that has limitless possibilities in a way that is fast and good but not always optimal? Do we solve this as best we can right now, or work forever for the best solution? Theoretical computer science really grabbed me because it showed the limits to what today’s computers can do. It led me to become fascinated by mathematicians and computer scientists John Von Neumann and Alan Turing, and by quantum computing, which I will write about later as we look ahead to artificial intelligence and machine learning.

Anu and I had decided to marry when I made a trip back to India just before joining Microsoft. I had known Anu all of my life. Her dad and my father had joined the IAS together and we were family friends. In fact, Anu’s dad and I shared a passion for talking endlessly about cricket, something we continue to this day. He had played for his school and college, captaining both teams. When exactly I fell in love with Anu is what computer scientists would call an NP complete question. I can come up with many times and places but there is no one answer. In other words, it’s complex. Our families were close. Our social circles were the same. As kids we had played together. We overlapped in school and college. Our beloved family dog came from Anu’s family dog’s litter. But once I moved to the United States, I lost touch with her. When I went back to India for a visit, we saw each other again.

See also smartphones; and specific products mobility, 42, 43, 54, 58, 70, 73, 88, 108, 216, 225 Mojang, 106–8 Moore, Gordon, 161 Moore’s Law, 140, 161 motion-sensing, 145 Motorola, 72 Mount Rainier, 19 mouse, 142 movable type, 152 Mulally, Alan, 64 multiculturalism, 19 multinational corporations, role of, 12, 235–39 Mundie, Craig, 30, 163 Musk, Elon, 203 Muslims, 19 Myerson, Terry, 3, 82, 105, 109 Myhrvold, Nathan, 30 Nadella, Anu, 7–8, 14, 27, 30–33, 41, 86, 92–93, 114 Nadella, father, 16–18, 20–21, 36, 56 Nadella, mother, 16–18, 20, 22, 86, 114, 181 nano-machines, 228 Nanyuki, Kenya, 99 Napoleonic Wars, 188 Narayen, Shantanu, 20, 136 National Aeronautics and Space Administration (NASA), 144, 146 National Football League (NFL), 10–11 National ICT for Development Policy (Malawi), 216 national security, 174–75, 228 National Security Agency (NSA), 172, 174–75, 181 Native Americans, 156 natural language, 151 Nehru, Jawaharlal, 16 Nepal, 44 Netflix, 30, 126 Netherland (O’Neill), 18 .Net, 58 networking, 45, 49, 213 Neuborne, Burt, 190 New Yorker, 233 New York Times, 24, 80, 176, 195, 209 New Zealand, 78 Nichols, Jill Tracie, 66–67, 95 Nietzsche, Friedrich, 79, 147 Nilekani, Nandan, 222 Nokia, 64, 71–73, 106, 133 nondeterministic polynomial time (NP-complete), 25 North, Douglass, 184 North Dakota, 47 North Korea, 169–70 Novell, 26 Numoto, Takeshi, 59 Obama, Barack, 3, 81, 175–76, 211–12, 214 Obama, Michelle, 211 Oculus Rift, 125, 144 Office, 2, 47, 53–54, 59, 68, 73, 81, 85, 123–25, 137, 203 Office 365, 44–45, 61, 62, 85, 123–25, 152, 233 OneDrive, 121 O’Neill, Joseph, 18 One Microsoft, 102, 108 OneNote, 103, 121 OneWeek growth hack, 103–5 online services, 46–47, 51 open-source, 62, 102 opportunity, 79, 238 Oracle, 3, 26, 81 Orlando nightclub massacre, 117 Osmania University, 36 Outlook, 104, 121 Ozzie, Ray, 46, 52–53 Parthasarathy, Sanjay, 115–16 Partnership on AI, 200 partnerships, 76, 78, 120–38 passion, 92, 94, 100, 103, 242 Pataudi, Tiger, 37 pattern recognition, 54, 150, 152, 201 pay equity, 113–14 PC Revolution, 1, 28, 45, 71, 89, 108, 139, 213 decline of, 66, 70, 79 perception, 150, 152, 154 pharmacies, 218, 223 Phillips, James, 58 PhotoShop, 136 photosynthesis, 160 Pichai, Sundar, 131 pivot tables, 143 Pixar, 13 platform shifts, 76, 142 point-of-sales devices, 128–29 Poland, 223 policymaking, 82, 182, 189–92, 214, 223–28, 235 poverty, 99, 237 Power BI, 121 Powerpoint, 121 Practo, 222 predictive power, 42, 88 Predix platform, 127 printing press, 152 PRISM, 172–73 Prism Skylabs, 153 privacy, 170, 172–80, 186–91, 193–94, 202, 205, 224, 230, 238 probabilistic decision making, 54 productivity, 76, 79, 88, 124, 126, 226–28 product launches, 98–100 public health, 237 public-private partnerships, 225–26 public sector, 222, 228, 237–38 Qatar, 225 Qi Lu, Dr., 51–52 Qualcomm, 3, 80, 131–32 quantum computing, 11, 110, 140–42, 159–67, 209, 212, 239 qubits, 160–61, 164, 166–67 logical, 167 topological, 162, 166 radiation monitoring, 44 railroads, 215 Ramakrishnan, Raghu, 58–59 Ranji Trophy, 38, 40 Rashid, Rick, 30 Reagan, Ronald, 181 Real Madrid, 71 Red Dog, 52–53, 58 Red Hat, 125 Reform Government Surveillance alliance, 174 refugees, 218 regulatory systems, 130, 186–90, 215, 227–28 relational algebra, 26 respect, 135, 202 retailers, 128–29, 153 rice production, 44 Rilke, Rainer Maria, 12 Rise and Fall of American Growth (Gordon), 234 risk-taking, 111, 220 River Runs Through It, A (Maclean), 56 Roberts, John, 185–86 robotics, 13, 145, 149–50, 202–4, 208–9, 228, 231–32, 239 Rochester Institute of Technology, 146 Rocky movies, 44–45 Rogan, Seth, 169 Rolling Stones, 98 Rolls-Royce, 127 Romer, Paul, 229 root-cause analysis, 61 RSA-2048 encryption, 162 Rubinstein, Ira, 32–33 run times, 203 rural areas, connecting, 99 Russia, 172 Russinovich, Mark, 58 Rwanda Vision 2020, 216 safety, 153, 172, 176–80, 182, 185, 188, 194, 228 sales conference, 86–95, 100, 118 Salesforce, 121 Samsung, 132–34 San Bernardino attacks, 177, 179, 189 Sanders, Bernie, 230 Sanskrit, 16, 181 Saudi Arabia, 225 scale, 50, 161 Schiller, Phil, 124 Schmidt, Eric, 26 Scott, Kevin, 82 search and seizure, 185–86 Search Checkpoint #1, 51 search engines, 46–52.


pages: 416 words: 112,268

Human Compatible: Artificial Intelligence and the Problem of Control by Stuart Russell

3D printing, Ada Lovelace, AI winter, Alan Turing: On Computable Numbers, with an Application to the Entscheidungsproblem, Alfred Russel Wallace, Andrew Wiles, artificial general intelligence, Asilomar, Asilomar Conference on Recombinant DNA, augmented reality, autonomous vehicles, basic income, blockchain, brain emulation, Cass Sunstein, Claude Shannon: information theory, complexity theory, computer vision, connected car, crowdsourcing, Daniel Kahneman / Amos Tversky, delayed gratification, Elon Musk, en.wikipedia.org, Erik Brynjolfsson, Ernest Rutherford, Flash crash, full employment, future of work, Gerolamo Cardano, ImageNet competition, Intergovernmental Panel on Climate Change (IPCC), Internet of things, invention of the wheel, job automation, John Maynard Keynes: Economic Possibilities for our Grandchildren, John Maynard Keynes: technological unemployment, John Nash: game theory, John von Neumann, Kenneth Arrow, Kevin Kelly, Law of Accelerating Returns, Mark Zuckerberg, Nash equilibrium, Norbert Wiener, NP-complete, openstreetmap, P = NP, Pareto efficiency, Paul Samuelson, Pierre-Simon Laplace, positional goods, probability theory / Blaise Pascal / Pierre de Fermat, profit maximization, RAND corporation, random walk, Ray Kurzweil, recommendation engine, RFID, Richard Thaler, ride hailing / ride sharing, Robert Shiller, Robert Shiller, Rodney Brooks, Second Machine Age, self-driving car, Shoshana Zuboff, Silicon Valley, smart cities, smart contracts, social intelligence, speech recognition, Stephen Hawking, Steven Pinker, superintelligent machines, Thales of Miletus, The Future of Employment, Thomas Bayes, Thorstein Veblen, transport as a service, Turing machine, Turing test, universal basic income, uranium enrichment, Von Neumann architecture, Wall-E, Watson beat the top human players on Jeopardy!, web application, zero-sum game

The first algorithm for theorem-proving in first-order logic worked by reducing first-order sentences to (very large numbers of) propositional sentences: Martin Davis and Hilary Putnam, “A computing procedure for quantification theory,” Journal of the ACM 7 (1960): 201–15. 3. An improved algorithm for propositional inference: Martin Davis, George Logemann, and Donald Loveland, “A machine program for theorem-proving,” Communications of the ACM 5 (1962): 394–97. 4. The satisfiability problem—deciding whether a collection of sentences is true in some world—is NP-complete. The reasoning problem—deciding whether a sentence follows from the known sentences—is co-NP-complete, a class that is thought to be harder than NP-complete problems. 5. There are two exceptions to this rule: no repetition (a stone may not be played that returns the board to a situation that existed previously) and no suicide (a stone may not be placed such that it would immediately be captured—for example, if it is already surrounded). 6. The work that introduced first-order logic as we understand it today (Begriffsschrift means “concept writing”): Gottlob Frege, Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens (Halle, 1879).

Suppose that LoopChecker exists. Now write a program Q that calls LoopChecker as a subroutine, with Q itself and X as inputs, and then does the opposite of what LoopChecker(Q,X) predicts. So, if LoopChecker says that Q halts, Q doesn’t halt, and vice versa. Thus, the assumption that LoopChecker exists leads to a contradiction, so LoopChecker cannot exist. 40. I say “appear” because, as yet, the claim that the class of NP-complete problems requires superpolynomial time (usually referred to as P ≠ NP) is still an unproven conjecture. After almost fifty years of research, however, nearly all mathematicians and computer scientists are convinced the claim is true. 41. Lovelace’s writings on computation appear mainly in her notes attached to her translation of an Italian engineer’s commentary on Babbage’s engine: L. F. Menabrea, “Sketch of the Analytical Engine invented by Charles Babbage,” trans.


Hands-On Machine Learning With Scikit-Learn, Keras, and TensorFlow: Concepts, Tools, and Techniques to Build Intelligent Systems by Aurelien Geron

Amazon Mechanical Turk, Bayesian statistics, centre right, combinatorial explosion, constrained optimization, correlation coefficient, crowdsourcing, en.wikipedia.org, iterative process, Netflix Prize, NP-complete, optical character recognition, P = NP, p-value, pattern recognition, performance metric, recommendation engine, self-driving car, SpamAssassin, speech recognition, statistical model

Solutions to these exercises are available in Appendix A. 1 Graphviz is an open source graph visualization software package, available at http://www.graphviz.org/. 2 P is the set of problems that can be solved in polynomial time. NP is the set of problems whose solutions can be verified in polynomial time. An NP-Hard problem is a problem to which any NP problem can be reduced in polynomial time. An NP-Complete problem is both NP and NP-Hard. A major open mathematical question is whether or not P = NP. If P ≠ NP (which seems likely), then no polynomial algorithm will ever be found for any NP-Complete problem (except perhaps on a quantum computer). 3 log2 is the binary logarithm. It is equal to log2(m) = log(m) / log(2). 4 A reduction of entropy is often called an information gain. 5 See Sebastian Raschka’s interesting analysis for more details. 6 It randomly selects the set of features to evaluate at each node.

Warning As you can see, the CART algorithm is a greedy algorithm: it greedily searches for an optimum split at the top level, then repeats the process at each level. It does not check whether or not the split will lead to the lowest possible impurity several levels down. A greedy algorithm often produces a reasonably good solution, but it is not guaranteed to be the optimal solution. Unfortunately, finding the optimal tree is known to be an NP-Complete problem:2 it requires O(exp(m)) time, making the problem intractable even for fairly small training sets. This is why we must settle for a “reasonably good” solution. Computational Complexity Making predictions requires traversing the Decision Tree from the root to a leaf. Decision Trees are generally approximately balanced, so traversing the Decision Tree requires going through roughly O(log2(m)) nodes.3 Since each node only requires checking the value of one feature, the overall prediction complexity is just O(log2(m)), independent of the number of features.


Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age by Steven Levy

Albert Einstein, Claude Shannon: information theory, cognitive dissonance, computer age, Donald Knuth, Eratosthenes, Extropian, invention of the telegraph, John Markoff, Kevin Kelly, knapsack problem, Marc Andreessen, Mitch Kapor, MITM: man-in-the-middle, Network effects, new economy, NP-complete, Ronald Reagan, Saturday Night Live, Silicon Valley, Simon Singh, Stephen Hawking, Steven Levy, Watson beat the top human players on Jeopardy!, web of trust, Whole Earth Catalog, zero-sum game, Zimmermann PGP, éminence grise

Knuth reminded them of an interesting mathematical phenomenon: while it is child’s play to multiply a pair of prime numbers, reversing the process—a task known as factoring—is an assignment that could confound the devil himself. Could this phenomenon be the basis for a devilishly challenging one-way function? Though Diffie and Hellman did not choose to pursue this idea, others would. Another alternative involved computational complexity, and Diffie pored over a book on the subject, particularly a chapter on what was known as NP-complete functions. The class of NP-complete problems, Diffie later wrote, are “problems thought not to be solvable in polynomial time on any deterministic computer.” This meant that they were so hard that you could set your Macintosh, or even your Cray supercomputer (if you were the NSA), to work on the problem and when you checked the results a few trillion years later, you wouldn’t even be in the general neighborhood of solving it.

It would be exhilarating to work with the two people in the world who best understood the problem. “I was basically isolated until I met Whit and Marty,” he says. “I was ready to keep banging away until I got some response, but there was no one else who was interested in pursuing this.” Merkle arrived at Stanford convinced that his most promising idea revolved around a scheme built around finding trapdoor one-way functions involving the NP-complete problem. The system was built around a mathematical problem known as knapsacks. To understand his scheme, picture, naturally, a knapsack. “The idea is to put things into this knapsack, to exactly fill it to the brim without going either over or under,” he says. Diffie would later describe the problem as that of a shipping clerk faced with a collection of packages of various sizes and shapes who had to find the absolute best way to stuff the packages in the mailbag.

., ref-1, ref-2, ref-3 Mosaic, ref-1 “Multiuser Cryptographic Techniques” (Diffie and Hellman), ref-1, ref-2, ref-3 Murray, Patty, ref-1 Myhrvold, Nathan, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Mykotronx, ref-1, ref-2, ref-3 National Bureau of Standards (NBS), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 National Institute of Standards and Technology (NIST), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 National Research Council (NRC), ref-1, ref-2 National Science Foundation (NSF), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 National Security Access Field (NSAF), ref-1 National Security Agency (NSA), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20, ref-21, ref-22, ref-23, ref-24, ref-25, ref-26, ref-27, ref-28, ref-29, ref-30, ref-31, ref-32, ref-33 Clipper and, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 DES and, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9 Diffie and, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 dual roles of, ref-1 GCHQ and, ref-1, ref-2 Kahn and, ref-1, ref-2 Lotus Notes and, ref-1, ref-2, ref-3, ref-4 NRC report and, ref-1 NSAF and, ref-1 Project Overtake of, ref-1 security failures at, ref-1 Snuffle and, ref-1 National Security Decision Directive, ref-1 Nelson, Mike, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Netscape, ref-1, ref-2, ref-3 Neukom, Bill, ref-1 “New Directions in Cryptography” (Diffie and Hellman), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 New York Times, ref-1, ref-2 Nicolai, Carl, ref-1, ref-2 nonrepudiation feature, ref-1 nonsecret encryption, ref-1 Notes, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8 NP-complete functions, ref-1, ref-2 O’Brien, Bart, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Odom, William E., ref-1 Omura, Jim, ref-1, ref-2 one-time pads, ref-1, ref-2, ref-3 one-way functions, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 factoring, ref-1, ref-2, ref-3 knapsacks, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 trapdoor, ref-1, ref-2, ref-3, ref-4 Ozzie, Ray, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 paranoia levels, ref-1 Parker, Donn, ref-1, ref-2 passwords, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Pasta, John R., ref-1 Patel, Marilyn, ref-1 patents, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20, ref-21, ref-22 Patterson, Nick, ref-1, ref-2, ref-3, ref-4 Penet, ref-1, ref-2, ref-3, ref-4, ref-5 Phasorphone, ref-1 Podesta, John, ref-1, ref-2 Poe, Edgar Allan, ref-1, ref-2, ref-3 pornography, ref-1 Press, Frank, ref-1 Pretty Good Privacy (PGP), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12 breaking of, ref-1, ref-2 Prime, Geoffrey, ref-1 prime numbers, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Project C43, ref-1, ref-2 Project Overtake, ref-1 public key cryptography, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20, ref-21, ref-22, ref-23, ref-24, ref-25, ref-26 certification of, ref-1 escrow and, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 nonsecret encryption and, ref-1 Secure Sockets Layer, ref-1, ref-2, ref-3 security failures and, ref-1 Public Key Partners (PKP), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Puzzle Palace, The (Bamford), ref-1, ref-2 quantum computers, ref-1 Random Number Generator (RNG), ref-1 Ray, Charles, ref-1 RC-2, ref-1, ref-2, ref-3 RC-4, ref-1, ref-2, ref-3, ref-4 Reagan, Ronald, ref-1, ref-2 Reeds, Jim, ref-1 remailers (anonymous servers), ref-1, ref-2, ref-3, ref-4, ref-5 Penet, ref-1, ref-2, ref-3, ref-4, ref-5 Richardson, Elliot, ref-1 Ritner, Peter, ref-1, ref-2 Rivest, Ron, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20 Rizzo, Paul, ref-1 Roberts, Larry, ref-1 Robinson, William B., ref-1, ref-2 Rohrbacher, Dana, ref-1 Rosenblum, Howard, ref-1, ref-2 Rotenberg, Marc, ref-1, ref-2 RSA, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17, ref-18, ref-19, ref-20, ref-21, ref-22, ref-23, ref-24, ref-25, ref-26, ref-27, ref-28, ref-29, ref-30, ref-31 Netscape and, ref-1 patents for, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 personal computers and, ref-1, ref-2 RSA Data Security, Inc., ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16 conference of, ref-1, ref-2, ref-3, ref-4 Sacco, Luigi, ref-1 Safire, William, ref-1 S-boxes (substitution boxes), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Schiller, Jeff, ref-1 Schneier, Bruce, ref-1, ref-2, ref-3 Schnorr, Claus, ref-1, ref-2 Schroeppel, Richard, ref-1, ref-2, ref-3, ref-4 Schwartz, John J., ref-1 Science, ref-1, ref-2, ref-3, ref-4 Scientific American, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8 Scientologists, ref-1, ref-2, ref-3 search warrants, ref-1, ref-2, ref-3, ref-4 secret sharing, ref-1 Secure Sockets Layer (SSL), ref-1, ref-2, ref-3 Security and Freedom through Encryption (SAFE) bill, ref-1, ref-2, ref-3 Security Dynamics, ref-1 Senate Bill ref-1, ref-2, ref-3, ref-4 servers, ref-1, ref-2 anonymous, see remailers Sessions, William, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Shamir, Adi, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13, ref-14, ref-15, ref-16, ref-17 Shannon, Claude, ref-1, ref-2, ref-3, ref-4, ref-5 shareware, ref-1, ref-2 signals intelligence, ref-1 signatures, digital, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11, ref-12, ref-13 blind, ref-1, ref-2 DSA, ref-1, ref-2, ref-3 Silver, Roland, ref-1, ref-2, ref-3, ref-4 Simmons, Gus, ref-1 Simons, Jim, ref-1, ref-2 Skipjack, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 Snefru, ref-1 Snow, Brian, ref-1 Snuffle, ref-1 stream ciphers, ref-1 Studeman, William O., ref-1, ref-2 substitution boxes (S-boxes), ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 SWIFT, ref-1 T Attack (differential cryptanalysis), ref-1, ref-2, ref-3 telephones: cellular, ref-1 security devices for, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 Tempest technology, ref-1 Tenet, George, ref-1 Tessera, ref-1 threshold scheme, ref-1 Time, ref-1 time-sharing, ref-1, ref-2 toll payments, ref-1 trapdoors, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9 knapsacks, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 one-way function, ref-1, ref-2, ref-3, ref-4 Senate bill and, ref-1, ref-2, ref-3 Tritter, Alan, ref-1, ref-2, ref-3, ref-4 Tuchman, Walter, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10 univectors, ref-1, ref-2 Usenet, ref-1, ref-2 vector space, ref-1 VeriSign, ref-1 Very Large Scale Integration (VLSI), ref-1 ViaCrypt, ref-1 virtual private networks, ref-1 Wagner, Dave, ref-1 Walker, Steve, ref-1 Wall Street Journal, ref-1, ref-2 Warren, Jim, ref-1, ref-2 Washington Post, ref-1 web of trust, ref-1 Weingarten, Fred, ref-1 Weldon, Curt, ref-1 Williamson, Malcolm, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6 Windows, ref-1 wiretapping, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7 Wise, William, ref-1 World Wide Web, ref-1, ref-2 browsers for, ref-1, ref-2, ref-3 Wormser, Dave, ref-1 Wylie, Shawn, ref-1 Xerox Corporation, ref-1, ref-2 xor operations, ref-1 Zero Knowledge, ref-1 zero-knowledge proofs of identity, ref-1 Zimmermann, Kacie, ref-1 Zimmermann, Phil, ref-1, ref-2, ref-3, ref-4, ref-5, ref-6, ref-7, ref-8, ref-9, ref-10, ref-11 contents acknowledgments preface the loner the standard public key prime time selling crypto patents and keys crypto anarchy the clipper chip slouching toward crypto epilogue: the open secret notes bibliography glossary index VIKING Published by the Penguin Group Penguin Putnam Inc., 375 Hudson Street, New York, New York 10014, U.S.A.


pages: 1,331 words: 163,200

Hands-On Machine Learning With Scikit-Learn and TensorFlow: Concepts, Tools, and Techniques to Build Intelligent Systems by Aurélien Géron

Amazon Mechanical Turk, Anton Chekhov, combinatorial explosion, computer vision, constrained optimization, correlation coefficient, crowdsourcing, don't repeat yourself, Elon Musk, en.wikipedia.org, friendly AI, ImageNet competition, information retrieval, iterative process, John von Neumann, Kickstarter, natural language processing, Netflix Prize, NP-complete, optical character recognition, P = NP, p-value, pattern recognition, pull request, recommendation engine, self-driving car, sentiment analysis, SpamAssassin, speech recognition, stochastic process

Solutions to these exercises are available in Appendix A. 1 Graphviz is an open source graph visualization software package, available at http://www.graphviz.org/. 2 P is the set of problems that can be solved in polynomial time. NP is the set of problems whose solutions can be verified in polynomial time. An NP-Hard problem is a problem to which any NP problem can be reduced in polynomial time. An NP-Complete problem is both NP and NP-Hard. A major open mathematical question is whether or not P = NP. If P ≠ NP (which seems likely), then no polynomial algorithm will ever be found for any NP-Complete problem (except perhaps on a quantum computer). 3 log2 is the binary logarithm. It is equal to log2(m) = log(m) / log(2). 4 A reduction of entropy is often called an information gain. 5 See Sebastian Raschka’s interesting analysis for more details. 6 It randomly selects the set of features to evaluate at each node.

Warning As you can see, the CART algorithm is a greedy algorithm: it greedily searches for an optimum split at the top level, then repeats the process at each level. It does not check whether or not the split will lead to the lowest possible impurity several levels down. A greedy algorithm often produces a reasonably good solution, but it is not guaranteed to be the optimal solution. Unfortunately, finding the optimal tree is known to be an NP-Complete problem:2 it requires O(exp(m)) time, making the problem intractable even for fairly small training sets. This is why we must settle for a “reasonably good” solution. Computational Complexity Making predictions requires traversing the Decision Tree from the root to a leaf. Decision Trees are generally approximately balanced, so traversing the Decision Tree requires going through roughly O(log2(m)) nodes.3 Since each node only requires checking the value of one feature, the overall prediction complexity is just O(log2(m)), independent of the number of features.

Pac-Man Using Deep Q-Learning min_after_dequeue, RandomShuffleQueue MNIST dataset, MNIST-MNIST model parallelism, Model Parallelism-Model Parallelism model parameters, Gradient Descent, Batch Gradient Descent, Early Stopping, Under the Hood, Quadratic Programming, Creating Your First Graph and Running It in a Session, Construction Phase, Training RNNsdefining, Model-based learning model selection, Model-based learning model zoos, Model Zoos model-based learning, Model-based learning-Model-based learning modelsanalyzing, Analyze the Best Models and Their Errors-Analyze the Best Models and Their Errors evaluating on test set, Evaluate Your System on the Test Set-Evaluate Your System on the Test Set moments, Adam Optimization Momentum optimization, Momentum optimization-Momentum optimization Monte Carlo tree search, Policy Gradients Multi-Layer Perceptrons (MLP), Introduction to Artificial Neural Networks, The Perceptron-Multi-Layer Perceptron and Backpropagation, Neural Network Policiestraining with TF.Learn, Training an MLP with TensorFlow’s High-Level API multiclass classifiers, Multiclass Classification-Multiclass Classification Multidimensional Scaling (MDS), Other Dimensionality Reduction Techniques multilabel classifiers, Multilabel Classification-Multilabel Classification Multinomial Logistic Regression (see Softmax Regression) multinomial(), Neural Network Policies multioutput classifiers, Multioutput Classification-Multioutput Classification MultiRNNCell, Distributing a Deep RNN Across Multiple GPUs multithreaded readers, Multithreaded readers using a Coordinator and a QueueRunner-Multithreaded readers using a Coordinator and a QueueRunner multivariate regression, Frame the Problem N naive Bayes classifiers, Multiclass Classification name scopes, Name Scopes natural language processing (NLP), Recurrent Neural Networks, Natural Language Processing-An Encoder–Decoder Network for Machine Translationencoder-decoder network for machine translation, An Encoder–Decoder Network for Machine Translation-An Encoder–Decoder Network for Machine Translation TensorFlow tutorials, Natural Language Processing, An Encoder–Decoder Network for Machine Translation word embeddings, Word Embeddings-Word Embeddings Nesterov Accelerated Gradient (NAG), Nesterov Accelerated Gradient-Nesterov Accelerated Gradient Nesterov momentum optimization, Nesterov Accelerated Gradient-Nesterov Accelerated Gradient network topology, Fine-Tuning Neural Network Hyperparameters neural network hyperparameters, Fine-Tuning Neural Network Hyperparameters-Activation Functionsactivation functions, Activation Functions neurons per hidden layer, Number of Neurons per Hidden Layer number of hidden layers, Number of Hidden Layers-Number of Hidden Layers neural network policies, Neural Network Policies-Neural Network Policies neuronsbiological, From Biological to Artificial Neurons-Biological Neurons logical computations with, Logical Computations with Neurons neuron_layer(), Construction Phase next_batch(), Execution Phase No Free Lunch theorem, Testing and Validating node edges, Visualizing the Graph and Training Curves Using TensorBoard nonlinear dimensionality reduction (NLDR), LLE(see also Kernel PCA; LLE (Locally Linear Embedding)) nonlinear SVM classification, Nonlinear SVM Classification-Computational Complexitycomputational complexity, Computational Complexity Gaussian RBF kernel, Gaussian RBF Kernel-Gaussian RBF Kernel with polynomial features, Nonlinear SVM Classification-Polynomial Kernel polynomial kernel, Polynomial Kernel-Polynomial Kernel similarity features, adding, Adding Similarity Features-Adding Similarity Features nonparametric models, Regularization Hyperparameters nonresponse bias, Nonrepresentative Training Data nonsaturating activation functions, Nonsaturating Activation Functions-Nonsaturating Activation Functions normal distribution (see Gaussian distribution) Normal Equation, The Normal Equation-Computational Complexity normalization, Feature Scaling normalized exponential, Softmax Regression norms, Select a Performance Measure notations, Select a Performance Measure-Select a Performance Measure NP-Complete problems, The CART Training Algorithm null hypothesis, Regularization Hyperparameters numerical differentiation, Numerical Differentiation NumPy, Create the Workspace NumPy arrays, Handling Text and Categorical Attributes NVidia Compute Capability, Installation nvidia-smi, Managing the GPU RAM n_components, Choosing the Right Number of Dimensions O observation space, Neural Network Policies off-policy algorithm, Temporal Difference Learning and Q-Learning offline learning, Batch learning one-hot encoding, Handling Text and Categorical Attributes one-versus-all (OvA) strategy, Multiclass Classification, Softmax Regression, Exercises one-versus-one (OvO) strategy, Multiclass Classification online learning, Online learning-Online learning online SVMs, Online SVMs-Online SVMs OpenAI Gym, Introduction to OpenAI Gym-Introduction to OpenAI Gym operation_timeout_in_ms, In-Graph Versus Between-Graph Replication Optical Character Recognition (OCR), The Machine Learning Landscape optimal state value, Markov Decision Processes optimizers, Faster Optimizers-Learning Rate SchedulingAdaGrad, AdaGrad-AdaGrad Adam optimization, Faster Optimizers, Adam Optimization-Adam Optimization Gradient Descent (see Gradient Descent optimizer) learning rate scheduling, Learning Rate Scheduling-Learning Rate Scheduling Momentum optimization, Momentum optimization-Momentum optimization Nesterov Accelerated Gradient (NAG), Nesterov Accelerated Gradient-Nesterov Accelerated Gradient RMSProp, RMSProp out-of-bag evaluation, Out-of-Bag Evaluation-Out-of-Bag Evaluation out-of-core learning, Online learning out-of-memory (OOM) errors, Static Unrolling Through Time out-of-sample error, Testing and Validating OutOfRangeError, Reading the training data directly from the graph, Multithreaded readers using a Coordinator and a QueueRunner output gate, LSTM Cell output layer, Multi-Layer Perceptron and Backpropagation OutputProjectionWrapper, Training to Predict Time Series-Training to Predict Time Series output_put_keep_prob, Applying Dropout overcomplete autoencoder, Unsupervised Pretraining Using Stacked Autoencoders overfitting, Overfitting the Training Data-Overfitting the Training Data, Create a Test Set, Soft Margin Classification, Gaussian RBF Kernel, Regularization Hyperparameters, Regression, Number of Neurons per Hidden Layeravoiding through regularization, Avoiding Overfitting Through Regularization-Data Augmentation P p-value, Regularization Hyperparameters PaddingFIFOQueue, PaddingFifoQueue Pandas, Create the Workspace, Download the Datascatter_matrix, Looking for Correlations-Looking for Correlations parallel distributed computing, Distributing TensorFlow Across Devices and Servers-Exercisesdata parallelism, Data Parallelism-TensorFlow implementation in-graph versus between-graph replication, In-Graph Versus Between-Graph Replication-Model Parallelism model parallelism, Model Parallelism-Model Parallelism multiple devices across multiple servers, Multiple Devices Across Multiple Servers-Other convenience functionsasynchronous communication using queues, Asynchronous Communication Using TensorFlow Queues-PaddingFifoQueue loading training data, Loading Data Directly from the Graph-Other convenience functions master and worker services, The Master and Worker Services opening a session, Opening a Session pinning operations across tasks, Pinning Operations Across Tasks sharding variables, Sharding Variables Across Multiple Parameter Servers sharing state across sessions, Sharing State Across Sessions Using Resource Containers-Sharing State Across Sessions Using Resource Containers multiple devices on a single machine, Multiple Devices on a Single Machine-Control Dependenciescontrol dependencies, Control Dependencies installation, Installation-Installation managing the GPU RAM, Managing the GPU RAM-Managing the GPU RAM parallel execution, Parallel Execution-Parallel Execution placing operations on devices, Placing Operations on Devices-Soft placement one neural network per device, One Neural Network per Device-One Neural Network per Device parameter efficiency, Number of Hidden Layers parameter matrix, Softmax Regression parameter server (ps), Multiple Devices Across Multiple Servers parameter space, Gradient Descent parameter vector, Linear Regression, Gradient Descent, Training and Cost Function, Softmax Regression parametric models, Regularization Hyperparameters partial derivative, Batch Gradient Descent partial_fit(), Incremental PCA Pearson's r, Looking for Correlations peephole connections, Peephole Connections penalties (see rewards, in RL) percentiles, Take a Quick Look at the Data Structure Perceptron convergence theorem, The Perceptron Perceptrons, The Perceptron-Multi-Layer Perceptron and Backpropagationversus Logistic Regression, The Perceptron training, The Perceptron-The Perceptron performance measures, Select a Performance Measure-Select a Performance Measureconfusion matrix, Confusion Matrix-Confusion Matrix cross-validation, Measuring Accuracy Using Cross-Validation-Measuring Accuracy Using Cross-Validation precision and recall, Precision and Recall-Precision/Recall Tradeoff ROC (receiver operating characteristic) curve, The ROC Curve-The ROC Curve performance scheduling, Learning Rate Scheduling permutation(), Create a Test Set PG algorithms, Policy Gradients photo-hosting services, Semisupervised learning pinning operations, Pinning Operations Across Tasks pip, Create the Workspace Pipeline constructor, Transformation Pipelines-Select and Train a Model pipelines, Frame the Problem placeholder nodes, Feeding Data to the Training Algorithm placers (see simple placer; dynamic placer) policy, Policy Search policy gradients, Policy Search (see PG algorithms) policy space, Policy Search polynomial features, adding, Nonlinear SVM Classification-Polynomial Kernel polynomial kernel, Polynomial Kernel-Polynomial Kernel, Kernelized SVM Polynomial Regression, Training Models, Polynomial Regression-Polynomial Regressionlearning curves in, Learning Curves-Learning Curves pooling kernel, Pooling Layer pooling layer, Pooling Layer-Pooling Layer power scheduling, Learning Rate Scheduling precision, Confusion Matrix precision and recall, Precision and Recall-Precision/Recall TradeoffF-1 score, Precision and Recall-Precision and Recall precision/recall (PR) curve, The ROC Curve precision/recall tradeoff, Precision/Recall Tradeoff-Precision/Recall Tradeoff predetermined piecewise constant learning rate, Learning Rate Scheduling predict(), Data Cleaning predicted class, Confusion Matrix predictions, Confusion Matrix-Confusion Matrix, Decision Function and Predictions-Decision Function and Predictions, Making Predictions-Estimating Class Probabilities predictors, Supervised learning, Data Cleaning preloading training data, Preload the data into a variable PReLU (parametric leaky ReLU), Nonsaturating Activation Functions preprocessed attributes, Take a Quick Look at the Data Structure pretrained layers reuse, Reusing Pretrained Layers-Pretraining on an Auxiliary Taskauxiliary task, Pretraining on an Auxiliary Task-Pretraining on an Auxiliary Task caching frozen layers, Caching the Frozen Layers freezing lower layers, Freezing the Lower Layers model zoos, Model Zoos other frameworks, Reusing Models from Other Frameworks TensorFlow model, Reusing a TensorFlow Model-Reusing a TensorFlow Model unsupervised pretraining, Unsupervised Pretraining-Unsupervised Pretraining upper layers, Tweaking, Dropping, or Replacing the Upper Layers Pretty Tensor, Up and Running with TensorFlow primal problem, The Dual Problem principal component, Principal Components Principal Component Analysis (PCA), PCA-Randomized PCAexplained variance ratios, Explained Variance Ratio finding principal components, Principal Components-Principal Components for compression, PCA for Compression-Incremental PCA Incremental PCA, Incremental PCA-Randomized PCA Kernel PCA (kPCA), Kernel PCA-Selecting a Kernel and Tuning Hyperparameters projecting down to d dimensions, Projecting Down to d Dimensions Randomized PCA, Randomized PCA Scikit Learn for, Using Scikit-Learn variance, preserving, Preserving the Variance-Preserving the Variance probabilistic autoencoders, Variational Autoencoders probabilities, estimating, Estimating Probabilities-Estimating Probabilities, Estimating Class Probabilities producer functions, Other convenience functions projection, Projection-Projection propositional logic, From Biological to Artificial Neurons pruning, Regularization Hyperparameters, Symbolic Differentiation Pythonisolated environment in, Create the Workspace-Create the Workspace notebooks in, Create the Workspace-Download the Data pickle, Better Evaluation Using Cross-Validation pip, Create the Workspace Q Q-Learning algorithm, Temporal Difference Learning and Q-Learning-Learning to Play Ms.


pages: 205 words: 20,452

Data Mining in Time Series Databases by Mark Last, Abraham Kandel, Horst Bunke

call centre, computer vision, discrete time, G4S, information retrieval, iterative process, NP-complete, p-value, pattern recognition, random walk, sensor fusion, speech recognition, web application

Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press. Median Strings: A Review 191 14. Guyon, Schomaker, L., Plamondon, R., Liberman, M. and Janet, S. (1994). UNIPEN Project on On-Line Exchange and Recognizer Benchmarks. Proc. of 12th Int. Conf. on Pattern Recognition, pp. 29–33. 15. de la Higuera, C. and Casacuberta, F. (2000). Topology of Strings: Median String is NP-Complete. Theoretical Computer Science, 230(1/2), 39–48. 16. Jiang, X., Schiffmann, L., and Bunke, H. (2000). Computation of Median Shapes. Proc. of 4th. Asian Conf. on Computer Vision, pp. 300–305, Taipei. 17. Jiang, X., Abegglen, K., and Bunke, H. (2001). Genetic Computation of Generalized Median Strings. (Submitted for publication.) 18. Jiang, X., Abegglen, K., Bunke, H., and Csirik, J. (2002). Dynamic Computation of Generalized Median Strings, Pattern Analysis and Applications.

Sanchez, G., Llados, J., and Tombre, K. (2002). A Mean String Algorithm to Compute the Average Among a Set of 2D Shapes. Pattern Recognition Letters, 23(1–3), 203–213. 34. Sankoff, D. and Kruskal, J.B. (1983). (eds.). Time Warps, String Edits, and Macromolecules: The Theory and Practice of String Comparison, AddisonWesley. 35. Sim, J.S. and Park, K. (2001). The Consensus String Problem for a Metric is NP-Complete. Journal of Discrete Algorithms, 2(1). 36. Stephen, G.A. (1994). String Searching Algorithms, World Scientific. 37. Subramanyan, K. and Dean, D. (2000). A Procedure to Average 3D Anatomical Structures. Medical Image Analysis, 4(4), 317–334. 38. Wagner, R.A. and Fischer, M.J. (1974). The String-to-String Correction Problem. Journal of the ACM, 21(1), 168–173. 39. Wang, L. and Jiang, Y. (1994). On the Complexity of Multiple Sequence Alignment.


pages: 931 words: 79,142

Concepts, Techniques, and Models of Computer Programming by Peter Van-Roy, Seif Haridi

computer age, Debian, discrete time, Donald Knuth, Eratosthenes, fault tolerance, G4S, general-purpose programming language, George Santayana, John von Neumann, Lao Tzu, Menlo Park, natural language processing, NP-complete, Paul Graham, premature optimization, sorting algorithm, Therac-25, Turing complete, Turing machine, type inference

Other problems are expensive for more fundamental reasons. For example, NP-complete problems. These problems are in the class NP, i.e., it is easy to check a solution, if you are given a candidate.14 But finding a solution may be much harder. A simple example is the circuit satisfiability problem. Given a combinational digital circuit that consists of And, Or, and Not gates, does there exist a set of input values that makes the output 1? This problem is NP-complete [47]. An NP-complete problem is a special kind of NP problem with the property that if you can solve one in polynomial time, then you can solve all in polynomial time. Many computer scientists have tried over several decades to find polynomial-time solutions to NP-complete problems, 13. Kurzweil claims that the growth rate is increasing and will lead to a “singularity” somewhere near the middle of the 21st century. 14.

Paul, 257 Mozart Consortium, xxiv, xxvi, 106 Mozart Programming System, 254 Base modules, 229, 729 Browser tool, 1, 88 displaying cyclic structures, 102 displaying strings, 716 WaitQuiet operation, 798 cheap concurrency, 252 command line interface, 817 Compiler Panel tool, 815 Distribution Panel tool, 815 Explorer tool, 757, 815 garbage collection, 78 GlobalStore, 743 interactive interface, 1, 87, 815 kernel languages, 844 library modules, 229 limited role of the compiler, 504 memory consumption, 174 Open Source license, xxiv overview, xxiv Panel tool, 815 performance, 201, 379 Prototyper tool, 689 separate compilation, 457 Standard Library, 214, 225, 230, 685, 690 System modules, 229, 729 thread scheduler, 253 uncaught exception, 93, 801 multi-agent systems (MAS), xxiii, 345, 362, 576 multimedia, 176 multiprocessor cluster, 711 shared-memory, 710 multiset, 240 mutable store (for cells), 794 Myriorama, 273 n-queens problem, 629 name, 203, 714, 791, 824, 847 defining scope, 508 distributed computing, 711 fresh, 203 generation, 206 impure, 715 pure, 715 name server, 403, 711 natural design, 461, 569 natural language, xiii, 31, 38, 641 natural selection, 451, 462 Naur, Peter, 32 Index 885 needed variable, 283, 796 negation as failure, 662, 674 nesting marker, 53, 83, 355, 365 Netherlands, 819 network awareness, 387, 723 network transparency, 255, 387, 708 neutral element, 187 New operation, 495, 549 NewActive operation, 558 NewActiveExc operation, 562, 728 NewArray operation, 436 NewCell operation, 416 NewDictionary operation, 437 NewLock operation, 22, 583 NewName operation, 203, 792, 824 NewPort operation, 349 NewSpace operation, 764 NewStat operation, 725 resilient, 742 Newton’s method for square roots, 119 Newton, Isaac, 278 nil, 828 node (in Erlang), 387 noise (electronic), 473 nonblocking operation, 333 receive (in Erlang), 394 delete (in queue), 598 read (in tuple space), 586 receive, 333 send, 333 stack, 578 noncompositional design, 461 nondeterminism choice statement, 621, 623, 772 declarative concurrent model, 575 don’t know, 324, 621 introduction, 20 limitation of declarative model, 319 logic programming, 638 observable, 20, 234, 319, 570, 573, 575, 576 bounded buffer, 595 Filter operation, 386 lack of in Flavius Josephus problem, 561 relation to exceptions, 327 relation to coroutines, 275 thread scheduler, 253 nonstrict evaluation, 331 Haskell, 310 nonvar operation (in Prolog), 660, 662 normal distribution, 476 normal order reduction, 330 Haskell, 309 notify operation (in monitor), 592 notifyAll operation (in monitor), 593 NP-complete problems, 176 NUL character, 841 number, 52, 819 O’Keefe, Richard, 111, 407, 668 object, 413, 420, 542, 546 declarative, 423, 483, 568 introduction, 17 Java, 551, 807 passive, 556, 575, 576 strong, 542 object code, 221 object graph, 553 object, active, 350, 556–567 comparison with passive object, 556 defining behavior with a class, 558 polymorphism, 429 object, port, 346, 350, 413 approaches to concurrency, 573 Erlang, 563 further reading, 582 many-to-one communication, 351 polymorphism, 429 reactive, 351 reasoning, 352 886 Index sharing one thread, 378 when to use, 576 object, stream, 256, 265–266, 411, 413, 574 comparison with port object, 351 Flavius Josephus problem, 561 higher-order iteration, 258 polymorphism, 429 producer/consumer, 257 transducer, 259 Ockham, William of, 29 octal integer, 819 Okasaki, Chris, 175, 330 OLE (Object Linking and Embedding), 462 OMG (Object Management Group), 462 open distribution, 709, 711, 714 open program, 202 Open Source software, xxiv operating system, 208 Linux, xxvi, 201, 471, 499 Mac OS X, xxiv, xxvi, 254 Solaris, xxvi, xxix Unix, xxiv, 254, 305, 459, 553, 642 VM (Virtual Machine), 41 Windows, xxiv, 254 operation (in data abstraction), 420 operational semantics, 38, 60, 635, 779–811 operator associativity, 34, 837 binary, 34, 836 infix, 52, 83, 185, 793, 826, 828, 830, 836 mixfix, 826, 837 postfix, 837 precedence, 34, 836 prefix, 836 ternary, 838 unary, 836 OPI (Oz programming interface), 815 optimistic scheduling, 603 optimization, 177 avoid during development, 452 combinatoric, 661 compiler, 162 eager execution, 302 early error detection, 504 first-argument indexing, 659 memoization, 694 monitor performance, 597 object system, 545 relational programming, 622 short-circuit protocol, 559 standard computer, 314 thread priorities, 265 order-independence, 49 unification, 110, 232 orelse operator, 83 otherwise method, 500 OTP (Ericsson Open Telecom Platform), 386 overloading, 313, 429 overriding relation, 502 Oz, Wizard of, 1 ozc command, 228, 817 pairwise distinct, 756, 774, 782 palindrome, 628 palindrome product problem, 628, 757 Panangaden, Prakash, 338 Panel tool, see Mozart Programming System Papert, Seymour, xiii, 233 paradigm, xiii, xvi, see computation model declarative, 29 school of thought, xvi paragraph (in OPI), 815 parallelism, 237, 322 difference with concurrency, 322 importance of nonstrictness, 331 importance of worst-case complexity, 174 parameter passing, 430–434 Index 887 call by name, 432 exercise, 484 call by need, 433 exercise, 485 lazy evaluation, 433 call by reference, 57, 430 Java, 555 call by value, 431 Java, 555 call by value-result, 431 call by variable, 430 parity, 14 Parnas, David Lorge, xxii, 462 parser, 32, 161–166 generic, 650 gump tool, 39 natural language, 641 partial failure, 326 partial list, 440, 829 partial order, 238 partial termination, 243, 338, 804 partial value, 46 Pascal’s triangle, 4 Pascal, Blaise, 5 pass by . . . , see parameter passing pattern matching case statement, 6, 67 function (in Erlang), 388 Haskell, 309 receive expression (in Erlang), 391 reduction rule semantics, 784 PDA (procedural data abstraction), 420 pencil, xviii Pentium III processor, 201, 471 performance cluster computing, 711 competitive concurrency, 254 constraint programming, 758 Cray-1 supercomputer, 175 declarative programming, 313 dictionary, 201 distributed stream, 724 lazy language, 289, 342 measuring, 167 memoization, 25, 315 mobile object, 724 monitor, 597 Mozart Programming System, 201, 379 personal computer, 175 price of concurrency, 339 record field access, 438 role of optimization, 177, 265, 302 role of parallelism, 237, 322 transitive closure, 471 word-of-mouth simulation, 486 permanent failure, 739 permutations, 2 persistence data structure, 149, 297 database, 654 Erlang, 387 transaction, 600 personal computer, 3, 252, 254, 289, 304 low-cost, 74, 175 pessimistic scheduling, 603 Phidani Software, 642 π calculus, xvii, 41, 54, 805 pipeline, 259 pixel, 556 placeholder dataflow variable, 86 future (in Multilisp), 336 GUI design, 686, 703 planning flight, 671 WARPLAN, 621 Plotkin, Gordon, 779 point resting, 338 synchronization, 333 two-dimensional space, 554 pointer, 76 content edge, 733 888 Index dependency, 459 dynamic typing, 106 garbage collection, 76 memory block, 480 resource, 480 state, 733 POLA (Principle of Least Authority), 209 polymorphism, 18, 106, 425, 462, 493 active objects, 429 ad-hoc, 429 apportioning responsibility, 425 example, 530 Haskell, 312 object-oriented programming, 490 port objects, 429 stream objects, 429 universal, 429 Ponsard, Christophe, 545 port (explicit state), 349, 719, 848 communication from inside encapsulated search, 673 distributed semantics, 383 Port.sendRecv operation, 673 portal, 476 postcondition, 441, 521 potential function, 175 precondition, 441, 521 predicate calculus, 633 preemption, 252 preprocessor, 318 DCG (in Prolog), 649 design patterns, 536 extended DCG (in Prolog), 140 fallacy of, 318 presentation model (in GUI), 695 principle abstraction, 410 avoid changing interfaces, 458 avoid premature optimization, 177, 452 balance planning and refactoring, 452 centralized first, distributed later, 745 class is final by default, 492 compartmentalize responsibility, 425, 451 concentrate explicit state, 412 creative extension, xiv, 844 decisions at right level, 460 declarative concurrency, 242, 281 document component interfaces, 451 documented violations, 460 eager default, lazy declared, 330 encapsulate design decisions, 458 enriching control (in logic programming), 640 error confinement, 90 “everything should be an object”, 542 exploit data abstraction uniformity, 543 form mirrors content, 544 freely exchange knowledge, 451 function structure follows type structure, 135 functional abstraction, 4 last call optimization, 72 layered language design, 850 least authority (POLA), 209 least expressiveness, 323 least privilege, 209 minimize dependencies, 387, 459 minimize indirections, 459 model independence, 457 more is not better or worse, just different, xx Mozart design rules, xxvi natural selection, 451, 462 need to know, 209 objects over ADTs, 490 pay only on use, 620 predictable dependencies, 460 run time is all there is, 504, 690 separation of concerns, 567 stateful component with declara- Index 889 tive behavior, 417 substitution property, 518, 521, 523 syntax stability, 643 system decomposition, 210 type first, 137 use data abstraction everywhere, 489, 543 working software keeps working, 59, 459, 722 private scope, 507, 508 C++ and Java sense, 508 Smalltalk and Oz sense, 507 probability exponential distribution, 475 Gaussian distribution, 476 normal distribution, 476 uniform distribution, 474 unique name generation, 207 problem cryptarithmetic, 755, 776 digital logic satisfiability, 176 Flavius Josephus, 558–561 flight planning, 671 grocery puzzle, 774 halting, 209, 681 Hamming, 293, 342 intractable, 176 library scheduler, 672 making change, 775 n-queens, 629 NP-complete, 176 palindrome product, 628, 757 Send-More-Money, 755, 776 undecidable, 209 zebra puzzle, 774 proc statement, 65, 792 procedure as component, 412 basic operations, 55 external reference, 65 importance, 54 order, 177 tail-recursive, 72 procedure value (closure), 65, 178, 792 anonymous, 53 common limitation, 179, 552 distributed lexical scoping, 722 encoding as an object, 540 higher-order programming, 177 relation to inner class, 552 process concurrent calculus, 54 concurrent program design, 364 CSP, 619 distributed system, 707 Erlang, 350, 386, 389 large program design, 450 operating system, 255 producer and consumer, 724 run-time error, 96 small program design, 218 processor, 237 cluster computing, 711 dataflow machine, 337, 469 parallel functional programming, 331 shared-memory multiprocessor, 710 producer, 257 profiling, 177, 452 program design, see software development program point, 444, 606 programming, xv, 1 accumulator, 139 component-based, 412 concurrent, 573 constraint, 44, 274, 577, 663 data-centered, 576 declarative, 29, 406 descriptive, 115 need for algorithms, 116 programmable, 115 Erlang, 388 flow-based, 257 functional, 406 890 Index future developments, 461 good style, xxi Haskell, 309 higher-order, 113, 123, 177–194 introduction, 13 relation to object-oriented, 538 imperative, 29, 406 Java, 552, 615 kernel language approach, xvi logic, 44, 101, 142, 406, 632 multi-agent, 412, 576 multiparadigm, xiv, xxvi event manager, 566 nonalgorithmic, 622 object-based, 19, 538 object-oriented (OOP), 19, 413, 489 open, 105, 202 paradigm, xiii, xvi, 29, see computation model Prolog, 663 real-time, 304 relational, 621 stateful, 29 stateless, 29 synchronous, 266 programming model, xiii, 29 Prolog, 660–671 Aquarius, 140, 661 Parma, 661 SICStus, 190, 663 state threads package, 190 proof engineering, 117 proof rule, 444 propagate-and-search, 629, 750 propagator, 752, 760 property liveness, 602 object, 497 safety, 602 propositional logic, 632 protected scope, 508 C++ sense, 509 Java sense, 567 protection boundary, 202 protector, 325 protocol, 353 by-need, 282 communication, 715 consistency, 712 DHCP (Dynamic Host Connection Protocol), 207 distributed binding, 733 distributed unification, 733 eager copy, 734 eager immediate copy, 734 interaction (in GUI), 682 invalidation, 733 IP (Internet Protocol), 206 lazy copy, 733 meta-object, 516 mobile state, 733 negotiation, 376 short-circuit, 559 stationary state, 733 TCP (Transmission Control Protocol), 712, 740 timer, 368 Prototyper tool, 689 pseudorandom numbers, 473 Psion Series 3 palmtop computer, 378 public scope, 507 pure object-oriented language, 543 QTk, 213, 680, 729 interactive use, 214, 684 Prototyper, 689 use in application, 225 quadratic equation, 179 quantifier, 441, 445, 633, 645 existential (in Prolog), 671 quantum (in thread scheduling), 252 query database, 655 logic programming, 634 queue, 145 amortized ephemeral, 147 amortized persistent, 298 Index 891 breadth-first traversal, 156 concurrent, 379, 583 nonblocking delete, 598 priority, 605, 614 worst-case ephemeral, 147 worst-case persistent, 299 race condition, 20, 234 raise statement, 93, 801 random number generation, 472 rational tree, 760 Raymond, Eric, 462 reachable memory, 74 ReadOnly operation, 799 real-time computing garbage collection, 76 hard, 174, 253, 254, 304 soft, 304 reasoning algebraic, 111, 116, 323 atomic action, 581 causal, 353, 575 lift control system, 375 logical, xix, 111, 632 message-passing concurrent model, 352 shared-shate concurrent model, 324 stateful model, 324, 440 receive asynchronous, 332 nonblocking, 333 synchronous, 332 receive expression (in Erlang), 391 recomputation, 761, 776 record, 19, 52, 825 adjoin, 827 basic operations, 54, 826 dynamic creation, 165, 549, 695 importance, 53 type, 438 usage trade-offs, 438 recurrence equation, 167 recursion, 3, 113, 124 direct, 113 indirect, 113 mutual, 110 polymorphic, 309 programming with, 127 Prototyper tool, 690 tail recursion optimization, 72 red cut (in Prolog), 670 Red Hat Corporation, xxvi, 201, 471 reduction order, 330–332 applicative, 330 normal, 330 reduction rule, 784 reengineering, 522 refactoring, 452 reference, 714 referential transparency, 113 reflection, 515 region (in OPI), 815 register abstract machine, 56 forwarding, 621 memory management, 74 registration action procedures (in GUI), 683 display refresh (FlexClock), 700 distributed binding, 737 finalization, 481 relation, 655 relative error, 120 reliability, 711 rendezvous, 619 replicator, 326 research project, xxiv resolution deadlock, 605 logic programming, 635, 640, 662 SLDNF, 662 video display, 321 resource distributed component, 746 distributed system, 729 external, 77, 480 file descriptor, 293 892 Index localized, 709 producer/consumer pipeline, 261 use of laziness, 289 responsibility atomicity and consistency (in transaction), 600 compartmentalize (in a team), 451 coroutine (avoiding starvation), 275 design by contract, 521 distributed memory management, 738 dynamic typing, 493 failure confinement, 245 memory management, 76 role of polymorphism, 425 type inference, 137 resting point, 338 restriction (environment), 62 retract/1 operation (in Prolog), 662 return (in for loop), 190 Reuter, Andreas, 582, 600 Reynolds, John C., 419 right, see name Rinard, Martin C., 338 RISC (Reduced Instruction Set Computer) microprocessor, 621 RMI (remote method invocation), 354, 709, 724, 725 root variable, 763 Round operation, 822 RPC (remote procedure call), 354, 709 rubber band, 251 runic inscription, 779 Runnable interface (in Java), 616 s-expression, 650 Sacks, Oliver, 405 safety, 602 Saint-Exupéry, Antoine de, 111 Santayana, George, 694 Saraswat, Vijay A., 338, 662, 808 scalability compilation, 458 multiprocessor, 710 program development, 105 weighted reference counting, 737 scalar product (constraint), 775 scheduler Delay operation, 304 deterministic, 253 lift control system, 366 nondeterministic, 253 randomness, 473 resource allocation, 672 round-robin, 252, 256 thread, 239, 252 transaction, 603 Schulte, Christian, xxvi science, xv, xviii scientific method, xvii scope, 56, 507 attribute, 510 dynamic, 59 lexical, 57, 59, 64, 508, 539 absence in Prolog, 661 distributed, 722 hiding, 221, 411, 423, 442, 483, 495, 549 substitution, 803 private, 507, 508 protected, 508 public, 507 static, see lexical user-defined, 508 search aggregate, 670 all-solutions, 626 binary, 151 branch-and-bound, 772 breadth-first, 644 communication from inside encapsulated search, 673 constraint programming, 274 contribution of AKL, 809 danger, 639 Index 893 database query, 657 depth-first, 622, 644 deterministic, 621 encapsulated, 625 generate-and-test, 629, 758 iterative deepening, 644 linear, 197 logic programming, 661 n-queens problem, 629 one-solution, 626 overuse, xxi propagate-and-search, 629, 750 pruning, 662 relational computation model, 623 relational programming, 621 saturation, 772 search space, 622 search strategy, 761 search tree, 624 security abstract data type, 201–210 application, 744 atom vs. name, 508 capability, 208 data abstraction, 419–435 distributed resources, 731 distributed system, 743 engineering, 744 hardware, 744 human society, 208 implementation, 744 kernel language concepts, 847 language, 208, 744 linguistic abstraction, 39 mechanism, 208 open distribution, 711 policy, 208 right, 791, 847 static typing, 106 threat model, 744 self clone, 517 delegation, 511 dynamic binding, 505 forwarding, 511 Java, 553 this notation, 551 self (in Erlang), 390 semantic stack, 62 runnable, 62 suspended, 62 terminated, 62 semantics, 31 abstract machine, 56–78, 92–94, 239–241, 282–283, 348–349, 416–417 axiomatic, 38, 440–450, 632 by-need trigger, 282 cell, 416 common abstractions, 808 denotational, 38 exceptions, 92 interleaving, 780 kernel language, see abstract machine kernel language approach, 38 logical, 38, 631–641 monitor (in Java), 592 operational, 38, 60, 635, 779–811 port, 348, 383 secure types, 203 semantic statement, 61 SOS (structural operational semantics), 779 thread, 239 Send operation, 349 slot-reserving semantics, 384 send asynchronous, 332 latency, 263 nonblocking, 333 synchronous, 332 Send-More-Money problem, 755, 776 separation of concerns, 567 sequential logic, 269 serializability, 600 serialization, 709 894 Index serializer, 325 set comprehension, 301 setof/3 operation (in Prolog), 626, 666, 670 Shakespeare, William, 815 shared-state concurrency, see atomic action, see lock, see monitor, see transaction sharing, 418 Browser tool, 102, 829 distributed state, 720 distributed value, 716 thread, 378 short-circuit concurrent composition, 277 Flavius Josephus problem, 559 transitive closure, 464 Show operation, 340 side effect, 411 declarative, 288 signal operation (in monitor), 592 signature (of procedure), 129 simulation components, 412 digital logic, 266–272 inadequacy of declarative model, 173 Internet, 412 multi-agent, 412 slow network, 578 small world, 486 word-of-mouth, 476 Simurgh, 707 single-assignment store, 42–49, 60, 781 importance, 43 singularity, 176 sink (consumer), 259 64-bit address, 78 64-bit word, 74, 175, 820 skip statement, 62, 785 SLDNF resolution, 662 small world graph, 461 simulation, 486 Smolka, Gert, xxvi snapshot (of state), 437, 718 software design, see design methodology, see language design software development, 218, 450 bottom-up, 451 compositional, 453 concurrent components, 362 distributed programming, 745 evolutionary, 451 extreme programming, 452 framework, 492 IID (Iterative and Incremental), 451 importance of names, 508 in the large, 450 in the small, 218 incremental, 451 interactive interface, 87 iterative, 451 middle-out, 451 stepwise refinement, 465, 604 test-driven, 452 top-down, 8, 451 software engineering, 450 component as unit of deployment, 221 concurrency, 233 distributed lexical scoping, 722 further reading, 462 informatics curriculum, xxii lexical scoping, 59 software rot, 459 Solaris operating system, xxvi, xxix Solve operation, 626, 773 SolveAll operation, 626 SolveOne operation, 626 Sort operation, 670, 829 SOS (structural operational semantics), 779 source (producer), 259 source code, 221 interactive, 815 Index 895 million line, xvi, 36, 387, 457, 458 nonexistent, 492 preprocessor input, 318 reengineering, 522 set of functors, 285 textual scope, 64 variable name, 44 space, see computation space, see memory space leak, see memory leak specification, 410 component, 461 specification language, 116 speculative execution (in nonstrict language), 331 stack declarative object, 423 depth-first traversal, 156 memory management, 74 open declarative, 195, 421 proving it correct, 442 secure declarative bundled, 423 secure declarative unbundled, 205, 422 secure stateful bundled, 424 secure stateful unbundled, 424 semantic, 61 stateful concurrent, 578 standalone application, 222 declare not allowed, 87 Java, 555 uncaught exception, 93 starvation, 275 wait set implementation, 597 state cell (mutable variable), 414 declarative, 408 explicit, 16, 409 implicit, 408 interaction with call by name, 485 lazy execution, 481 lazy language, 331 memory management, 77 modularity property, 315 nonstrict language, 331 port (communication channel), 347 reasoning with, 38, 440 revocable capability, 434 threading, 139 transformation, 133 state transition diagram, 353, 368 component design, 364 floor component, 369 lift component, 371 lift controller component, 369 transaction, 607 stateless (declarative programming), 111 statement case, 67, 790 catch (clause in try), 94 choice, 623, 772 conc, 278 declare, 2, 87 fail, 623 finally (clause in try), 94 for, 188 fun, 84 functor, 223 gate, 272 if, 66, 790 local, 56, 63, 786 lock, 22, 583 proc, 65, 792 raise, 93, 801 skip, 62, 785 thread, 241, 785 try, 92, 799 break, 486 compound, 117 compound (in Java), 552 declarative kernel language, 49 interactive, 87 procedure application, 66 sequential composition, 63, 785 suspendable, 65 896 Index value creation, 63 variable-variable binding, 63 static binding, 506 linking, 222 scope, see scope, lexical typing, 51, 104–106 stdin (standard input), 229, 553 stdout (standard output), 553 Steiner, Jennifer G., 334 Stirling’s formula for factorial, 618 storage manager, 325 store, 781 equivalence, 785 mutable (for cells), 416 mutable (for ports), 348 need, 780, 795 predicate, 781 read-only, 206, 798 single-assignment, 42–49, 60, 99, 235, 781 trigger, 282, 795 value, 43 stream, 795 deterministic, 257 Java, 553 merger, 395 producer/consumer, 257 usage trade-offs, 439 strict . . . , see eager . . . strict two-phase locking, 604 strictness analysis, 289, 310, 342 string, 53, 830 virtual, 211, 831 StringToAtom operation, 824 structure compiler, 162 compositional, 461 difference, 141 distribution, 255 effect of concurrency, 252 grammar, 32 hierarchical, 453 interpreter, 653 noncompositional, 461 program, 219, 220 structure equality, 103, 418, 723 substitution, 126, 803 substitution property, 518, 521, 523 subtype basic types, 52 class hierarchy, 518 Sun Microsystems, xxvi, 462 superclass, 503, 513, 556 supercomputer, 175 supply-driven execution, see eager execution suspension Delay operation, 305 due to program error, 48, 89 thread, 239, 276 Sussman, Gerald Jay, 42 Sussman, Julie, 42 Symbian Ltd., 378 symbolic link, 459 synchronization, 333–337 clock, 308 dataflow, 790 synchronized keyword, 593, 616 synchronous communication, 332 active object variant, 562 component interaction, 456 CSP, 619 dependency, 387 error reporting, 360 failure detection, 400, 739 fault confinement, 745 receive, 332 send, 332 synchronous programming, 266 syntactic sugar, 40, 79–84 dynamic record creation, 165 local statement, 40 state transition diagram, 369 syntax, 31 convention for examples, xxix language, 31 nestable constructs (in Oz), 833 Index 897 nestable declarations (in Oz), 833 Oz language, 833 Oz lexical, 839 Prolog, 663 term (in Oz), 833 synthesized argument, 161 system exception, 96 Szyperski, Clemens, 462 tail call optimization, 72 Tanenbaum, Andrew S., 334 task (in concurrency), 780 tautology, 632 TCP (Transmission Control Protocol), 712, 740 technology, xv dangers of concurrency, 21 history of computing, 176 magic, 314 molecular computing, 176 Prolog implementation, 661 reengineering, 522 singularity, 176 software component, 462 synchronous digital, 267 transition to 64-bit, 78 Tel, Gerard, 353 tell operation, 782, 787 temporal logic, 603 temporary failure, 739 term Erlang, 391 Oz, 833 Prolog, 664 termination detection, 276, 382 ping-pong example, 305 failure in declarative program, 245 partial, 243, 338, 804 proof, 449 total, 804 test-driven development, 452 testing declarative programs, 111, 407 dynamic typing, 105 programming in the small, 219 stateful programs, 407 text file, 210 Thalys high-speed train, 382 theorem binomial, 4 Church-Rosser, 331 Gödel’s completeness, 634 Gödel’s incompleteness, 634 halting problem, 681 theorem prover, 117, 634, 662 Therac-25 scandal, 21 thinking machine, 621 third-party independence, 335 32-bit address, 78 32-bit word, 74, 174 this, see self Thompson, D’Arcy Wentworth, 405 thread, 846 declarative model, 233 hanging, 399 interactive interface, 89 introduction, 15 Java, 615 monotonicity property, 239, 781, 782 priority, 253 ready, 239 runnable, 239 suspended, 239 synchronization, 333 thread statement, 241, 785 Thread class (in Java), 616 throughput, 263 thunk, 432 ticket, 480, 714 Connection module, 715 ticking, 307 time complexity, 11 time slice, 252–254 duration, 254 898 Index time-lease mechanism, 480, 734, 738 time-out, 740 Erlang, 391–394 system design, 460 timer protocol, 368 timestamp, 207, 602 timing measurement active object, 379 memory consumption, 173 palindrome product (constraint version), 758 palindrome product (naive version), 629 transitive closure, 471 word frequency, 201 token equality, 418, 714, 723 token passing, 579, 588, 591, 721 token syntax (of Oz), 833 tokenizer, 32, 162 top-down software development, 8, 451 total termination, 804 trade-off asynchronous communication vs. fault confinement, 745 compilation time vs. execution efficiency, 457 compositional vs. noncompositional design, 461 dynamic vs. static scoping, 58 dynamic vs. static typing, 104 explicit state vs. implicit state, 315, 409 expressiveness vs. execution efficiency, 116 expressiveness vs. manipulability, 681 functional decomposition vs. type decomposition, 542 helper procedure placement, 120 indexed collections, 435 inheritance vs. component composition, 462, 492 kernel language design, 844 language design, 811 lazy vs. eager execution, 329 memory use vs. execution speed, 177 names vs. atoms, 510 nonstrictness vs. explicit state, 331, 344 objects vs.

. , see parameter passing pattern matching case statement, 6, 67 function (in Erlang), 388 Haskell, 309 receive expression (in Erlang), 391 reduction rule semantics, 784 PDA (procedural data abstraction), 420 pencil, xviii Pentium III processor, 201, 471 performance cluster computing, 711 competitive concurrency, 254 constraint programming, 758 Cray-1 supercomputer, 175 declarative programming, 313 dictionary, 201 distributed stream, 724 lazy language, 289, 342 measuring, 167 memoization, 25, 315 mobile object, 724 monitor, 597 Mozart Programming System, 201, 379 personal computer, 175 price of concurrency, 339 record field access, 438 role of optimization, 177, 265, 302 role of parallelism, 237, 322 transitive closure, 471 word-of-mouth simulation, 486 permanent failure, 739 permutations, 2 persistence data structure, 149, 297 database, 654 Erlang, 387 transaction, 600 personal computer, 3, 252, 254, 289, 304 low-cost, 74, 175 pessimistic scheduling, 603 Phidani Software, 642 π calculus, xvii, 41, 54, 805 pipeline, 259 pixel, 556 placeholder dataflow variable, 86 future (in Multilisp), 336 GUI design, 686, 703 planning flight, 671 WARPLAN, 621 Plotkin, Gordon, 779 point resting, 338 synchronization, 333 two-dimensional space, 554 pointer, 76 content edge, 733 888 Index dependency, 459 dynamic typing, 106 garbage collection, 76 memory block, 480 resource, 480 state, 733 POLA (Principle of Least Authority), 209 polymorphism, 18, 106, 425, 462, 493 active objects, 429 ad-hoc, 429 apportioning responsibility, 425 example, 530 Haskell, 312 object-oriented programming, 490 port objects, 429 stream objects, 429 universal, 429 Ponsard, Christophe, 545 port (explicit state), 349, 719, 848 communication from inside encapsulated search, 673 distributed semantics, 383 Port.sendRecv operation, 673 portal, 476 postcondition, 441, 521 potential function, 175 precondition, 441, 521 predicate calculus, 633 preemption, 252 preprocessor, 318 DCG (in Prolog), 649 design patterns, 536 extended DCG (in Prolog), 140 fallacy of, 318 presentation model (in GUI), 695 principle abstraction, 410 avoid changing interfaces, 458 avoid premature optimization, 177, 452 balance planning and refactoring, 452 centralized first, distributed later, 745 class is final by default, 492 compartmentalize responsibility, 425, 451 concentrate explicit state, 412 creative extension, xiv, 844 decisions at right level, 460 declarative concurrency, 242, 281 document component interfaces, 451 documented violations, 460 eager default, lazy declared, 330 encapsulate design decisions, 458 enriching control (in logic programming), 640 error confinement, 90 “everything should be an object”, 542 exploit data abstraction uniformity, 543 form mirrors content, 544 freely exchange knowledge, 451 function structure follows type structure, 135 functional abstraction, 4 last call optimization, 72 layered language design, 850 least authority (POLA), 209 least expressiveness, 323 least privilege, 209 minimize dependencies, 387, 459 minimize indirections, 459 model independence, 457 more is not better or worse, just different, xx Mozart design rules, xxvi natural selection, 451, 462 need to know, 209 objects over ADTs, 490 pay only on use, 620 predictable dependencies, 460 run time is all there is, 504, 690 separation of concerns, 567 stateful component with declara- Index 889 tive behavior, 417 substitution property, 518, 521, 523 syntax stability, 643 system decomposition, 210 type first, 137 use data abstraction everywhere, 489, 543 working software keeps working, 59, 459, 722 private scope, 507, 508 C++ and Java sense, 508 Smalltalk and Oz sense, 507 probability exponential distribution, 475 Gaussian distribution, 476 normal distribution, 476 uniform distribution, 474 unique name generation, 207 problem cryptarithmetic, 755, 776 digital logic satisfiability, 176 Flavius Josephus, 558–561 flight planning, 671 grocery puzzle, 774 halting, 209, 681 Hamming, 293, 342 intractable, 176 library scheduler, 672 making change, 775 n-queens, 629 NP-complete, 176 palindrome product, 628, 757 Send-More-Money, 755, 776 undecidable, 209 zebra puzzle, 774 proc statement, 65, 792 procedure as component, 412 basic operations, 55 external reference, 65 importance, 54 order, 177 tail-recursive, 72 procedure value (closure), 65, 178, 792 anonymous, 53 common limitation, 179, 552 distributed lexical scoping, 722 encoding as an object, 540 higher-order programming, 177 relation to inner class, 552 process concurrent calculus, 54 concurrent program design, 364 CSP, 619 distributed system, 707 Erlang, 350, 386, 389 large program design, 450 operating system, 255 producer and consumer, 724 run-time error, 96 small program design, 218 processor, 237 cluster computing, 711 dataflow machine, 337, 469 parallel functional programming, 331 shared-memory multiprocessor, 710 producer, 257 profiling, 177, 452 program design, see software development program point, 444, 606 programming, xv, 1 accumulator, 139 component-based, 412 concurrent, 573 constraint, 44, 274, 577, 663 data-centered, 576 declarative, 29, 406 descriptive, 115 need for algorithms, 116 programmable, 115 Erlang, 388 flow-based, 257 functional, 406 890 Index future developments, 461 good style, xxi Haskell, 309 higher-order, 113, 123, 177–194 introduction, 13 relation to object-oriented, 538 imperative, 29, 406 Java, 552, 615 kernel language approach, xvi logic, 44, 101, 142, 406, 632 multi-agent, 412, 576 multiparadigm, xiv, xxvi event manager, 566 nonalgorithmic, 622 object-based, 19, 538 object-oriented (OOP), 19, 413, 489 open, 105, 202 paradigm, xiii, xvi, 29, see computation model Prolog, 663 real-time, 304 relational, 621 stateful, 29 stateless, 29 synchronous, 266 programming model, xiii, 29 Prolog, 660–671 Aquarius, 140, 661 Parma, 661 SICStus, 190, 663 state threads package, 190 proof engineering, 117 proof rule, 444 propagate-and-search, 629, 750 propagator, 752, 760 property liveness, 602 object, 497 safety, 602 propositional logic, 632 protected scope, 508 C++ sense, 509 Java sense, 567 protection boundary, 202 protector, 325 protocol, 353 by-need, 282 communication, 715 consistency, 712 DHCP (Dynamic Host Connection Protocol), 207 distributed binding, 733 distributed unification, 733 eager copy, 734 eager immediate copy, 734 interaction (in GUI), 682 invalidation, 733 IP (Internet Protocol), 206 lazy copy, 733 meta-object, 516 mobile state, 733 negotiation, 376 short-circuit, 559 stationary state, 733 TCP (Transmission Control Protocol), 712, 740 timer, 368 Prototyper tool, 689 pseudorandom numbers, 473 Psion Series 3 palmtop computer, 378 public scope, 507 pure object-oriented language, 543 QTk, 213, 680, 729 interactive use, 214, 684 Prototyper, 689 use in application, 225 quadratic equation, 179 quantifier, 441, 445, 633, 645 existential (in Prolog), 671 quantum (in thread scheduling), 252 query database, 655 logic programming, 634 queue, 145 amortized ephemeral, 147 amortized persistent, 298 Index 891 breadth-first traversal, 156 concurrent, 379, 583 nonblocking delete, 598 priority, 605, 614 worst-case ephemeral, 147 worst-case persistent, 299 race condition, 20, 234 raise statement, 93, 801 random number generation, 472 rational tree, 760 Raymond, Eric, 462 reachable memory, 74 ReadOnly operation, 799 real-time computing garbage collection, 76 hard, 174, 253, 254, 304 soft, 304 reasoning algebraic, 111, 116, 323 atomic action, 581 causal, 353, 575 lift control system, 375 logical, xix, 111, 632 message-passing concurrent model, 352 shared-shate concurrent model, 324 stateful model, 324, 440 receive asynchronous, 332 nonblocking, 333 synchronous, 332 receive expression (in Erlang), 391 recomputation, 761, 776 record, 19, 52, 825 adjoin, 827 basic operations, 54, 826 dynamic creation, 165, 549, 695 importance, 53 type, 438 usage trade-offs, 438 recurrence equation, 167 recursion, 3, 113, 124 direct, 113 indirect, 113 mutual, 110 polymorphic, 309 programming with, 127 Prototyper tool, 690 tail recursion optimization, 72 red cut (in Prolog), 670 Red Hat Corporation, xxvi, 201, 471 reduction order, 330–332 applicative, 330 normal, 330 reduction rule, 784 reengineering, 522 refactoring, 452 reference, 714 referential transparency, 113 reflection, 515 region (in OPI), 815 register abstract machine, 56 forwarding, 621 memory management, 74 registration action procedures (in GUI), 683 display refresh (FlexClock), 700 distributed binding, 737 finalization, 481 relation, 655 relative error, 120 reliability, 711 rendezvous, 619 replicator, 326 research project, xxiv resolution deadlock, 605 logic programming, 635, 640, 662 SLDNF, 662 video display, 321 resource distributed component, 746 distributed system, 729 external, 77, 480 file descriptor, 293 892 Index localized, 709 producer/consumer pipeline, 261 use of laziness, 289 responsibility atomicity and consistency (in transaction), 600 compartmentalize (in a team), 451 coroutine (avoiding starvation), 275 design by contract, 521 distributed memory management, 738 dynamic typing, 493 failure confinement, 245 memory management, 76 role of polymorphism, 425 type inference, 137 resting point, 338 restriction (environment), 62 retract/1 operation (in Prolog), 662 return (in for loop), 190 Reuter, Andreas, 582, 600 Reynolds, John C., 419 right, see name Rinard, Martin C., 338 RISC (Reduced Instruction Set Computer) microprocessor, 621 RMI (remote method invocation), 354, 709, 724, 725 root variable, 763 Round operation, 822 RPC (remote procedure call), 354, 709 rubber band, 251 runic inscription, 779 Runnable interface (in Java), 616 s-expression, 650 Sacks, Oliver, 405 safety, 602 Saint-Exupéry, Antoine de, 111 Santayana, George, 694 Saraswat, Vijay A., 338, 662, 808 scalability compilation, 458 multiprocessor, 710 program development, 105 weighted reference counting, 737 scalar product (constraint), 775 scheduler Delay operation, 304 deterministic, 253 lift control system, 366 nondeterministic, 253 randomness, 473 resource allocation, 672 round-robin, 252, 256 thread, 239, 252 transaction, 603 Schulte, Christian, xxvi science, xv, xviii scientific method, xvii scope, 56, 507 attribute, 510 dynamic, 59 lexical, 57, 59, 64, 508, 539 absence in Prolog, 661 distributed, 722 hiding, 221, 411, 423, 442, 483, 495, 549 substitution, 803 private, 507, 508 protected, 508 public, 507 static, see lexical user-defined, 508 search aggregate, 670 all-solutions, 626 binary, 151 branch-and-bound, 772 breadth-first, 644 communication from inside encapsulated search, 673 constraint programming, 274 contribution of AKL, 809 danger, 639 Index 893 database query, 657 depth-first, 622, 644 deterministic, 621 encapsulated, 625 generate-and-test, 629, 758 iterative deepening, 644 linear, 197 logic programming, 661 n-queens problem, 629 one-solution, 626 overuse, xxi propagate-and-search, 629, 750 pruning, 662 relational computation model, 623 relational programming, 621 saturation, 772 search space, 622 search strategy, 761 search tree, 624 security abstract data type, 201–210 application, 744 atom vs. name, 508 capability, 208 data abstraction, 419–435 distributed resources, 731 distributed system, 743 engineering, 744 hardware, 744 human society, 208 implementation, 744 kernel language concepts, 847 language, 208, 744 linguistic abstraction, 39 mechanism, 208 open distribution, 711 policy, 208 right, 791, 847 static typing, 106 threat model, 744 self clone, 517 delegation, 511 dynamic binding, 505 forwarding, 511 Java, 553 this notation, 551 self (in Erlang), 390 semantic stack, 62 runnable, 62 suspended, 62 terminated, 62 semantics, 31 abstract machine, 56–78, 92–94, 239–241, 282–283, 348–349, 416–417 axiomatic, 38, 440–450, 632 by-need trigger, 282 cell, 416 common abstractions, 808 denotational, 38 exceptions, 92 interleaving, 780 kernel language, see abstract machine kernel language approach, 38 logical, 38, 631–641 monitor (in Java), 592 operational, 38, 60, 635, 779–811 port, 348, 383 secure types, 203 semantic statement, 61 SOS (structural operational semantics), 779 thread, 239 Send operation, 349 slot-reserving semantics, 384 send asynchronous, 332 latency, 263 nonblocking, 333 synchronous, 332 Send-More-Money problem, 755, 776 separation of concerns, 567 sequential logic, 269 serializability, 600 serialization, 709 894 Index serializer, 325 set comprehension, 301 setof/3 operation (in Prolog), 626, 666, 670 Shakespeare, William, 815 shared-state concurrency, see atomic action, see lock, see monitor, see transaction sharing, 418 Browser tool, 102, 829 distributed state, 720 distributed value, 716 thread, 378 short-circuit concurrent composition, 277 Flavius Josephus problem, 559 transitive closure, 464 Show operation, 340 side effect, 411 declarative, 288 signal operation (in monitor), 592 signature (of procedure), 129 simulation components, 412 digital logic, 266–272 inadequacy of declarative model, 173 Internet, 412 multi-agent, 412 slow network, 578 small world, 486 word-of-mouth, 476 Simurgh, 707 single-assignment store, 42–49, 60, 781 importance, 43 singularity, 176 sink (consumer), 259 64-bit address, 78 64-bit word, 74, 175, 820 skip statement, 62, 785 SLDNF resolution, 662 small world graph, 461 simulation, 486 Smolka, Gert, xxvi snapshot (of state), 437, 718 software design, see design methodology, see language design software development, 218, 450 bottom-up, 451 compositional, 453 concurrent components, 362 distributed programming, 745 evolutionary, 451 extreme programming, 452 framework, 492 IID (Iterative and Incremental), 451 importance of names, 508 in the large, 450 in the small, 218 incremental, 451 interactive interface, 87 iterative, 451 middle-out, 451 stepwise refinement, 465, 604 test-driven, 452 top-down, 8, 451 software engineering, 450 component as unit of deployment, 221 concurrency, 233 distributed lexical scoping, 722 further reading, 462 informatics curriculum, xxii lexical scoping, 59 software rot, 459 Solaris operating system, xxvi, xxix Solve operation, 626, 773 SolveAll operation, 626 SolveOne operation, 626 Sort operation, 670, 829 SOS (structural operational semantics), 779 source (producer), 259 source code, 221 interactive, 815 Index 895 million line, xvi, 36, 387, 457, 458 nonexistent, 492 preprocessor input, 318 reengineering, 522 set of functors, 285 textual scope, 64 variable name, 44 space, see computation space, see memory space leak, see memory leak specification, 410 component, 461 specification language, 116 speculative execution (in nonstrict language), 331 stack declarative object, 423 depth-first traversal, 156 memory management, 74 open declarative, 195, 421 proving it correct, 442 secure declarative bundled, 423 secure declarative unbundled, 205, 422 secure stateful bundled, 424 secure stateful unbundled, 424 semantic, 61 stateful concurrent, 578 standalone application, 222 declare not allowed, 87 Java, 555 uncaught exception, 93 starvation, 275 wait set implementation, 597 state cell (mutable variable), 414 declarative, 408 explicit, 16, 409 implicit, 408 interaction with call by name, 485 lazy execution, 481 lazy language, 331 memory management, 77 modularity property, 315 nonstrict language, 331 port (communication channel), 347 reasoning with, 38, 440 revocable capability, 434 threading, 139 transformation, 133 state transition diagram, 353, 368 component design, 364 floor component, 369 lift component, 371 lift controller component, 369 transaction, 607 stateless (declarative programming), 111 statement case, 67, 790 catch (clause in try), 94 choice, 623, 772 conc, 278 declare, 2, 87 fail, 623 finally (clause in try), 94 for, 188 fun, 84 functor, 223 gate, 272 if, 66, 790 local, 56, 63, 786 lock, 22, 583 proc, 65, 792 raise, 93, 801 skip, 62, 785 thread, 241, 785 try, 92, 799 break, 486 compound, 117 compound (in Java), 552 declarative kernel language, 49 interactive, 87 procedure application, 66 sequential composition, 63, 785 suspendable, 65 896 Index value creation, 63 variable-variable binding, 63 static binding, 506 linking, 222 scope, see scope, lexical typing, 51, 104–106 stdin (standard input), 229, 553 stdout (standard output), 553 Steiner, Jennifer G., 334 Stirling’s formula for factorial, 618 storage manager, 325 store, 781 equivalence, 785 mutable (for cells), 416 mutable (for ports), 348 need, 780, 795 predicate, 781 read-only, 206, 798 single-assignment, 42–49, 60, 99, 235, 781 trigger, 282, 795 value, 43 stream, 795 deterministic, 257 Java, 553 merger, 395 producer/consumer, 257 usage trade-offs, 439 strict . . . , see eager . . . strict two-phase locking, 604 strictness analysis, 289, 310, 342 string, 53, 830 virtual, 211, 831 StringToAtom operation, 824 structure compiler, 162 compositional, 461 difference, 141 distribution, 255 effect of concurrency, 252 grammar, 32 hierarchical, 453 interpreter, 653 noncompositional, 461 program, 219, 220 structure equality, 103, 418, 723 substitution, 126, 803 substitution property, 518, 521, 523 subtype basic types, 52 class hierarchy, 518 Sun Microsystems, xxvi, 462 superclass, 503, 513, 556 supercomputer, 175 supply-driven execution, see eager execution suspension Delay operation, 305 due to program error, 48, 89 thread, 239, 276 Sussman, Gerald Jay, 42 Sussman, Julie, 42 Symbian Ltd., 378 symbolic link, 459 synchronization, 333–337 clock, 308 dataflow, 790 synchronized keyword, 593, 616 synchronous communication, 332 active object variant, 562 component interaction, 456 CSP, 619 dependency, 387 error reporting, 360 failure detection, 400, 739 fault confinement, 745 receive, 332 send, 332 synchronous programming, 266 syntactic sugar, 40, 79–84 dynamic record creation, 165 local statement, 40 state transition diagram, 369 syntax, 31 convention for examples, xxix language, 31 nestable constructs (in Oz), 833 Index 897 nestable declarations (in Oz), 833 Oz language, 833 Oz lexical, 839 Prolog, 663 term (in Oz), 833 synthesized argument, 161 system exception, 96 Szyperski, Clemens, 462 tail call optimization, 72 Tanenbaum, Andrew S., 334 task (in concurrency), 780 tautology, 632 TCP (Transmission Control Protocol), 712, 740 technology, xv dangers of concurrency, 21 history of computing, 176 magic, 314 molecular computing, 176 Prolog implementation, 661 reengineering, 522 singularity, 176 software component, 462 synchronous digital, 267 transition to 64-bit, 78 Tel, Gerard, 353 tell operation, 782, 787 temporal logic, 603 temporary failure, 739 term Erlang, 391 Oz, 833 Prolog, 664 termination detection, 276, 382 ping-pong example, 305 failure in declarative program, 245 partial, 243, 338, 804 proof, 449 total, 804 test-driven development, 452 testing declarative programs, 111, 407 dynamic typing, 105 programming in the small, 219 stateful programs, 407 text file, 210 Thalys high-speed train, 382 theorem binomial, 4 Church-Rosser, 331 Gödel’s completeness, 634 Gödel’s incompleteness, 634 halting problem, 681 theorem prover, 117, 634, 662 Therac-25 scandal, 21 thinking machine, 621 third-party independence, 335 32-bit address, 78 32-bit word, 74, 174 this, see self Thompson, D’Arcy Wentworth, 405 thread, 846 declarative model, 233 hanging, 399 interactive interface, 89 introduction, 15 Java, 615 monotonicity property, 239, 781, 782 priority, 253 ready, 239 runnable, 239 suspended, 239 synchronization, 333 thread statement, 241, 785 Thread class (in Java), 616 throughput, 263 thunk, 432 ticket, 480, 714 Connection module, 715 ticking, 307 time complexity, 11 time slice, 252–254 duration, 254 898 Index time-lease mechanism, 480, 734, 738 time-out, 740 Erlang, 391–394 system design, 460 timer protocol, 368 timestamp, 207, 602 timing measurement active object, 379 memory consumption, 173 palindrome product (constraint version), 758 palindrome product (naive version), 629 transitive closure, 471 word frequency, 201 token equality, 418, 714, 723 token passing, 579, 588, 591, 721 token syntax (of Oz), 833 tokenizer, 32, 162 top-down software development, 8, 451 total termination, 804 trade-off asynchronous communication vs. fault confinement, 745 compilation time vs. execution efficiency, 457 compositional vs. noncompositional design, 461 dynamic vs. static scoping, 58 dynamic vs. static typing, 104 explicit state vs. implicit state, 315, 409 expressiveness vs. execution efficiency, 116 expressiveness vs. manipulability, 681 functional decomposition vs. type decomposition, 542 helper procedure placement, 120 indexed collections, 435 inheritance vs. component composition, 462, 492 kernel language design, 844 language design, 811 lazy vs. eager execution, 329 memory use vs. execution speed, 177 names vs. atoms, 510 nonstrictness vs. explicit state, 331, 344 objects vs.


pages: 120 words: 17,504

Data Structures & Algorithms Interview Questions You'll Most Likely Be Asked by Vibrant Publishers

NP-complete, sorting algorithm, traveling salesman

Give examples of problems solved using greedy algorithms. Answer: A greedy algorithm is any algorithm that makes the local optimal choice at each stage with the hope of finding the global optimum. A classical problem which can be solved using a greedy strategy is the traveling salesman problem. Another problems that can be solved using greedy algorithms are the graph coloring problem and all the NP-complete problems. 164: Which are the pillars of a greedy algorithm? Answer: In general, greedy algorithms have five pillars: a) a candidate set, from which a solution is created b) a selection function, which chooses the best candidate to be added to the solution c) a feasibility function, that is used to determine if a candidate can be used to contribute to a solution d) an objective function, which assigns a value to a solution, or a partial solution e) a solution function, which will indicate when we have discovered a complete solution 165: What is a backtracking algorithm?


pages: 828 words: 205,338

Write Great Code, Volume 2 by Randall Hyde

complexity theory, Donald Knuth, G4S, locality of reference, NP-complete, premature optimization

For this reason, the optimization process is usually a case of compromise management, where you make tradeoffs and sacrifice certain subgoals (for example, running certain sections of the code a little slower) in order to create a reasonable result (for example, creating a program that doesn’t consume too much memory). 5.4.4.2 Optimization’s Effect on Compile Time You might think that it’s possible to choose a single goal (for example, highest possible performance) and optimize strictly for that. However, the compiler must also be capable of producing an executable result in a reasonable amount of time. The optimization process is an example of what complexity theory calls an NP-complete problem. These are problems that are, as far as we know, intractable. That is, a guaranteed correct result cannot be produced (for example, an optimal version of a program) without computing all possibilities and choosing the best result from those possibilities. Unfortunately, the time generally required to solve an NP-complete problem increases exponentially with the size of the input, which in the case of compiler optimization means roughly the number of lines of source code. This means that in the worst case, producing a truly optimal program would take longer than it was worth.

Natural offsets in an activation record, 16.5.2 Assigning Offsets to Local Variables Nested procedures, 8.5.3 Storage Allocation for Intermediate Variables new (memory allocation), 8.1.4 The Stack Section, 8.3.2 Pseudo-Static Binding and Automatic Variables, 8.3.3 Dynamic Binding and Dynamic Variables, 11.2 Pointer Implementation in High-Level Languages, 11.2 Pointer Implementation in High-Level Languages function, 8.3.3 Dynamic Binding and Dynamic Variables, 11.2 Pointer Implementation in High-Level Languages operator (C++ or Pascal), 8.1.4 The Stack Section next statement, 14.3 The goto Statement NIL, 14.5.3 Forcing Short-Circuit Boolean Evaluation in an if Statement Nodes in a call tree, 16.1.2 Other Sources of Overhead Non-numeric constants, 7.4 Manifest Constants Versus Read-Only Memory Objects Nonportable optimizations, 6.1 Background Nonscalar function return results, 16.6.2 Pass-by-Reference NOT operator, 15.2 The repeat..until (do..until/do..while) Loop NP-complete problems, 5.4.4 Optimization NULL pointer references, 8.1 Runtime Memory Organization NumberOfLinenumbers field in a COFF file, 5.6.3 COFF Section Headers NumberOfRelocations field in a COFF file, 5.6.3 COFF Section Headers NumberOfSections field in a COFF file, 5.6.1 The COFF File Header, 5.6.2 The COFF Optional Header Numeric constants, 3.4 Literal Constants O objdump, 5.8.4 Section Alignment and Library Modules, 6.3.1.3 The dumpbin.exe /headers Command-Line Option, 6.3.1.6 Other dumpbin.exe Command-Line Options, 6.3.2 The FSF/GNU objdump.exe Utility command-line options, 6.3.1.6 Other dumpbin.exe Command-Line Options utility, 5.8.4 Section Alignment and Library Modules, 6.3.1.3 The dumpbin.exe /headers Command-Line Option for GNU/Gas/GCC code, 6.3.1.3 The dumpbin.exe /headers Command-Line Option Object code files, Compiler Operation and Code Generation Object files, 5.4.4.5 Controlling Compiler Optimization, 5.5.2 Emitting Assembly Language as Compiler Output, 5.6.7 Learning More About Object File Formats, 5.7.1 Pages, Segments, and File Size as compiler output, 5.5.2 Emitting Assembly Language as Compiler Output formats, 5.6.7 Learning More About Object File Formats sections and memory consumption, 5.7.1 Pages, Segments, and File Size Object-oriented programs, overgeneralization in, 12.8.7 Classes, Objects, and Performance Objects, 12.7 Namespaces One-address machines, 13.1.2 Accumulator-Based Machines Operand sizes in assembly language, 3.8 Specifying Operand Sizes in Assembly Language, 3.8.1 Type Coercion in HLA, 4.9 The Minimal Instruction Set ambiguity (80x86), 3.8.1 Type Coercion in HLA on the PowerPC, 4.9 The Minimal Instruction Set operating system.

, 80x86 Assembly for the HLL Programmer, 3.4 Literal Constants, 3.4.3.2 Hexadecimal Literal Constants in Gas, 3.4.4.2 Character and String Literal Constants in Gas, 3.4.4.2 Character and String Literal Constants in Gas, 3.4.5 Floating-Point Literal Constants, 3.5.2 Manifest Constants in Gas, 3.5.2 Manifest Constants in Gas, 3.5.2 Manifest Constants in Gas, 3.6.1.1 Register Access in HLA, 3.6.1.3 Register Access in MASM and TASM, 3.6.2 Immediate Addressing Mode, 3.6.2 Immediate Addressing Mode, 3.6.4 Register Indirect Addressing Mode, 3.6.5.2 Indexed Addressing Mode in MASM and TASM, 3.6.6.1 Scaled-Indexed Addressing in HLA, 3.7.2 Data Declarations in MASM and TASM, 3.7.2 Data Declarations in MASM and TASM, 3.7.2 Data Declarations in MASM and TASM, 3.7.3 Data Declarations in Gas, 3.7.3 Data Declarations in Gas, 3.7.3.1 Accessing Byte Variables in Assembly Language, 3.8 Specifying Operand Sizes in Assembly Language, 3.8.1 Type Coercion in HLA, 6.2.1 Assembly Output from GNU and Borland Compilers, 6.2.3.2 Borland C++ Assembly Language Output, 8.5 Variable Addresses and High-level Languages = operator, 3.5.2 Manifest Constants in Gas binary constants, 3.4 Literal Constants character literal constants, 3.4.4.2 Character and String Literal Constants in Gas compatible assembly output from Borland C++, 6.2.3.2 Borland C++ Assembly Language Output constant declarations, 3.5.2 Manifest Constants in Gas data declarations, 3.7.2 Data Declarations in MASM and TASM db declarations, 3.7.2 Data Declarations in MASM and TASM dd/dword declarations, 3.7.3.1 Accessing Byte Variables in Assembly Language direct addressing mode, 3.6.2 Immediate Addressing Mode displacement-only addressing mode, 3.6.2 Immediate Addressing Mode, 8.5 Variable Addresses and High-level Languages dw declaration, 3.7.3 Data Declarations in Gas equ directive, 3.5.2 Manifest Constants in Gas floating-point literal constants, 3.4.5 Floating-Point Literal Constants hexadecimal literal constants, 3.4.3.2 Hexadecimal Literal Constants in Gas indexed addressing mode, 3.6.5.2 Indexed Addressing Mode in MASM and TASM initialized data, 3.7.2 Data Declarations in MASM and TASM mov instruction, 3.6.1.1 Register Access in HLA operand sizes, 3.8 Specifying Operand Sizes in Assembly Language register indirect addressing mode, 3.6.4 Register Indirect Addressing Mode register names, 3.6.1.3 Register Access in MASM and TASM scaled-indexed addressing modes, 3.6.6.1 Scaled-Indexed Addressing in HLA string literal constants, 3.4.4.2 Character and String Literal Constants in Gas type coercion, 3.8.1 Type Coercion in HLA word declaration, 3.7.3 Data Declarations in Gas TBL register (PowerPC), 4.3.3.3 XER Register TBU register (PowerPC), 4.3.3.3 XER Register TByte data (80x86), 3.7 Declaring Data in Assembly Language Tested code, 1.8 Characteristics of Great Code Text sections in an executable file, 5.7 Executable File Formats Textual substitution for parameters, 16.3 Macros and Inline Functions text_start field in a COFF file, 5.6.2 The COFF Optional Header Thread-safe code, 8.3.2 Pseudo-Static Binding and Automatic Variables Three-address architectures, 13.1.5 Three-Address Architectures Three-dimensional array access, 9.1.5.5 Accessing Elements of a Multidimensional Array Time Base facility (TBR) registers (PowerPC), 4.3 Basic PowerPC Architecture Time Base registers (TBL and TBU) (PowerPC), 4.3.3.3 XER Register Time required to optimize a program (NP-Completeness), 5.4.4 Optimization Time/space trade-off for macros, 16.3 Macros and Inline Functions TimeDateStamp (Windows COFF header field), 5.6.1 The COFF File Header Tokens, Compiler Operation and Code Generation, Compiler Operation and Code Generation, 5.4.1 Lexical Analysis and Tokens, 5.4.1 Lexical Analysis and Tokens, 5.4.1 Lexical Analysis and Tokens, 5.4.1 Lexical Analysis and Tokens attributes, 5.4.1 Lexical Analysis and Tokens composition, 5.4.1 Lexical Analysis and Tokens in a source file, Compiler Operation and Code Generation representing a source file, Compiler Operation and Code Generation streams, 5.4.1 Lexical Analysis and Tokens Top-of-stack, 13.1.1.1 Basic Stack Machine Organization, 13.1.1.3 Popping Data from a Stack Tracking changes to variables through a basic block, 5.4.4.3 Basic Blocks, Reducible Code, and Optimization Tracking memory use in a heap manager, 11.7 The OS and Memory Allocation Transfer of control at the machine level, Control Structures and Programmatic Decisions Translation from source code to machine code, 5.3.3 Compilers True, 7.6 Boolean Constants tsize field in a COFF file, 5.6.2 The COFF Optional Header Tuples, 12.1 Records Turbo Assembler.


Toast by Stross, Charles

anthropic principle, Buckminster Fuller, cosmological principle, dark matter, double helix, Ernest Rutherford, Extropian, Francis Fukuyama: the end of history, glass ceiling, gravity well, Khyber Pass, Mars Rover, Mikhail Gorbachev, NP-complete, oil shale / tar sands, peak oil, performance metric, phenotype, plutocrats, Plutocrats, Ronald Reagan, Silicon Valley, slashdot, speech recognition, strong AI, traveling salesman, Turing test, urban renewal, Vernor Vinge, Whole Earth Review, Y2K

I was elbow-deep in an eviscerated PC, performing open heart surgery on a diseased network card, when the news about the traveling salesman theorem came in. Over on the other side of the office John’s terminal beeped, notification of incoming mail. A moment later my own workstation bonged. “Hey, Geoff! Get a load of this!” I carried on screwing the card back into its chassis. John is not a priority interrupt. “Someone’s come up with a proof that NP-complete problems lie in P! There’s a posting in comp.risks saying they’ve used it to find an O*(n2 ) solution to the traveling salesman problem, and it scales! Looks like April First has come early this year, doesn’t it?” I dropped the PC’s lid on the floor hastily and sat down at my workstation. Another cubed-sphere hypothesis, another flame war in the math newsgroups—or something more serious? “When did it arrive?”

Burgundy has gained a small reputation as an information buffer—a side-effect of its monarch’s paranoid attitude towards encroachment by other deities. It exports confidentiality, delay-line buffers, fine wines, and dissidents. In other words, it’s the last place a futures trader specializing in spread option trades that leverage developments in the artificial intelligence market—someone like me—would normally be seen dead in. On the other hand . . . As an accountant specializing in Monte Carlo solutions to NP-complete low-knowledge systems I am naturally of interest to the Queen, who made me an offer I would have considered long and hard at the best of times; in my circumstances back on Dordogne—exposed to risk, to say the least—I could hardly consider refusing her invitation. Many technologies are banned from the system, in an attempt to reduce the vulnerability of the monarchy to algorithmic complexity attacks.


pages: 541 words: 109,698

Mining the Social Web: Finding Needles in the Social Haystack by Matthew A. Russell

Climategate, cloud computing, crowdsourcing, en.wikipedia.org, fault tolerance, Firefox, full text search, Georg Cantor, Google Earth, information retrieval, Mark Zuckerberg, natural language processing, NP-complete, Saturday Night Live, semantic web, Silicon Valley, slashdot, social graph, social web, statistical model, Steve Jobs, supply-chain management, text mining, traveling salesman, Turing test, web application

A maximal clique, on the other hand, is one that is not a subgraph of another clique. The maximum clique is also a maximal clique in that it isn’t a subgraph of any other clique. However, various other maximal cliques often exist in graphs and need not necessarily share any nodes with the maximum clique. Figure 4-2, for example, illustrates a maximum clique of size 4, but there are several other maximal cliques of size 3 in the graph as well. Finding cliques is an NP-complete problem (implying an exponential runtime), but NetworkX does provide the find_cliques method, which delivers a solid implementation that takes care of the heavy lifting. Just be advised that it might take a long time to run as graphs get beyond a reasonably small size. Figure 4-2. An example graph containing a maximum clique of size 4 Example 4-11 could be modified in any number of ways to compute interesting things, so long as you’ve first harvested the necessary friendship information.

Assuming you’ve first constructed a graph as demonstrated in the previous section, it shows you how to use some of the NetworkX APIs for finding and analyzing cliques. Example 4-11. Using NetworkX to find cliques in graphs (friends_followers__clique_analysis.py) # -*- coding: utf-8 -*- import sys import json import networkx as nx G = sys.argv[1] g = nx.read_gpickle(G) # Finding cliques is a hard problem, so this could # take awhile for large graphs. # See http://en.wikipedia.org/wiki/NP-complete and # http://en.wikipedia.org/wiki/Clique_problem cliques = [c for c in nx.find_cliques(g)] num_cliques = len(cliques) clique_sizes = [len(c) for c in cliques] max_clique_size = max(clique_sizes) avg_clique_size = sum(clique_sizes) / num_cliques max_cliques = [c for c in cliques if len(c) == max_clique_size] num_max_cliques = len(max_cliques) max_clique_sets = [set(c) for c in max_cliques] people_in_every_max_clique = list(reduce(lambda x, y: x.intersection(y), max_clique_sets)) print 'Num cliques:', num_cliques print 'Avg clique size:', avg_clique_size print 'Max clique size:', max_clique_size print 'Num max cliques:', num_max_cliques print print 'People in all max cliques:' print json.dumps(people_in_every_max_clique, indent=4) print print 'Max cliques:' print json.dumps(max_cliques, indent=4) Sample output from the script follows for Tim O’Reilly’s 600+ friendships and reveals some interesting insights.


Mining of Massive Datasets by Jure Leskovec, Anand Rajaraman, Jeffrey David Ullman

cloud computing, crowdsourcing, en.wikipedia.org, first-price auction, G4S, information retrieval, John Snow's cholera map, Netflix Prize, NP-complete, PageRank, pattern recognition, random walk, recommendation engine, second-price auction, sentiment analysis, social graph, statistical model, web application

Interestingly, the technique for doing this search on a large graph involves finding large frequent itemsets, as was discussed in Chapter 6. 10.3.1Finding Cliques Our first thought about how we could find sets of nodes with many edges between them is to start by finding a large clique (a set of nodes with edges between any two of them). However, that task is not easy. Not only is finding maximal cliques NP-complete, but it is among the hardest of the NP-complete problems in the sense that even approximating the maximal clique is hard. Further, it is possible to have a set of nodes with almost all edges between them, and yet have only relatively small cliques. EXAMPLE 10.10Suppose our graph has nodes numbered 1, 2, . . . , n and there is an edge between two nodes i and j unless i and j have the same remainder when divided by k.

., 226 Near-neighbor search, see Locality-sensitive hashing Nearest neighbor, 17, 419, 447, 455 Negative border, 218 Negative example, 423 Neighbor, 357 Neighborhood, 367, 375 Neighborhood profile, 367 Netflix challenge, 2, 295, 321 Network, see Social network Neural net, 419 Newman, M.E.J., 382 Newspaper articles, 109, 286, 296 Non-Euclidean distance, 238, see also Cosine distance, see also Edit distance, see also Hamming distance, see also Jaccard distance Non-Euclidean space, 252, 254 Norm, 87, 88 Normal distribution, 244 Normalization, 305, 307, 318 Normalized cut, 344 NP-complete problem, 338 Numerical feature, 416, 455 O’Callaghan, L., 265 Off-line algorithm, 270 Olston, C., 67 Omiecinski, E., 226 On-line advertising, see Advertising On-line algorithm, 16, 270 On-line learning, 421 On-line retailer, 194, 268, 292, 294 Open directory, 174, 422 OR-construction, 95 Orr, G.B., 458 Orthogonal vectors, 231, 389 Orthonormal matrix, 397, 402 Orthonormal vectors, 389, 393 Out-component, 159 Outlier, 230 Output, 54 Overfitting, 303, 319, 419, 420, 432, 456 Overlapping Communities, 350 Overture, 276 Own pages, 178 Paepcke, A., 122 Page, L., 154, 190 PageRank, 3, 15, 28, 29, 40, 154, 156, 168 Pairs, see Frequent pairs Palmer, C.R., 383 Pan, J.


pages: 678 words: 159,840

The Debian Administrator's Handbook, Debian Wheezy From Discovery to Mastery by Raphaal Hertzog, Roland Mas

bash_history, Debian, distributed generation, do-ocracy, en.wikipedia.org, failed state, Firefox, GnuPG, Google Chrome, Jono Bacon, MITM: man-in-the-middle, NP-complete, QWERTY keyboard, RFC: Request For Comment, Richard Stallman, Skype, SpamAssassin, Valgrind, web application, zero day, Zimmermann PGP

With packages all depending upon each other, it is sometimes necessary to migrate a large number of packages simultaneously, which is impossible when some are uploading updates regularly. On the other hand, the script identifying the families of related packages works hard to create them (this would be an NP-complete problem, for which, fortunately, we know some good heuristics). This is why we can manually interact with and guide this script by suggesting groups of packages, or imposing the inclusion of certain packages in a group, even if this temporarily breaks some dependencies. This functionality is accessible to the Release Managers and their assistants. Recall that an NP-complete problem is of an exponential algorithmic complexity according to the size of the data, here being the length of the code (the number of figures) and the elements involved. The only way to resolve it is frequently to examine all possible configurations, which could require enormous means.


pages: 245 words: 12,162

In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation by William J. Cook

complexity theory, computer age, Computer Numeric Control, four colour theorem, index card, John von Neumann, linear programming, NP-complete, P = NP, p-value, RAND corporation, Richard Feynman, traveling salesman, Turing machine

Lenstra et al., eds. History of Mathematical Programming—A Collection of Personal Reminiscences. NorthHolland. 32–54. [11] Flood, M. 1954. Operations research and logistics. Proceedings of the First Ordnance Conference on Operations Research. Office of Ordnance Research, Durham, North Carolina. 3–32. [12] Garey, M. R., D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, California. [13] Gomory, R. E. 1966. The traveling salesman problem. Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems. IBM, White Plains, New York. 93–121. [14] Grötschel, M., O. Holland. 1991. Solution of large-scale symmetric travelling salesman problems. Mathematical Programming 51, 141–202. 224 Bibliography [15] Held, M., R. M. Karp. 1962.


The Art of Computer Programming by Donald Ervin Knuth

Brownian motion, complexity theory, correlation coefficient, Donald Knuth, Eratosthenes, G4S, Georg Cantor, information retrieval, Isaac Newton, iterative process, John von Neumann, Louis Pasteur, mandelbrot fractal, Menlo Park, NP-complete, P = NP, Paul Erdős, probability theory / Blaise Pascal / Pierre de Fermat, RAND corporation, random walk, sorting algorithm, Turing machine, Y2K

., bs are any addition chains, then J(]T djcubj) < r + 5 + ]T aj — 1 for any (r + 1) x E + 1) matrix of nonnegative integers dj. 41. [SICOMP 10 A981), 638-646.] The stated formula can be proved whenever A > 9m2. Since this is a polynomial in m, and since the problem of finding a minimum vertex cover is NP-hard (see Section 7.9), the problem of computing l(ni,..., nm) is NP-complete. [It is unknown whether or not the problem of computing l(n) is NP- complete. But it seems plausible that an optimum chain for, say, X^fcTcI ^fc+i2Afe2 would entail an optimum chain for {ni,... ,nm}, when A is sufficiently large.] SECTION 4.6.4 1. Set y «— x2, then compute ((... (u2n+iy + U2n-i)y + • • ¦ )y + U\)x. 2. Replacing x in B) by the polynomial x + xo leads to the following procedure: Gl. Do step G2 for k = n, n — 1, ..., 0 (in this order), and stop.

He has extended the results to multivariate polynomials in SICOMP 9 A980), 225-229. The tensor rank of an arbitrary m x n x 2 tensor in a suitably large field has been determined by Joseph Ja'Ja', SICOMP 8 A979), 443-462; JACM 27 A980), 822-830. See also his interesting discussion of commutative bilinear forms in SICOMP 9 A980), 713-728. However, the problem of computing the tensor rank of an arbitrary nxnx n tensor over any finite field is NP-complete [J. Hastad, Journal of Algorithms 11 A990), 644-654]. 4.6.4 EVALUATION OF POLYNOMIALS 515 For further reading. In this section we have barely scratched the surface of a very large subject in which many beautiful theories are emerging. Considerably more comprehensive treatments can be found in the books Computational Com- Complexity of Algebraic and Numeric Problems by A. Borodin and I. Munro (New York: American Elsevier, 1975); Polynomial and Matrix Computations 1 by D.

Normal distribution, 56, 122, 384, 565. tail of, 139. variations, 132, 139. Normal evaluation schemes, 506, 709-710. Normal numbers, 177. Normalization of divisors, 272-273, 282-283. Normalization of floating point numbers, 215-217, 227-228, 238, 248-249, 254, 616. Normand, Jean-Marie, 29. Norton, Graham Hilton, 372, 673. Norton, Karl Kenneth, 383. Norton, Victor Thane, Jr., 607. Notations, index to, 730-734. Nozaki, Akihiro (ff*§Hg3A), 524. NP-complete problems, 499, 514, 585, 698. Null space of a matrix, 443-444, 456, 659-660, 681. Number field sieve, 403. Number fields, 331, 333, 345, 403, 674. Number sentences, 605. Number system: A language for representing numbers. balanced binary, 213. balanced decimal, 211. balanced mixed-radix, 103, 293, 631. balanced ternary, 207-208, 209, 227, 283, 353. binary (radix 2), 195, 198-206, 209-213, 419, 461, 483. combinatorial, 209. complex, 205-206, 209-210, 292. decimal (= denary, radix ten), 197—199, 210, 320-326, 374. duodecimal (radix twelve), 199-200. factorial, 66, 209.


Algorithms in C++ Part 5: Graph Algorithms by Robert Sedgewick

Erdős number, linear programming, linked data, NP-complete, reversible computing, sorting algorithm, traveling salesman

Does the presence of cycles in a flow network make more difficult the task of computing a maxflow? We have seen many examples of digraph-processing problems that are much more difficult to solve in the presence of cycles. Perhaps the most prominent example is the shortest-paths problem in weighted digraphs with edge weights that could be negative (see Section 21.7), which is simple to solve in linear time if there are no cycles but NP-complete if cycles are allowed. But the maxflow problem, remarkably, is no easier for acyclic networks. Property 22.16 The maxflow problem for acyclic networks is equivalent to the standard maxflow problem. Proof: Again, we need only to show that the standard problem reduces to the acyclic problem. Given any network with V vertices and E edges, we construct a network with 2V +2 vertices and E +3V edges that is not just acyclic but has a simple structure.

Hell, “On the history of the minimum spanning tree problem,” Annals of the History of Computing, 7 (1985). D. B. Johnson, “Efficient shortest path algorithms,” Journal of the ACM, 24 (1977). D. E. Knuth, The Art of Computer Programming. Volume 1:Fundamental Algorithms, third edition, Addison-Wesley, 1997. J. R. Kruskal Jr., “On the shortest spanning subtree of a graph and the traveling salesman problem,” Proceedings AMS, 7, 1 (1956). K. Mehlhorn, Data Structures and Algorithms 2:NP-Completeness and Graph Algorithms, Springer-Verlag, 1984. C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982. R. C. Prim, “Shortest connection networks and some generalizations,” Bell System Technical Journal, 36 (1957). R. E. Tarjan, “Depth-first search and linear graph algorithms,” SIAM Journal on Computing, 1, 2 (1972). R. E. Tarjan, Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.


A Natural History of Beer by Rob DeSalle

agricultural Revolution, British Empire, double helix, Drosophila, Louis Pasteur, microbiome, NP-complete, phenotype, placebo effect, wikimedia commons

This is a tough question, because if we choose an outgroup that is too far away (milk, say), the root of the tree will become random and meaningless, and if we choose an outgroup from within the beers (barleywine, for instance), we will run the risk of artificially rooting the tree next to it. As a compromise, we tried rooting our tree with two relatively closely related beverages, gruit and wine. Next, as already mentioned, came the sheer computational difficulty that is involved in evaluating 10100 different trees. Computing the solutions for so many trees poses what mathematicians and computer scientists call an NP-complete problem: even though we know there is a finite solution to the problem, we don’t have the computing power to find it, so we must seek another road. In other words, with this many trees to examine we need to use shortcut methods that eliminate large swaths of those trees that will definitely not be part of the solution. One shortcut method of rooting the tree would be simply to interpose a root between the two larger groups of beers (say, lagers and ales) into which all the other beers are thought to fall.


pages: 571 words: 105,054

Advances in Financial Machine Learning by Marcos Lopez de Prado

algorithmic trading, Amazon Web Services, asset allocation, backtesting, bioinformatics, Brownian motion, business process, Claude Shannon: information theory, cloud computing, complexity theory, correlation coefficient, correlation does not imply causation, diversification, diversified portfolio, en.wikipedia.org, fixed income, Flash crash, G4S, implied volatility, information asymmetry, latency arbitrage, margin call, market fragmentation, market microstructure, martingale, NP-complete, P = NP, p-value, paper trading, pattern recognition, performance metric, profit maximization, quantitative trading / quantitative finance, RAND corporation, random walk, risk-adjusted returns, risk/return, selection bias, Sharpe ratio, short selling, Silicon Valley, smart cities, smart meter, statistical arbitrage, statistical model, stochastic process, survivorship bias, transaction costs, traveling salesman

Snippet 21.3 Evaluating all trajectories Note that this procedure selects an globally optimal trajectory without relying on convex optimization. A solution will be found even if the covariance matrices are ill-conditioned, transaction cost functions are non-continuous, etc. The price we pay for this generality is that calculating the solution is extremely computationally intensive. Indeed, evaluating all trajectories is similar to the traveling-salesman problem. Digital computers are inadequate for this sort of NP-complete or NP-hard problems; however, quantum computers have the advantage of evaluating multiple solutions at once, thanks to the property of linear superposition. The approach presented in this chapter set the foundation for Rosenberg et al. [2016], which solved the optimal trading trajectory problem using a quantum annealer. The same logic can be applied to a wide range on financial problems involving path dependency, such as a trading trajectory.


RDF Database Systems: Triples Storage and SPARQL Query Processing by Olivier Cure, Guillaume Blin

Amazon Web Services, bioinformatics, business intelligence, cloud computing, database schema, fault tolerance, full text search, information retrieval, Internet Archive, Internet of things, linked data, NP-complete, peer-to-peer, performance metric, random walk, recommendation engine, RFID, semantic web, Silicon Valley, social intelligence, software as a service, SPARQL, web application

All these DL names define a given language with a set of constructors, such as conjunctions, disjunctions, negations, quantifiers, cardinalities, etc. These languages are also characterized by complexities for a set of selected reasoning problems. For example, with DLs like ALC (considered the Storage and Indexing of RDF Data first DL of interest due to its set of constructors) or SHIQ, the combined complexities of CQ answering are respectively Exptime-complete and 2-ExpTime-complete and NP-complete for data complexity. Besides these high complexities, some lightweight DLs have been identified with polynomial complexity for CQ answering. The DL-Lite family is one of them and it motivated the creation of the OWL2QL recommendation. The basic DL-Lite logic provides key conceptual modeling constructs like concept inclusion and disjointness, as well as domain and range constraints; other DL-Lite logics support functionality constraints, property inclusion and disjointness, and data types.


pages: 404 words: 113,514

Atrocity Archives by Stross, Charles

airport security, anthropic principle, Berlin Wall, brain emulation, British Empire, Buckminster Fuller, defense in depth, disintermediation, experimental subject, glass ceiling, haute cuisine, hypertext link, Khyber Pass, mandelbrot fractal, Menlo Park, MITM: man-in-the-middle, NP-complete, the medium is the message, Y2K, yield curve

Anyway, the theorem has been rediscovered periodically ever since; it has also been suppressed efficiently, if a little bit less violently, because nobody wants it out in the open where Joe Random Cypherpunk can smear it across the Internet. The theorem is a hack on discrete number theory that simultaneously disproves the Church-Turing hypothesis (wave if you understood that) and worse, permits NP-complete problems to be converted into P-complete ones. This has several consequences, starting with screwing over most cryptography algorithms--translation: all your bank account are belong to us--and ending with the ability to computationally generate a Dho-Nha geometry curve in real time. This latter item is just slightly less dangerous than allowing nerds with laptops to wave a magic wand and turn them into hydrogen bombs at will.


Entangled Life: How Fungi Make Our Worlds, Change Our Minds & Shape Our Futures by Merlin Sheldrake

biofilm, buy low sell high, carbon footprint, crowdsourcing, cuban missile crisis, dark matter, discovery of penicillin, experimental subject, Fellow of the Royal Society, Isaac Newton, Kickstarter, late capitalism, low earth orbit, Mason jar, meta analysis, meta-analysis, microbiome, moral panic, NP-complete, phenotype, randomized controlled trial, Ronald Reagan, the built environment, Thomas Bayes, Thomas Malthus, traveling salesman

Valles-Colomer M, Falony G, Darzi Y, Tigchelaar EF, Wang J, Tito RY, Schiweck C, Kurilshikov A, Joossens M, Wijmenga C, et al. 2019. The neuroactive potential of the human gut microbiota in quality of life and depression. Nature Microbiology: 623–32. van Delft FC, Ipolitti G, Nicolau DV, Perumal A, Kašpar O, Kheireddine S, Wachsmann-Hogiu S, Nicolau DV. 2018. Something has to give: scaling combinatorial computing by biological agents exploring physical networks encoding NP-complete problems. Journal of the Royal Society Interface Focus 8: 20180034. van der Heijden MG. 2016. Underground networking. Science 352: 290–91. van der Heijden MG, Bardgett RD, Straalen NM. 2008. The unseen majority: soil microbes as drivers of plant diversity and productivity in terrestrial ecosystems. Ecology Letters 11: 296–310. van der Heijden MG, Dombrowski N, Schlaeppi K. 2017. Continuum of root-fungal symbioses for plant nutrition.


pages: 1,737 words: 491,616

Rationality: From AI to Zombies by Eliezer Yudkowsky

Albert Einstein, Alfred Russel Wallace, anthropic principle, anti-pattern, anti-work, Arthur Eddington, artificial general intelligence, availability heuristic, Bayesian statistics, Berlin Wall, Build a better mousetrap, Cass Sunstein, cellular automata, cognitive bias, cognitive dissonance, correlation does not imply causation, cosmological constant, creative destruction, Daniel Kahneman / Amos Tversky, dematerialisation, different worldview, discovery of DNA, Douglas Hofstadter, Drosophila, effective altruism, experimental subject, Extropian, friendly AI, fundamental attribution error, Gödel, Escher, Bach, hindsight bias, index card, index fund, Isaac Newton, John Conway, John von Neumann, Long Term Capital Management, Louis Pasteur, mental accounting, meta analysis, meta-analysis, money market fund, Nash equilibrium, Necker cube, NP-complete, P = NP, pattern recognition, Paul Graham, Peter Thiel, Pierre-Simon Laplace, placebo effect, planetary scale, prediction markets, random walk, Ray Kurzweil, reversible computing, Richard Feynman, risk tolerance, Rubik’s Cube, Saturday Night Live, Schrödinger's Cat, scientific mainstream, scientific worldview, sensible shoes, Silicon Valley, Silicon Valley startup, Singularitarianism, Solar eclipse in 1919, speech recognition, statistical model, Steven Pinker, strong AI, technological singularity, The Bell Curve by Richard Herrnstein and Charles Murray, the map is not the territory, the scientific method, Turing complete, Turing machine, ultimatum game, X Prize, Y Combinator, zero-sum game

If you limit yourself to simple Boolean propositions of the form ((A or B or C) and (B or ¬C or D) and (D or ¬A or ¬C)…), conjunctions of disjunctions of three variables, then this is a very famous problem called 3-SAT, which is one of the first problems ever to be proven NP-complete. So just because you don’t see a contradiction in the Zombie World at first glance, it doesn’t mean that no contradiction is there. It’s like not seeing a contradiction in the Riemann Hypothesis at first glance. From conceptual possibility (“I don’t see a problem”) to logical possibility, in the full technical sense, is a very great leap. It’s easy to make it an NP-complete leap, and with first-order theories you can make it arbitrarily hard to compute even for finite questions. And it’s logical possibility of the Zombie World, not conceptual possibility, that is needed to suppose that a logically omniscient mind could know the positions of all the atoms in the universe, and yet need to be told as an additional non-entailed fact that we have inner listeners.

Chalmers, The Conscious Mind. 222 Zombie Responses I’m a bit tired today, having stayed up until 3 a.m. writing yesterday’s >6,000-word essay on zombies, so today I’ll just reply to Richard, and tie up a loose end I spotted the next day. (A) Richard Chappell writes: A terminological note (to avoid unnecessary confusion): what you call “conceivable,” others of us would merely call “apparently conceivable.” The gap between “I don’t see a contradiction yet” and “this is logically possible” is so huge (it’s NP-complete even in some simple-seeming cases) that you really should have two different words. As the zombie argument is boosted to the extent that this huge gap can be swept under the rug of minor terminological differences, I really think it would be a good idea to say “conceivable” versus “logically possible” or maybe even have a still more visible distinction. I can’t choose professional terminology that has already been established, but in a case like this, I might seriously refuse to use it.


The Art of Computer Programming: Sorting and Searching by Donald Ervin Knuth

card file, Claude Shannon: information theory, complexity theory, correlation coefficient, Donald Knuth, double entry bookkeeping, Eratosthenes, Fermat's Last Theorem, G4S, information retrieval, iterative process, John von Neumann, linked data, locality of reference, Menlo Park, Norbert Wiener, NP-complete, p-value, Paul Erdős, RAND corporation, refrigerator car, sorting algorithm, Vilfredo Pareto, Yogi Berra, Zipf's Law

[N—t — 1:N — t], where t = mn + n + 1. a) Describe all inputs (xq, x\ ,..., xn) that are not sorted by such a network, in terms of the behavior of the special subnetwork. b) Given a set of clauses such as (yi V y^ V y-i) A (y2 V y3 V y^) A ..., explain how to construct a special subnetwork such that Fig. 61 sorts all inputs if and only if the clauses are unsatisfiable. [Hence the task of deciding whether a comparator sequence forms a sorting network is co-NP-complete, in the sense of Section 7.9.] 3.3.4 NETWORKS FOR SORTING 243 53. [30] (Periodic sorting networks.) The following two 16-networks illustrate general recursive constructions of t-level networks for n = 2* in the case t = 4: I tx (a) (b) If we number the input lines from 0 to 2* — 1, the Zth level in case (a) has comparators [i:j] where i mod 2t+1~l < 2t~l and j = i © Bt+1~l - 1); there are t2t~~1 comparators altogether, as in the bitonic merge.

Nikitin, Andrei Ivanovich (Hhkhthh, AHflpeH HBaHOBH^i), 351. Nitty-gritty, 317-343, 357-379. Nodine, Mark Howard, 698. Non-messing-up theorem, 90, 238, 669. Nondeterministic adversary, 219. Norlund, Niels Erik, 638. Normal deviate, 69. Normal distribution, approximately, 45, 650. Norwegian language, 520. Noshita, Kohei (IFTS ?), 213, 218. Notations, index to, 752-756. Novelli, Jean-Christophe, 614. NOW-Sort, 390. NP-complete problems, 242. Nsort, 390. Null permutation, 25, 36. Number-crunching computers, 175, 381, 389-390. Numerical instability, 41. Nyberg, Christopher, 390. Oberhettinger, Fritz, 131. Oblivious algorithms, 219-220. O'Connor, Daniel J., 225. Octrees, 565. INDEX AND GLOSSARY 771 j Odd-even merge, 223-226, 228, 230, J(l 243, 244. Odd-even transposition sort, 240. Odd permutations, 19, 196. Odell, Margaret K., 394.


pages: 574 words: 164,509

Superintelligence: Paths, Dangers, Strategies by Nick Bostrom

agricultural Revolution, AI winter, Albert Einstein, algorithmic trading, anthropic principle, anti-communist, artificial general intelligence, autonomous vehicles, barriers to entry, Bayesian statistics, bioinformatics, brain emulation, cloud computing, combinatorial explosion, computer vision, cosmological constant, dark matter, DARPA: Urban Challenge, data acquisition, delayed gratification, demographic transition, different worldview, Donald Knuth, Douglas Hofstadter, Drosophila, Elon Musk, en.wikipedia.org, endogenous growth, epigenetics, fear of failure, Flash crash, Flynn Effect, friendly AI, Gödel, Escher, Bach, income inequality, industrial robot, informal economy, information retrieval, interchangeable parts, iterative process, job automation, John Markoff, John von Neumann, knowledge worker, longitudinal study, Menlo Park, meta analysis, meta-analysis, mutually assured destruction, Nash equilibrium, Netflix Prize, new economy, Norbert Wiener, NP-complete, nuclear winter, optical character recognition, pattern recognition, performance metric, phenotype, prediction markets, price stability, principal–agent problem, race to the bottom, random walk, Ray Kurzweil, recommendation engine, reversible computing, social graph, speech recognition, Stanislav Petrov, statistical model, stem cell, Stephen Hawking, strong AI, superintelligent machines, supervolcano, technological singularity, technoutopianism, The Coming Technological Singularity, The Nature of the Firm, Thomas Kuhn: the structure of scientific revolutions, transaction costs, Turing machine, Vernor Vinge, Watson beat the top human players on Jeopardy!, World Values Survey, zero-sum game

is a televised game show with trivia questions about history, literature, sports, geography, pop culture, science, and other topics. Questions are presented in the form of clues, and often involve wordplay. Poker Varied Computer poker players remain slightly below the best humans for full-ring Texas hold ‘em but perform at a superhuman level in some poker variants.52 FreeCell Superhuman Heuristics evolved using genetic algorithms produce a solver for the solitaire game FreeCell (which in its generalized form is NP-complete) that is able to beat high-ranking human players.53 Go Very strong amateur level As of 2012, the Zen series of go-playing programs has reached rank 6 dan in fast games (the level of a very strong amateur player), using Monte Carlo tree search and machine learning techniques.54 Go-playing programs have been improving at a rate of about 1 dan/year in recent years. If this rate of improvement continues, they might beat the human world champion in about a decade.


pages: 721 words: 197,134

Data Mining: Concepts, Models, Methods, and Algorithms by Mehmed Kantardzić

Albert Einstein, bioinformatics, business cycle, business intelligence, business process, butter production in bangladesh, combinatorial explosion, computer vision, conceptual framework, correlation coefficient, correlation does not imply causation, data acquisition, discrete time, El Camino Real, fault tolerance, finite state, Gini coefficient, information retrieval, Internet Archive, inventory management, iterative process, knowledge worker, linked data, loose coupling, Menlo Park, natural language processing, Netflix Prize, NP-complete, PageRank, pattern recognition, peer-to-peer, phenotype, random walk, RFID, semantic web, speech recognition, statistical model, Telecommunications Act of 1996, telemarketer, text mining, traveling salesman, web application

For different tests, even for a different order of their application, different trees will be generated. Ideally, we would like to choose a test at each stage of sample-set splitting so that the final tree is small. Since we are looking for a compact decision tree that is consistent with the training set, why not explore all possible trees and select the simplest? Unfortunately, the problem of finding the smallest decision tree consistent with a training data set is NP-complete. Enumeration and analysis of all possible trees will cause a combinatorial explosion for any real-world problem. For example, for a small database with five attributes and only 20 training examples, the possible number of decision trees is greater than 106, depending on the number of different values for every attribute. Therefore, most decision tree-construction methods are non-backtracking, greedy algorithms.


pages: 496 words: 174,084

Masterminds of Programming: Conversations With the Creators of Major Programming Languages by Federico Biancuzzi, Shane Warden

Benevolent Dictator For Life (BDFL), business intelligence, business process, cellular automata, cloud computing, commoditize, complexity theory, conceptual framework, continuous integration, data acquisition, domain-specific language, Douglas Hofstadter, Fellow of the Royal Society, finite state, Firefox, follow your passion, Frank Gehry, general-purpose programming language, Guido van Rossum, HyperCard, information retrieval, iterative process, John von Neumann, Larry Wall, linear programming, loose coupling, Mars Rover, millennium bug, NP-complete, Paul Graham, performance metric, Perl 6, QWERTY keyboard, RAND corporation, randomized controlled trial, Renaissance Technologies, Ruby on Rails, Sapir-Whorf hypothesis, Silicon Valley, slashdot, software as a service, software patent, sorting algorithm, Steve Jobs, traveling salesman, Turing complete, type inference, Valgrind, Von Neumann architecture, web application

Brian maintained a log of major decisions we made as we designed the language. I found his log invaluable. Computer Science What constitutes research in computer science? Al: This is a wonderful question, and one that does not have a well-defined answer. I think computer science research has broadened enormously in its scope. We still have the deep, unsolved, quintessential questions of computer science: how do we prove that a problem like factoring or an NP-complete problem is actually hard; how do we model complex systems like a human cell or the human brain; how can we construct scalable, trustworthy systems; how can programmers build arbitrarily reliable software; how can we make software with human-friendly characteristics like emotion or intelligence; how far can we extend Moore’s Law? Today, the scale and scope of computing has exploded. We are trying to organize and access all of the world’s information, and computers and computation are affecting all areas of daily life.