Tag Info

23

Of course. The weight can mean things that are irrelevant to the existence of an edge. Since you don't ask for a "list of say 6 or 7 real-life examples", I will just add one. Consider a road network. If you want to find a path from A to B in a road network, you need to keep all the road segments that exist. There are two important measures: ...

20

I would like to say both you and that Berkeley tutorial are correct. As commented by chepner, the trees in Berkeley tutorial and the trees you thought are the same semantically; only the labels of the nodes are different. Every node in all figures represents a call to compute the corresponding Fibonacci number. The difference is that you prefer to use ...

12

The classic strategy game Civilization by MicroProse represents the world map as a square grid where each node of the grid is a tile of the world map, representing some type of terrain. Players control civilian and military units over this map. Each unit has a specific allocation of movement points, and each terrain type costs a specific amount of movement ...

8

In circuity, we often construct a graph of a circuit. Wires are typically modeled as 0 resistance because, frankly, measuring the resistance of wires is really tricky and rarely profitable. So if we have multiple devices connected to a single wire, we can treat that as separate vertices with 0 weight nodes between them. We can transform them into one "...

7

Your trees are showing the same thing; you are just labeling each node by the call, and the Berkeley tutorial is labeling each node by the result of that call. Compare the two pictures of fibtree(3), noting that: $F(0) = 0$ $F(1) = 1$ $F(2) = 1$ $F(3) = 2$ You'll see there's no disagreement at all. Perhaps it would be informative to see the tree "grow&...

6

The measure you are trying to minimize is called (directed) bandwidth. Finding a minimum directed bandwidth ordering is NP-hard.

4

"Decidable" and "effectively decidable" mean the same thing. I realize that's a bit confusing; but it reflects a difference in terminology between two communities. (Strictly speaking, I suspect there might be a difference between those two concepts if Church's thesis is false; but if Church's thesis is true, then they are equivalent.)

4

