Questions tagged [mathematical-foundations]

Questions about the relation of (subfields of) computer science to the relevant mathematical foundations and their application.

Filter by
Sorted by
Tagged with
0
votes
0answers
9 views

A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?

First of all I'm a Physics Student and I've been arguing with my brother concerning the usage and the fundamental meaning of a vector on Computer Science (CS). I) Vectors A vector have a axiomatic ...
0
votes
0answers
18 views

Mathematical expression for the quantity that we are maximising in the stock buying and selling problem

Problem Statement: Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$. Design an algorithm to find the maximum profit. You may complete as many ...
1
vote
1answer
41 views

What is the difference between a fraction and a float?

I understand any fraction to be a quotient of integers which isn't 0, but after coming across the term "float" in various programming languages (such as JavaScript) I misunderstand why it is ...
1
vote
1answer
36 views

How was the σ function chosen to extend the perceptron?

I am just reading about perceptrons in more depth, and now onto Sigmoid Neurons. Some quotes: A small change in the weights or bias of any single perceptron in the network can sometimes cause the ...
4
votes
2answers
106 views

Usefulness of Differential Geometry

I recently came across these books: Differential Geometry and Lie Groups: A Computational Perspective Differential Geometry and Lie Groups: A Second Course Their subject matter really intrigues me, ...
0
votes
1answer
36 views

How do you convert bits into a different alphabet?

I have forgotten how to do this. How do I figure out what the requirements are for a 128-bit string using a certain alphabet? That is to say, I want to generate a UUID (128-bit) value, using only the ...
1
vote
1answer
59 views

Sets in Mathematics are immutable but in Computer Science sets are mutable and called “Dynamic Sets” - truth of the statement

While reading the classic text Introduction to Algorithms by Cormen et. al. I came across the following claim: Sets are as fundamental to computer science as they are to mathematics. Whereas ...
2
votes
1answer
43 views

A general picture of formal verification in software

I'm trying to piece together a general picture of the state of formal software verification, and I'm having a good bit of trouble. For context, I come from mostly a math background. I'm quite familiar ...
1
vote
1answer
22 views

How is expected value in entropy derived?

I was self learning about entropy and came across this equation. $$ H = - \sum p(x) \log p(x) $$ The equation for entropy in expected value, $$ H(x) = \operatorname*{\mathbb{E}}_{X \sim P}[I(x)] = -\...
0
votes
0answers
8 views

Higher dimensions' equivalent of Polar coordinates for PSO

I'm making a Particle Swarm Optimization (PSO). I've done this on 2D with Cartesian and Polar coordinates for position, velocity, and acceleration. I used Cartesian to draw the particles and do simple ...
1
vote
3answers
63 views

Prove little o with just the definition

I have been searching for a while now but couldn't find anything about this exact pair of functions with the little $\mathcal{o}$ notation. Given the functions $f(n) = 2^{n}$ and $g(n) = n!$ I am ...
0
votes
1answer
19 views

Where does the base come from in a subsequence count?

If sequence X has m symbols, then X has 2m possible subsequences. Where does the base (<...
0
votes
1answer
52 views

Big O Tires Question? [duplicate]

My question is regarding the last paragraph of this excerpt from "Cracking the Coding Interview." (For some reason, my table is not formatting here.) What's the runtime of this code? ...
0
votes
0answers
18 views

Big O Calculating Runtime [duplicate]

My question is regarding the last paragraph of this excerpt from "Cracking the Coding Interview." What's the runtime of this code? ...
2
votes
1answer
37 views

Why is addition in GF(2^8) the same as XOR?

I get the impression it has to do with either some quirk involved with limiting to 2^8 or that I'm misunderstanding what addition can be within the context of a finite field, but I'm not quite sure ...
0
votes
0answers
23 views

I don't understand formula meaning of computer vision Paper

I am master degree student at Computer Science Department. I started master degree at this year. Now I'm reading two papers about computer vision. Actually before time I didn't have experience about ...
1
vote
1answer
33 views

How does the forget layer of an LSTM work?

Can someone explain the mathematical intuition behind the forget layer of an LSTM? So as far as I understand it, the cell state is essentially long term memory embedding (correct me if I'm wrong), ...
0
votes
1answer
43 views

How are Complex Numbers and Complex Analysis used in CS? [closed]

The world is 3D and data of it is usually (as far as I know) represented and processed with real numbers. I've seen very few cases where complex numbers are used in programming and none when it comes ...
2
votes
0answers
66 views

Integer-array indexing (e.g. numpy.take) as function composition: where can I find more resources?

For context, one of Numpy's features is that an an array of integers can be passed as an index to an array, and this selects values at all of the specified positions, in any order with possible ...
1
vote
2answers
107 views

What are the other language models of computation similar to lambda calculus?

I hope this question makes sense, but I was wondering if there are other models of computation similar to lambda calculus that you can use to build up axiomatic mathematical and logical fundamentals ...
3
votes
2answers
1k views

How does a computer interpret real numbers?

I understand that the modern day digital computer works on the binary number system. I can also get, that the binary representation can be converted to rational numbers. But I want to know how does ...
0
votes
0answers
52 views

Can we see all of mathematics as an attempt to simplify computations?

This is a rather strong claim, and therefore likely to be incorrect, but hear me out. Firstly, when I talk of “computations”, I mean this in a broader sense than normally used, because I am including ...
0
votes
1answer
42 views

Effective Procedures and P vs NP Problem

If, suppose, P doesn't equal NP. Implication of this statement is that there is no effective procedure to solve a hard problem; however there exists an acceptable solution S. I have following two ...
1
vote
2answers
96 views

“Mathematical Physics”'s equivalent for Computer Science

Mathematical Physics is a well defined scientific fields that deals with the application of mathematics , mathematical tools , and mathematical methods in the theories and the problems of physics. Is ...
1
vote
0answers
59 views

Mathematical resource material accompanying TAPL

I'm currently reading Types and Programming Languages by Benjamin C. Pierce and just arrived at chapter 21 Metatheory of Recursive Types. Prior to this chapter I found the book challenging but ...
1
vote
1answer
30 views

How can we compute how many processes should be in memory at a time to make CPU utilization max?

From the given formula, we can compute the CPU utilization: CPU Utilization = 1 - P^n Where p is the probability of I/O and n is the total number of processes. E.g, If we were to find CPU ...
14
votes
3answers
2k views

Shannon Entropy of 0.922, 3 Distinct Values

Given a string of values $AAAAAAAABC$, the Shannon Entropy in log base $2$ comes to $0.922$. From what I understand, in base $2$ the Shannon Entropy rounded up is the minimum number of bits ...
1
vote
1answer
40 views

How many prefix code we can find for a given distribution of probability?

A source emits 5 signals s1, s2, s3, s4 and s5 whose probabilities are as follows: 1/3, 1/3, 1/9, 1/9, 1/9, 1/9. How many prefix codes we can construct on A={a, b, c}? And how many are there with the ...
0
votes
1answer
24 views

What is the relation between the quantity of information of $A_i$ and $A$, where $A=\bigcup_iA_i$?

Let $A$ be an event divided into 4 events $A_i$ with the same probability. Why does the quantity of information of $A_i$ satisfy $$ I(A_i) = I(A) + \log (4)?$$
-4
votes
1answer
346 views

Is Alan Turing's proof of the incomputability of halting problem invalid?

I fail to see a contradiction in the halting machine proposed by Alan Turing. Definition of halting machine Where H = all possible programs that terminates N = all possible programs that do not ...
23
votes
2answers
7k views

Do any programming languages use general recursive functions as their basis?

This is a naïve and, therefore, possibly malformed question, so apologies in advance! My view is that a Turing Machine can be seen as the computational basis for procedural/imperative programming ...
2
votes
0answers
58 views

Why, intuitively, is Lob's theorem true? [closed]

Lob's theorem states that: Let $\textbf{Prov}(n^A)$ be the arithmetic statement such that $PA\vdash$ $A$ iff $\textbf{Prov}(n^A)$, where $PA$ is peano arithmetic, and $n^A$ is the godel number of $A$....
1
vote
1answer
32 views

Syntax of recurrence formula not clear

I have this task for Analysis of Algorithms module in university $$ \begin{align*} W, V &= \{v_1, v_2, v_n\}, S = \{s_1, s_2, s_n\}\\ G(W) &= \max~_{i:w_i\leq w} ~\{G(W-s_i) + v_i\}, G(0)=0\\...
0
votes
1answer
84 views

How to represent a map data structure mathematically

Wondering how to represent a map object such as the following mathematically: var foo = { a: 10, b: 'bar', c: true } You could say that it was a function ...
38
votes
3answers
5k views

What exactly is a logic?

An apology might be in due for asking another question about prerequisites, but I was confused about the starting points. I have come across various terms such as "Modal Logic", "Temporal logic", "...
1
vote
0answers
79 views

Order of growth: substitution of monotonically increasing functions

One strategy for ordering the growth of functions involves substitutions when comparing functions using the limit as $n$ goes to infinity comparing two equations using the following rule. $$ \lim_{n\...
5
votes
1answer
208 views

Analogy between Gödel's incompleteness proof and Richard's argument

If we take a look at Gödel's paper “On formally undecidable propositions”, the first self referential proof given in the paper, with the following formula: $$n \in K \equiv \overline{\textit{Bew}}[R(...
1
vote
0answers
59 views

Should I go for computer science or maths? [closed]

I am in 11th grade. The only subject which I love the most is solving alegebraic equations and questions related to it. I enjoy doing trigonometry but hate the part of proving theorems. I opted ...
-1
votes
2answers
81 views

Compute growth of function [closed]

Suppose that $p>0$ and $n>0$ is a natural number. How do I prove that $$ \sum_{k=1}^n k^p = 1^p + 2^p + \dots +n^p \sim \frac{1}{p+1}n^{p+1}=\Theta(n^{p+1})$$ for $n \rightarrow \infty$?
5
votes
1answer
460 views

Mathematical proofs implemented purely by Lambda Calculus

I've seen often stated that Lambda Calculus can be used for mathematical proofing but I haven't yet seen any example how it is actually used for the task. Is there a simple example, lambda ...
4
votes
2answers
90 views

Why algorithms calculating non-tirivial zeros can't be used as proofs of Riemann Hypothesis?

Recently I was reading again this propositions as types paper by Philip Wadler: http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf It gives an impression, ...
205
votes
29answers
49k views

Why is writing down mathematical proofs more fault-proof than writing computer code?

I have noticed that I find it far easier to write down mathematical proofs without making any mistakes, than to write down a computer program without bugs. It seems that this is something more ...
2
votes
0answers
27 views

Soft Question: Looking for resources on computation over reals

As the title suggests, I want to take a look at resources (books, lectures or papers) that are available (free or paid) on computation over reals. Thanks in advance!
1
vote
1answer
45 views

How to understand the probablistic analysis of skiplist?

I've been studying the skiplist analysis from the open data structures book here: Open Data Structures I've understood the first 3 lemma's, (after looking at how they use indicator variables in the ...
2
votes
4answers
171 views

How does maths consistency impacts on computer science?

Lot of mathematicians have made several efforts to answer the question : are mathematics consistent ? Although we haven't yet had a proof of consistency, and surely we will never (Gödel second theorem)...
5
votes
1answer
348 views

Set theory and computer science

It's said that in Zermelo–Fraenkel set theory (ZFC) one can develop all of mathematics. How about computer science? Is it possible to define algorithms as a first step? More specifically, how to ...
5
votes
3answers
1k views

Is there a formalization of the computational model for quantum computers?

There are several equivalent computation models, each capable of simulating each other. For example, the lambda calculus or the SKI calculus which are based on rewriting, Cardelli's object calculus, ...
4
votes
1answer
175 views

Mathematical equivalent of reduce()?

filter() in functional programming can be thought of as being analogous to an equation that filters the range of the variable. map() can be through of as a function mapping domain to codomain. ...
15
votes
1answer
536 views

Mathematics topics or fields that increase computer programming proficiency? [closed]

Generally computer programmers who are mathematicians or have mathematics background are very good in terms of algorithms and computer programming in general. What I am not saying: Mathematics is ...
0
votes
2answers
256 views

Tight bound on the number of divisors of n

The inner loop of this pseudocode runs only for the divisors of n for i=1 to n: if(n%i==0): for j=1 to n: Do something in constant time If I ...