Is there a notion like Kolmogorov complexity but for functions? Computer Science |
- Is there a notion like Kolmogorov complexity but for functions?
- Is there a future for me as a computer scientist?
- How to index multidimensional array starting from the end? (Python3)
- Time Complexity of Array.Splice
- Humble Book Bundle: Be a Coder by No Starch Press
- Determine if I should buy dollars or euros?
- Online OS class offered by universities ?
| Is there a notion like Kolmogorov complexity but for functions? Posted: 29 Dec 2017 06:22 PM PST The Kolmogorov complexity of a string is defined as the size of the smallest program (i.e., Turing machine) that outputs the string. This might seem like it would vary widely depending on the programming language (or Turing machine representation) used, but there is a theorem that shows there is some constant such that (e.g.) the difference in size between the smallest Ruby program and the smallest Java program for any string is bounded by a constant (specifically, the length of the smallest Ruby interpreter written in Java). Unfortunately, it can also be shown that Kolmogorov complexity is uncomputable using a self-referential concept known as the Berry paradox: consider "the smallest positive integer not definable in fewer than twelve words" (note that this defining phrase has eleven words). My question is whether there is a similar notion of Kolmogorov complexity for functions or decision problems, i.e., the length of the smallest Turing machine that implements the function. Is this even a coherent idea? I could not find any mention of this concept on the web, which is surprising, since it seems like it would be an obvious extension of algorithmic information theory. (Note that Kolmogorov complexity is not the same as time or space complexity.) [link] [comments]  |
| Is there a future for me as a computer scientist? Posted: 29 Dec 2017 11:17 AM PST Hello everyone, im 22 years old and im studying CS at an undergraduate program in germany. Usually i have more 'practicable' courses then theory heavy courses. However, last semester i had a course about Theory of Computation and i immideatly fell in love with it. I don't know why, but my eyes started sparkling when my Professor started teaching us about the complexity classes and how some are/aren't equivalent to another. This course encouraged me to dive deeper into the subject and now, having read more than 4 books im convinced that i would absolutely love to contribute something to this beautiful and deep field. Im not an extremely smart guy in fact my grades are average. Actually im here where i am because of my big passion for CS and hard dedication. So im having some kind of self doubt if i should pursue this career path. Im afraid that im not smart enough to contribute something to this field. I hope there is someone in this subreddit that could tell me about his experience and could tell me his opinion about my whole situation. To sum it up: I love CS, ToC and Math and my wish is to be a computer scientist some day but im afraid that im not smart enough. Tell me your opinion in the commends Thanks :) [link] [comments]  |
| How to index multidimensional array starting from the end? (Python3) Posted: 30 Dec 2017 12:09 AM PST Say I have a numpy array A with shape (a,b,c,d). How would I index this array starting from d. For example if A holds the shape (2, 2, 3, 8), and I want to extract the shape (2,2,3) for the first value of d, how would I go about that. Similarly, how about (2,2) for the first values of c and d? I have searched for hours to no avail and it's killing me. Thanks! [link] [comments]  |
| Time Complexity of Array.Splice Posted: 29 Dec 2017 01:16 PM PST Time complexity of array.splice is worst-case O(n) because it has to potentially copy over all the elements. Question 1: this means array.shift() is always O(n)? Or is it optimized somehow low-level where it just adjusts starting memory address? Question 2: People say use a linked list instead of array if you repeatedly splice because deletion is O(1). But you'd still have to search through linked list to find element (which worst-case is still linear) because it's not indexed. So how do you index a linked list, so that deletion is ACTUALLY constant time? (also, is a language's implementation, like JS, of an array ever a linked list?) [link] [comments]  |
| Humble Book Bundle: Be a Coder by No Starch Press Posted: 29 Dec 2017 02:27 PM PST |
| Determine if I should buy dollars or euros? Posted: 29 Dec 2017 08:14 PM PST I plan to build a program in python to get the USD and EUR historical values... The idea is that this program should tell me if it's a good or a bad day to buy some of these currencies... What is the state of the art to do this? I imagine that it could be done with some method of artificial intelligence as evolutionary algorithms, but I'm not sure about the step by step or the detail of how the algorithm would be... Could somebody tell me a hint? [link] [comments]  |
| Online OS class offered by universities ? Posted: 29 Dec 2017 10:37 AM PST I'm searching for a university that offers an online (i.e. Distant learning ) OS (operating systems) course that applies to an official transcript and that can be transferred for university credit (i.e. units) ? I work as a software engineer at amazon and last year I decided to return to university for computer science, taking discrete mathematics and computer organization from the university of North Dakota and university of northern Iowa, respectively. Both courses I am taking for credit that show up on an official transcript (once completed ). I'd like to find a school that offers an OS for credits as well. Although coursera (and other MOOC) offer an OS class, I prefer taking it from a university that will allow me to obtain actual credits since I may return for a undergraduate degree or I may return for a masters. Any ideas ? [link] [comments]  |
| You are subscribed to email updates from Computer Science: Theory and Application. To stop receiving these emails, you may unsubscribe now. | Email delivery powered by Google |
| Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States | |
No comments:
Post a Comment