Such a graph does not need to represent an actual road network. It can be anything representable by a network. For example, conversion options between various online banking and cryptocurrency services. Most of them have a little or more fee, but sometimes you can do it for free (most likely, internal conversions by the same service, like sending cash from ...

3

Distances and times (and other units of measurement) Consider a graph where the edges are the driving distances between warehouses across the country. If two warehouses are on the same premises, they could potentially be given a distance of 0. Strictly speaking there might be some distance between them, but this may be considered negligible if the distance ...

3

An n-way set associative cache is a cache that is chopped up in sections called sets. And each set can hold n-blocks. A cache-address can be broken up up in 3 parts. the offset within the block the index that identifies the set the tag that identifies the block in the set. When a request comes in, the index is calculated to identify the set. Then the tags ...

2

I recently had the same question in mind when reading Pager's work. I found the paper The Edge-Pushing LR(k) Algorithm by Chen and Pager, which seems to say that the two terms are indeed the same. Quoting that paper: The concepts of state, configuration and theads(α, k) used here are equivalent to “item set”, “item” and FIRSTk(α) correspondingly in some ...

2

One possible direction is looking at the (computational) hardness of distributions. For example, a family of distributions $\{\mathcal{P}_n\}_{n\in\mathbb{N}}$ where $\mathcal{P}_n$ is a distribution over $\{0,1\}^n$ is called polynomialy-samplable (you can substitute here any other type of time/space restriction) if there exists a probabilistic polynomial ...

2

Given that this is an introduction, I wouldn't get too concerned about the wording. It's normal to describe things in general terms, and then go into specifics later. In a typical computer system, everything ultimately happens because some program running in the CPU made it happen. Even with external events such as interrupts (e.g. someone typed on a ...

2

The term first described by Horst Feistel (1973) As the input moves through successive layers the pattern of 1's generated is amplified and results in an unpredictable avalanche. It is rather very good naming. Consider a bit flip in the AES's input; It enters the first Sbox, then according to the design of the Sboxes of AES the output is different since ...

2

There is no standard term for this, as it's very language-specific whether your notion makes sense, or what it would mean exactly. For instance, Some languages have no undefined values, or no undefined values in arrays, or only undefined values for certain data types. For instance, in C, you can cast an arbitrary piece of memory to an array of integers and ...

2

A literal is not a variable. See https://en.wikipedia.org/wiki/Literal_(computer_programming). I wouldn't consider a literal a "built-in", but I'm not familiar with a precise formal definition of "built-in".

2

I think in the older literature there was a real distinction between job shop scheduling and multiprocessor scheduling. I tried to break down some of that distinction in an answer to a previous question about the distinction between job shop, flow shop, and open shop scheduling. Briefly: In job shop scheduling problems the resources are different from one ...

2

Sounds subjective to me. Data abstraction is not a black-and-white binary property; it is a matter of shades of grey. Any abstraction hides some information and reveals others. Another way to put it is that these two classes expose a different amount of functionality and make a different set of promises. So, what do you want the client to be aware of, and ...

2

The term and intuitive notion of a side effect of course predates functional programming. So your question is really, does the meaning of side effect in programming languages (i.e., a function which has effects beyond its input-output behavior) date back to functional programming? To this I think the answer is yes for trivial reasons, if "functional ...

2

$2^{\Sigma^{*}}$ means the powerset of the full language $\Sigma^{*}$. It means the set of all subsets of $\Sigma^{*}$, including the empty set and $\Sigma^{*}$ itself, i.e., all possible languages with alphabet $\Sigma$. Here is the simple understanding. When we want to describe a language $X$ with alphabet $\Sigma$, for each string $w$ in $\Sigma^{*}$, ...

2

Neural networks A neural network assigns weights to each connection between the simulated neurons. As you say, when calculating the output of the network, any edges with zero weight are equivalent to missing connections. However, the training step considers both the weight of the edge and the partial derivative of the output value with regards to the weight. ...

2

Not sure if this is a stretch for this question, but an NFA for the regex (xx)? is ϵ [Start] ─────→ [Accept] │ ↑ └───── xx ─────┘ It's not technically a number, but semantically the ϵ edge is a "null"-weighted edge: you can take it without incurring any "cost" (which in this case might be consumption of ...

1

An API is an Application Programming Interface. So it is intended for two progammmed component to communicate. It is not a Human-Machine Interface, hence does not involve a web page for communication. In your question, it could be a subprogram (in whatever variant or language) that can be called, with ingredients spécified in some way, possibly as parameters ...

1

In principle, a name is just a means for communication. You can use any terms and definitions you want as long as you and your audience both agree on the meaning of them and as long as it doesn't cause confusion. In practice, no, bits are not characters. The word "character" has an accepted definition and most people would probably find it ...

1

Vector has different meanings depending on the context. I would say that, in this case, the word vector is used because it enables "directing" the IRQs to the right handler. You could define vector to be the entry in the IVT that enables directing the IRQs. They are more like vectors of transmission or vectors that enable transmission rather than ...

1

The ability to "guess" is an informal but often helpful analogy on the NFA's capability to solve problems with much fewer states than the equivalent DFA would. I will demonstrate with an example. Let $L_n = \{ w \in \{a, b\}^* : \text{the } n\text{th-last character of } w \text{ is } a\}$. For example, $L_1$ is the language of strings with $a$ as ...

1

Linear (used the same way as in linear extensions) refers to the fact that the semantic model is an infinite "path" ("linear", if you will) without cycles; every state has a well-defined next element. There is a total ordering over the Kripke-structure (possible worlds). I.e. it refers to temporal.

1

In Computer Science, we don't really talk about "software". But we do talk about algorithms and models of computation, and also sometimes about computing machines. When we think about algorithms, there are two ways in which they can operate over either discrete or continuous domains: The algorithm can operate on discrete values (for example, ...

1

To answer the question If a Turing machine halts for all rejects of L but might accept/loop otherwise, how is L's recognizability classified? $L$ is Turing-unrecognizable, but $\overline{L}$ is Turing-recognizable. To see this, let $L=\overline{A_{TM}}$ and $\overline{L}=A_{TM}$, where \$A_{TM} = \{(M,w)|\space M \space \text{is a TM that accepts} \space w\}...

Only top voted, non community-wiki answers of a minimum length are eligible