maths.free › Combinatorics & Graph Theory › Combinatorial Basics › Discussion
Discussion
Carlos, Dave and Yolanda were fascinated by the discussion on complexity. Zori was less enthusiastic but even she sensed that the question of which problems could be solved quickly had practical implications.
Discussion
Carlos, Dave and Yolanda were fascinated by the discussion on complexity. Zori was less enthusiastic but even she sensed that the question of which problems could be solved quickly had practical implications. She could even predict that people could earn a nice income solving problems faster and more accurately than their competition.
Bob remarked, I'm not sure I understand what's being talked about here. I don't see why it can't be the case that all problems can be solved. Maybe we just don't know how to do it. Xing said, Any finite problem can be solved. There is always a way to list all the possibilities, compare them one by one and take the best one as the answer. Alice joined in, Well, a problem might take a long time just because it is big. For example, suppose you are given two DVD's, each completely full with the data for a large integer. How are you possibly going to multiply them together, even with a large computer and fancy software. Carlos then offered, But I think there are really hard problems that any algorithm will take a long time to solve and not just because the input size is large. At this point, I don't know how to formulate such a problem but I suspect that they exist.
Tani ti. Asnjë kalkulator nuk e zgjidh këtë, por pjesët e saj janë të llogaritura. Provo një më poshtë, ose shkruaj tënde.
Një llogari e lirë shtohet shënime në çdo mësim, një regjistrim të asaj që ju keni përfunduar, problemet tuaja të zgjidhura në një vend, dhe një mësues që ju mund të pyesni rreth kësaj faqeje. Matematika vetë është e hapur për të gjithë, të regjistruar apo jo.
Regjistrohu HyrSimbolet e përdorura këtu
Prek çdo simbol për përkufizimin e plotë, një fotografi dhe se çfarë do të thotë çdo shkronjë në të.
Pyetja që bëjnë njerëzit
Permutation or combination?
Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).
What is a graph in this sense?
Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.
Pjesa e kësaj faqeje është adaptuar nga Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). E përmbledhur dhe ri-shkruar këtu; gabimet janë tona.
Më shumë në Combinatorics & Graph Theory
The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs