Questions tagged [computer-science]

All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For questions from scientific computing, use (computational-mathematics).

Computer science is the study of the theory, experimentation, and engineering that form the basics for the design and use of computers. It is the scientific and practical approach to computation and its applications and the systematic study of the feasibility, structure, expression, and mechanization of the methodical procedures (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information. An alternate, more succinct definition of computer science is the study of automating algorithmic processes that scale.

Some fields of computer science such as computational complexity theory (which explores the fundamental properties of computational and intractable problems) are highly abstract, while fields such as computer graphics emphasize real-world visual applications.

5523 questions
1
vote
2 answers

theory behind semantics, RDF, OWL

What are the fields of mathematics related with semantics technologies and their specifications as RDF, OWL, SPARQL? If somebody working as a programmer with those technologies (using them with a practical scope and from a pragmatic point of view)…
1
vote
0 answers

Proving a greedy algorithm - find minimum number of terms in expression $n=a_1!+\cdots+a_k!$

Given a number $n$ (integer) I should find $a_1,\ldots,a_k$ such that $k$ is minimal and $n=a_1!+\cdots+a_k!$. I think that the following greedy algorithm should give the solution - iterating over $1!,\ldots,k!$ I find the biggest k such that…
qiubit
  • 2,313
1
vote
0 answers

How can I create/modify 3-SAT functions according to Valiant-Varizani?

The Valiant-Varizani Theorem is given here. I also liked the description/proof given here - it's fairly straightforward. I've read these works, and I'm still very shaky with constructing new hashed functions. I start with a 3-SAT function as a…
Matt Groff
  • 6,117
1
vote
1 answer

If L is decidable and acceptable, is L' (complementary language) not-acceptable?

I know that if L is decidable and L' is acceptable, than L is not-acceptable. Is it also true to say that if L is decidable and acceptable, than L' is not-acceptable? I'm sorry if this question sounds dumb, but I have a test on these stuff in 2 days…
Archer2486
1
vote
1 answer

Maximum variable string length $m$ needed to represent $n$ items using strings of size $1$ through $m$ with fixed alphabet size

Consider the following problem. You have a list containing $k$ total identifiers comprising $n$ unique identifiers such that $k \ge n$ (i.e. there can be duplicates). These identifiers are long strings, far longer than necessary to retain…
1
vote
0 answers

Two decidable languages for which a mapping reducibility does not exist?

The trivial null language might not be reduced to another language, but are there standard examples of two decidable languages $L_1$ and $L_2$ such that there is no mapping reduction possible from $L_1$ to $L_2$ or vice versa?
0
votes
1 answer

Question about greedy algorithms

Suppose I have a set of points on a plane and I want cover them in or on a circle of radius r. I want to minimize the number of circles I use. What would be an appropriate greedy approach to this problem? Personally, I would sort the points by x…
Mark
  • 3,109
0
votes
1 answer

Generalize diagonalization by using permutations

I am reading a textbook on computer science, and now the author explains a proof of existence of non-recursively enumerable language (he calls it $L_{diag}$) by diagonalization method, that is very reminiscent of Cantor's diagonalization and is the…
0
votes
2 answers

In general, what does the location of the rightmost “1” in a binary number tell you? Is it different for positive and for negative numbers?

In general, what does the location of the rightmost “1” in a binary number tell you? Is it different for positive and for negative numbers?
0
votes
1 answer

How many bits are needed to encode the following data?

A weather station on Santa Rosa Island sends data about weather conditions once every 15 minutes. The data sent is as follows: Temperature (0..60 degrees Celsius) Wind speed (0..170 kph) Wind direction (0..359 degrees from North) Humidity…
Brian
  • 1
0
votes
0 answers

Proving that there always exists two opposite points on a circle where the temperature difference is less than 1

You are given $n$ ($n$ is even) integers $a_0,a_1,\ldots,a_{n-1}$ representing temperature measurements, equally spaced around a circle. Since the points are "close", the temperature difference between two points next to each other is at most one.…
0
votes
1 answer

Fibonacci proof with a language

The proof I am working toward achieving is as follows: I know this can be proven using induction, and in doing so, I will need to: show when n = 2, F₂ = G₀; when n = 3, F₃ = G₁; if $F_{n -1} = G_{n - 3}$, then $F_n = G_{n - 2}$ for any $n >…
Jacob
  • 1
0
votes
2 answers

How to prove that for all 25 ppl and 4 groups, there is a group of at least 6 ppl from the same group?

As of Jun.17, I predict that Brazil, Germany, Italy, and Argentina will make it to the semi-finals of the FIFA World Cup. Suppose you have a group of 25 footballers from those four countries. Prove that out of those 25, there is a group of at least…
0
votes
2 answers

minmizing average problem

Given a set containing N numbers, minimize the average where you can take out any string of consecutive numbers in the set. |N|<=100000 Ex. {5, 1, 7, 8, 2} You can take out {1,7}, etc. but the way to minimize in this case is just to take out {7,8}…
user157920
  • 109
  • 6
0
votes
1 answer

Do sets require a general equivalence relation over all elements?

and does this mean there cant be sets of things I have not defined equivalency for? This is maybe a weird question and maybe not even a meaningful one, my understanding of sets and such is not complete, but it seems like "two sets are the same if…