Questions tagged [terminology]
Questions about how specific notions have to be understood as well as conventions of notation.
1,052
questions
2
votes
1answer
98 views
Explicit algorithms and algorithms involving unknowns
Let's assume the you have two algorithms for computing some single but complicated number (e.g., the Ramsey number $R(5,5)$). Both are provided as high-level, half-formal textbook descriptions.
The ...
3
votes
1answer
65 views
What is $C_4$ + two “ears” called?
A graph with $C_3$ + 3 "ears" is called a net graph.
In general, $C_n$ + $n$ pendant vertices are called sunlet graphs.
Is there a name for 4-sunlet graph minus two pendant vertices?
3
votes
3answers
3k views
Is there any difference between Time Complexity and Running time?
Is time complexity and running time of the program/algorithm one and the same thing?
Also, running time sounds like 'computer complexity'. As, it utilizes all the resources and give tangible time that ...
2
votes
1answer
210 views
Why is it called 'throwing' an exception?
I'm just wondering where the phrase "throwing" an exception came from. I understand "raising" an exception but I'm wondering if "throwing" has a reason or meaning behind it?
1
vote
2answers
46 views
How are lookup tables described from the perspective of complexity theory?
Lookup tables can convert a piece of computational time into space. I remember that it was a part of a complexity theory course, but I cannot recall how it's called in its terms. I know how to use ...
0
votes
0answers
25 views
What topics are related to “concept drift”?
The term "concept drift" specifically relates to a model changing over time. However, a similar phenomenon may manifest in, e.g., spatial data, where a topographical model changes behavior at a land/...
2
votes
0answers
150 views
Term for weak head normal forms that cannot be reduced in any environment
In my understanding, a lambda expression is a normal form (NF) when it has no redexes. For instance, $\lambda x.x$ is a NF, but $(\lambda x.x)y$ is not. A lambda expression is a weak head normal form (...
0
votes
0answers
517 views
What is the correct term for a probabilistically complete algorithm?
I'm wondering what the correct term for an algorithm that is probabilistically complete is. An algorithm is probabilistically complete if the probability of finding a solution, should a solution exist,...
1
vote
1answer
230 views
High Level Assemblers vs Compilers?
I'm reading the "Art of Assembly" 2nd Edition by Randall Hyde. In the book the author seems uses his own language called High Level Assembly (HLA). Coming from a C Background, I question how useful ...
2
votes
1answer
110 views
Do the classes $P$ and $NP$ include problems faster then polynomial?
I have being reading up on complexity classes (in Rieffel & Polak, 2011; pg149). I am slightly confused about something. Does for example $P$ (DTime($n^k$)) include all problems that can be solved ...
0
votes
1answer
32 views
A Question about what it means to Compare two Vectors
Please consider the following question:
Given an integer m by n matrix A and an integer m-vector b, the 0-1 integer programming problem asks whether there exists an integer n-vector x with elements in ...
0
votes
1answer
27 views
terminology: half adders, full adders
I'm very confused about the reasoning for these circuits being called 'full adders' and 'half adders'
I've read before that 'half adders' are called so, because two of them make up a 'full adder', ...
1
vote
2answers
572 views
Correct term for a priority queue with unique elements
Is there a standard term for a priority queue which can only hold a single occurrence of any element? This would be a priority queue for which operations such as "raise the priority of element ...
3
votes
1answer
966 views
What are the primal and dual planes in the context of the point-line duality?
In computational geometry, we can define a duality between points and lines. The line is the primal (or dual) object of a point, or a point is the primal (or dual) object of a line. However, the exact ...
1
vote
1answer
350 views
Bisimilarity and Trace Equivalence in Labelled Transition Systems
I'm a bit confused regarding the relation between trace equivalence and bisimilarity. These lecture notes I found and a few others documents I've read state that "if an LTS is deterministic then two ...
1
vote
2answers
83 views
Definition of InLeft and InRight
So in reading I have come across the terms "InLeft" and "InRight" and I am unable to find a concrete definition for it.
I have found it used in the specification for COQ, and in some notes on ...
4
votes
1answer
361 views
What is the name for a function's “return arity”?
The number of parameters a function has (and thus the number of arguments it can take) is known as arity. What is the name for the number of values a function returns? I'm not asking for the "size" of ...
1
vote
2answers
72 views
What mathematical terminology exists for “embellished trees”?
I'm looking for some pointers on proper mathematical (FP?, category-theory?) terminology.
My apologies if the below is somewhat imprecise; I suppose the precision is precisely what I'm looking for in ...
2
votes
0answers
888 views
Latency and Throughput Bounds
Say that I have a superscalar processor and I am given the latency, issue and capacity (in clock cycles) for different instructions.
What is the general formula for latency bound and throughput bound?...
6
votes
3answers
816 views
Why is the set for which a decision problem is true called a “language”?
When we have a decision problem, " does $f(x)=1$ hold?", we call the set of strings $x$ for which the answer is yes a "language".
Why this strange terminology?
1
vote
0answers
322 views
What's elementary operation in Computer science?
What do Computer Science mean when they use the Term Elementary Operations?
1
vote
0answers
22 views
Is there a term for mixing deferred and eager evaluation?
I've written a model which utilises deferred evaluation for many aspects of its feature but in one instance of its use it is mixed with threaded eager evaluation for things that are expected to be ...
2
votes
2answers
97 views
What is the name for the comparison used in C's memcmp?
The C memcmp function (and strcmp) does a comparison similar to the function below for comparing integers:
...
6
votes
1answer
588 views
What does the “big O complexity” of a function mean?
What do people mean when they refer to the "big O complexity" of a function? What is the big O complexity of $9n^2 + 10n$, for example?
2
votes
1answer
70 views
What do we call a greedy algorithm that tracks the best $n > 1$ solutions?
A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima.
To avoid this problem, we may keep track of the best $n > 1$ ...
12
votes
5answers
3k views
Why does soundness imply consistency?
I was reading the question Consistency and completeness imply soundness? and the first statement in it says:
I understand that soundness implies consistency.
Which I was quite puzzled about ...
83
votes
11answers
24k views
Why is the unit of image size not Pixel²?
If you calculate the area of a rectangle, you just multiply the height and the width and get back the unit squared.
Example:
5cm * 10cm = 50cm²
In contrast, if you calculate the size of an image, you ...
2
votes
1answer
159 views
Finite Automata: Final vs Accepting States
What is the difference between a final and accepting state when addressing an automaton?
As I understand it, a final state is depicted (traditionally) with a double circle, and apparently so is an ...
1
vote
2answers
32 views
Not quite-infinitely expandable human-friendly naming system?
This may be a known problem, with known approaches, but I can't find the right way to search for it.
I would like to name points along a line of unknown final length such that their name reflects ...
0
votes
1answer
308 views
What is the difference between a Standardization and a Specification?
While asking this question on "what exactly is standardization", I remebered that another related term that always came up while reading about C libraries was the term "specification".
To avoid asking ...
0
votes
3answers
1k views
What is standardization in computer science?
I was reading about the differences standards and specifications for C.
I understood that programming languages are usually stadardized and I learnt that there are different approches to ...
4
votes
1answer
2k views
What does synchronous and asynchronous mean in computer science?
Words synchronous and asynchronous can be met several times, in different contexts, when studying computer science. As an example :
Synchronous and asynchronous circuits.
Synchronous and asynchronous ...
1
vote
1answer
45 views
What is the computational complexity category of $T(n) = m^{\frac{n-1}{m}}$?
I'm analyzing the computational complexity of an algorithm whose input size is $n$. Finally, I've ended up with
$T(n) = {m^\frac{n-1}{m}}$ where $m$ is a constant. Can one explain the type name ...
2
votes
1answer
1k views
What is a ridge - Hill climbing
I do not understand what is a ridge for hill climbing. The definition I found is a place where all points appear like a maximum, but how is that different than a plateau?
0
votes
1answer
254 views
What us difference between distributed computing and workgroup computing?
According to the definition, distributed computing means to distributed a problem among different users while workgroup computing means to work on a problem by different users. So what's the ...
0
votes
1answer
3k views
Why must a Primary Index be sparse?
Reading Fundamentals of Database Systems 7th Edition, on Page 603, it says,
Indexes can also be characterized as dense or sparse. A dense index has an index entry for every search key value (and ...
5
votes
5answers
2k views
Why call it 'Time Complexity'?
P.S. I have added the tag 'history', if there is any historical connotation.
Also, I found this question What is running time of an algorithm? but I am not satisfied with answers.
2
votes
0answers
42 views
What is cyclomatic complexity and how relevant it is today? [closed]
I have read that cyclomatic complexity is widely used, but critique on it exists
claimed that it is based on poor theoretical foundations and an
inadequate model of software development.
I have read ...
0
votes
2answers
717 views
What does “effective enumeration” in Turing machines mean?
what is meant by EFFECTIVE ENUMERATION i have comes across this word when I was reading about enumerators for Turing machines is it same as LEXICOGRAPHIC ORDER?
so effective enumeration is possible ...
3
votes
2answers
265 views
What is “Containment order”? Could I get a friendly explanation?
Reading the Wikipedia page was a little dense for me. Can anyone offer a friendly explanation of what this means? It sounds like it saying that if you have two ordered collections, if they are "...
6
votes
1answer
345 views
What does “local” mean?
I study graph theory on my own using Diestel's Graph Theory book (with Algorithmic graph theory in mind). I don't understand what local property, global property, locality mean given a graph $G$.
...
6
votes
1answer
462 views
What is static complexity?
Definition : Kolmogorov complexity is a static complexity measure that captures the difficulty of describing a string.
For example, the string consisting of three million zeroes can be described with ...
8
votes
2answers
3k views
How do we define a tree in a directed graph?
I am trying to solve the exercise 3.3 in Approximation Algorithms by Vazirani, pg 34. It states
3.3 Give an approximation factor preserving reduction from the set cover
problem to the following ...
1
vote
0answers
138 views
What is the name for the recursion scheme in which data flows top-down exclusively?
This is a question that is in a sense a follow-up of a question I asked earlier, and which was answered.
In that question, the answer to "in which recursion scheme does data only flow bottom up, and ...
0
votes
2answers
289 views
Definition of “idempotence” of a function?
Currently there are two things that may change between invocations of a function: the return value, and the external states. I understand that if the external states changes, the function is not ...
6
votes
1answer
721 views
Reception of numerical infinities
A group of computer scientists associated with numerical analyst Yaroslav Sergeyev have published numerous publications recently on a scheme proposed by Sergeyev that uses terms like Infinity Computer,...
0
votes
0answers
38 views
Are the terms “Language Implementation”, “Runtime” and “Virtual Machine” synonymous?
To describe the implementation of a dynamic programming language, I have seen the terms "Runtime" (e.g. Security transparency in the Python runtime), "Virtual Machine" (Python Virtual Machine (PVM), ...
1
vote
1answer
113 views
size of a variable [closed]
I'm a beginner. I would like to know if the size of a variable (and generally speaking of a storage space) is:
Its capacity (the amount of data that can be put in it).
The amount of data it contains
0
votes
1answer
44 views
Is there a concept of information that distinguishes between “computed” and “non-computed” information?
I always tend to think of information as follows: If we have an information set $I$, and it is possible to derive from $I$ another information set $X$, then $I$ really contained $X$ all along, and we ...
1
vote
2answers
124 views
