Allegro.cc - Online Community

Allegro.cc Forums » Off-Topic Ordeals » Wikipedia for dummies

Credits go to Andrei Ellman, bamccaig, Bruce Perry, Chris Katko, Elias, Gideon Weems, jmasterx, and OICW for helping out!
This thread is locked; no one can reply to it. rss feed Print
 1   2 
Wikipedia for dummies
Edgar Reynaldo
Major Reynaldo
May 2007
avatar

I don't know it just seems like I can only ever barely understand what they are talking about on wikipedia pages. I'm trying to learn about P versus NP and NP-Completeness and I still don't understand much. The language they use is just so complex. They expect everyone to be expert mathematicians and understand all their crazy relations and proofs and so on... I barely understand half the symbols used and there are always more where that came from. And I definitely don't understand the difference between a deterministic and non-deterministic Turing machine which makes understanding NP that much harder. :P

Anybody else feel the same way?

Edit
See, this is the kind of shit I need :
http://www.explainxkcd.com/wiki/index.php/287:_NP-Complete

Chris Katko
Member #1,881
January 2002
avatar

Wikipedia isn't so much a learning tool, it's a summary page. If you want to learn complex topics in detail, you really need to find a better source.

Some Wikipedia pages are the exception to that, but it's rare.

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

jmasterx
Member #11,410
October 2009

You need to recursively look up terms you do not understand on wiki until you understand your initial wiki page (note: may require multiple passes of the same page)

void understandWikiPage(const std::string& page) {
   bool understood = false;
//first = term, second = wiki page
   std::vector<std::pair<std::string,std::string> > data = getPage(page);
   do {
      understood = true;
      for( std::vector<std::pair<std::string,std::string> >::iterator it = data.begin(); it != data.end(); ++it) {
         if(it->second.length() > 0 && !understandsTerm(it->first)) {
            understandWikiPage(it->second);
            understood = false;     
         }
   } while(!understood);
}

I can't comment on average time complexity of understanding a wiki page, but if you're interested in finding that out, well, you know what to do ;)

Note: This algorithm assumes infinite patience and should be adapted for ragequitting.

I believe NP-Complete problems are problems for which an efficient algorithm has not been found where I believe efficient means at most polynomial time. That includes for example, factoring prime numbers (without using quantum computing). I also believe NP-Complete problems are when, if you can solve one of them, you can solve them all.

---
A few years ago I had an idea of creating a virtual machine with a very simple instruction set. You feed it input and check the output. If it successfully finds the factors of a variety of prime numbers then you've found a program that can factor prime numbers. You then check to see if it does it in Polynomial time.

Repeat until you have a program that computes prime factors in polynomial time :)

Basically, the idea is to brute-force a set of instructions that does the task.

I can't imagine such a program being over about 5,000 instructions.

If your instruction set has 10 instructions, that's only 9678073481456549436528438162585600000 possible programs :)

Chris Katko
Member #1,881
January 2002
avatar

jmasterx said:

A few years ago I had an idea of creating a virtual machine with a very simple instruction set. You feed it input and check the output. If it successfully finds the factors of a variety of prime numbers then you've found a program that can factor prime numbers. You then check to see if it does it in Polynomial time.

Repeat until you have a program that computes prime factors in polynomial time :)

So... a Neural Net?

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

jmasterx
Member #11,410
October 2009

That sounds like a much better way to do it actually :P

Elias
Member #358
May 2000

I found Wikipedia very helpful back when I was at university in the "Theoretic Informatics 2" lecture, because believe it or not, my professor's lecture notes were much harder to follow even :P Unfortunately I forgot most of it by now.

A non-deterministic Turing machine is simply one where you have multiple possibilities to go from one state to another, in other words if you look at the state diagram instead of one arrow leaving each state it can be several. However just to understand what NP-complete means in general you do not need Turing machines at all. They only come important if you want to understand every little mathematical bit, as a mathematical model of computation itself, but unless you're a mathematician I don't see why you would want to.

(Also, for me one entire lecture was only on Turing Machines and then next year's only on complexity classes, so there simply is a lot of information to digest if you want to fully understand every little detail.)

I'm still fascinated by this though:

video

--
"Either help out or stop whining" - Evert

Gideon Weems
Member #3,925
October 2003

Anybody else feel the same way?

Yes. Reading Wikipedia takes energy... It would probably upset me, however, if the powers that be decided to simplify its langauge. Dense language has its place in the world. Besides, "Simple English" pages are available for that.

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

It's just that wikipedia has grown to be such an incorporated part of so many people's online internet experience. Google often points you right to a Wikipedia article. The thing is that an encyclopedia is supposed to be a place where anyone can go and gain knowledge without having to be an expert in the topic. The people who author the wiki know what they're talking about generally for the most part, but they do not have a clue how to go about properly explaining it to people.

Gideon Weems
Member #3,925
October 2003

Do you have any examples? I'll give impressions.

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Gideon Weems
Member #3,925
October 2003

Quote:

In computational complexity theory...

Looks that up.

Quote:

Computational complexity theory is a branch of the theory of computation...

Looks that up. Sees illustration of Turing machine. Ooh, I know that. Goes back.

Quote:

... in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

Okay, that's enough. Going back again.

Quote:

... the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes...

Looks that up. Sees big O notation and goes back.

Quote:

... that generalize the classes P, NP and co-NP...

Skips these, as the language implies they are inherent to the understanding of the very article I now read. Expects definition to follow eventually.

Quote:

... to oracle machines.

Looks that up.

Quote:

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle...

Ah, that thing. For some reason, my mind had replaced the oracle with a demon. I blame thermodynamics.

Phew! I now kind of understand the first sentence, though my equation of "complexity class" with big O notation was off-base. I should remedy that, if I am to proceed further. However, as I do not foresee knowledge of this subject matter assisting me in making awesome and fun games, and the topic's presentation does not interest me too much, I choose not to.

Life is too short to learn everything.

Chris Katko
Member #1,881
January 2002
avatar

Learning from an encyclopedia is the exception, not the norm. It's a reference, not a teaching material. It's a dictionary of concepts. It won't teach you how to use them.

I mean think about how all of your textbooks are structured. Prerequisite knowledge is either noted, or proceeds the chapter in the same book. Addition comes before multiplication. Multiplication comes before exponentiation.

Wikipedia stretches the line between encyclopedia and textbooks. Some of the articles are good enough to "teach" from. But that's not a requirement. There is no scholar deciding the scope of required material--every article stands on its own. You can go from multiplication, back to addition, and end up at Ph.D. level theories involving addition. There is no central "theme" or grouping to those topics to teach a specific theory or concept. There's also so much superfluous information that is useful to people in niche category X/Y/Z, but it tends to overwhelm and confuse someone who doesn't realize it's not important for learning the fundamental concept.

I find Wikipedia to be very good for general information, and very specific information on occasion, but not at all for learning fields. You'd end up with way too many holes in your understanding with no sense of whether you're grasping the depth of the material, or barely touching the surface.

It works well for "trivia stuff" like where Greece is, what Grapes of Wrath was about, or what a the chemical formula for a diesel fuel is. But other stuff--like learning the Central Limit Theorem--not so much. However, animated GIFs sure are amazing for showing many concepts.

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

OICW
Member #4,069
November 2003
avatar

Most of the time I find Wikipedia articles on math really hard to follow and mind you I'm pursuing a Ph.D. degree in computer science. All are much like the polynomial hierarchy article you've linked - bunch of equations with notation completely different to what I'm used to from school or papers/books on the topic.

As far as NP-complete problems are concerned, in a nutshell these are problems like the Travelling salesman. On a computer (or deterministic Turing machine) you can verify that a given solution to the problem is correct in polynomial time, but you can't find the optimal solution in polynomial time using deterministic Turing machine.

Moreover, if you can find mapping of your particular problem to one of the known NP problems, it means that your problem is also NP. I can't right now remember more details, especially the difference between NP-hard and NP-complete, from top of my head. Although I should ::)

[My website][CppReference][Pixelate][Allegators worldwide][Who's online]
"Final Fantasy XIV, I feel that anything I could say will be repeating myself, so I'm just gonna express my feelings with a strangled noise from the back of my throat. Graaarghhhh..." - Yahtzee
"Uhm... this is a.cc. Did you honestly think this thread WOULDN'T be derailed and ruined?" - BAF
"You can discuss it, you can dislike it, you can disagree with it, but that's all what you can do with it"

jmasterx
Member #11,410
October 2009

OICW said:

On a computer (or deterministic Turing machine) you can verify that a given solution to the problem is correct in polynomial time, but you can't find the optimal solution in polynomial time using deterministic Turing machine.

Ah yeah, that's the part I had forgotten.

Bruce Perry
Member #270
April 2000

Try this and this :)

See also https://xkcd.com/547/

--
Bruce "entheh" Perry [ Web site | DUMB | Set Up Us The Bomb !!! | Balls ]
Programming should be fun. That's why I hate C and C++.
The brxybrytl has you.

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Okay, I think simple.wikipedia.org is a little too far in the other direction, now it's not advanced enough to learn very much. But it is useful for a simple direct overview of the subject.

I don't know but when I was a kid I used to love to read encylopedias and find out about things. And I don't remember it being all that difficult to understand a topic. Maybe their treatments were superficial, and that's why it was so easy, but then again maybe it was written specifically with ease of learning in mind.

I mean, if wikipedia isn't there to teach people new things, then what is it there for? Just as a reference for experts in the field? They could go a long way in making it more learner friendly, and using simpler language in introductions and more advanced topics later on in the articles.

jmasterx
Member #11,410
October 2009

Wikipedia is written by the people. And one thing I have noticed is, just because someone knows a topic it doesn't mean they can teach it. The people that contribute articles of advanced topics are probably advanced in their respective field and for them all the terminology is pretty trivial for them.

Chris Katko
Member #1,881
January 2002
avatar

jmasterx said:

Wikipedia is written by the people. And one thing I have noticed is, just because someone knows a topic it doesn't mean they can teach it.

Absolutely. I knew a ton of teachers who knew were very inept at breaking topics down into ways laymen could understand.

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

bamccaig
Member #7,536
July 2006
avatar

I think that Wikipedia is always a work in progress. Since it is written by whomever wants to contribute knowledge the knowledge is subject to error and also subject to poor writing or badly made assumptions. Sometimes it happens, but for the most part you can figure things out. I think that some authors probably are getting it wrong trying to go in depth on a subject without having the time or patience to give it the attention it deserves. You should either gloss over topics that are too in depth to explain in a single page (with references to the more in depth explanations), or you should assume that the reader has no working knowledge of the particular field and start from the beginning. Some topics, such as non-trivial mathematical topics, are probably too advanced for Wikipedia to really explain. However, they should be able to give a laymen description of its meaning, its usefulness, what prerequisites are needed to understand it, and where to find more information.

Wikipedia gives you an idea of whether something warrants more study because you need or want that knowledge, or whether it's subjective and simple enough to form your own ideas around. It won't replace an actual education, but it will certainly complement one. It mostly gives you an idea of what the subject is, and in many cases is detailed enough to be a sufficient one-stop shop for sufficient information gathering.

I would agree that some articles are just poorly written and need work, but that's the nature of Wikipedia. If ReyBrujo was still here I'm sure he'd defend it. There are guidelines and rules for writing Wikipedia articles intended to keep them useful for people. I imagine that some topics are just too complicated to really regulate... If you can't fix it then you just have to trust the authors to be doing good enough. Of course, you can always mark the article as problematic and needing work. I'm sure it would be within Wikipedia's guidelines to mark articles that you have trouble reading with those kinds of attributes: "needs work" or something like that.

Andrei Ellman
Member #3,434
April 2003

jmasterx said:

You need to recursively look up terms you do not understand on wiki until you understand your initial wiki page (note: may require multiple passes of the same page)

https://xkcd.com/214/

--
Don't let the illegitimates turn you into carbon.

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

That XKCD is spot on, Andrei. I've just spent the last 4 hours reading through wikipedia articles trying to figure out how to find an up vector in my modeling program for the camera.

{"name":"609437","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/8\/4831c7eef844baad0fe90a5a97309977.png","w":1280,"h":800,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/8\/4831c7eef844baad0fe90a5a97309977"}609437

Chris Katko
Member #1,881
January 2002
avatar

Hahaha lightweight! ;)

This is what my computer looked like at the end of last night/3 AM.
{"name":"rOI13W6.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/a\/fac552b9dbfe107ba5fae2510c4c4381.png","w":1920,"h":73,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/a\/fac552b9dbfe107ba5fae2510c4c4381"}rOI13W6.png

Note the 163 = tabs open. ;D

And I actually closed dozens before I went to bed, but I kept finding knew topics. Last night was a rare, really productive learning session.

Memory, optimizations, design-by-policy/contract, lots of D programming language, compilation of features missing in many languages (ala string slicing, digit grouping, etc), exceptions, stack-based allocation, data-driven programming, some DirectX/OGL mobile uglyness.

I'm much more likely to switch toward D. It's got way more helpful features than C++, yet lets you program closer to the metal than C++ and maybe C. It directly supports things like specifying structure alignment / padding. And they're apparently working toward making the entire D common library support "no garbage collection" mode. They have a rule about "if it looks like C++, it should function like C++" so there's no confusing duality of syntax meanings in your head. And I just found out the co-author is also the writer of the quintessential book "Modern C++: Generic Programming and Design Patterns applied" . There's lots more, but I don't want to fill this thread up.

WAIT, there's one insanely awesome one. You can write compile-time functions. No template insanity needed (though it supports templates). You can literally write imperative functions that write functions, or calculate numbers at compile time. You can also write in any function a "static if" statement that functions as a compile time decision without littering your code with preprocessor macros.

And default language support for Design by Contract which allows you to specify almost like an exception syntax the pre-conditions, post-conditions and invariants of your code. Previously, people made the same proposal for C++ and they rejected it--apparently helping us write clean, clear, safe code isn't in their budgets.

[edited]

I can't stop! They also support a built-in unit testing framework. You compile your program with a single flag, and it runs all unit-test{} blocks on your code. Everyone's all about unit tests these days but it's strange that nobody mentions that Design By Contract is the orthogonal complement to unit testing.

[edited again]

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

Bruce Perry
Member #270
April 2000

I love D too :)

--
Bruce "entheh" Perry [ Web site | DUMB | Set Up Us The Bomb !!! | Balls ]
Programming should be fun. That's why I hate C and C++.
The brxybrytl has you.

l j
Member #10,584
January 2009
avatar

You can write compile-time functions

This is also possible in C++11 with constexpr.

I don't like D's struct vs class. It seems like a major design fault to have reference vs value types for a language with supposedly low level memory access possibilities.

bamccaig
Member #7,536
July 2006
avatar

 1   2 


Go to: