Hovedinnhold
Kurs: (Informatikk > Enhet 1
Leksjon 1: Introduksjon til algoritmerHva er en algoritme og hvorfor skal du bruke tid på det?
Ønsker du å delta i samtalen?
Ingen innlegg enda.
Videotranskripsjon
- [Voiceover] What is an algorithm? One definition might be a set of steps to accomplish a task. You might have an algorithm for getting from home to school, for making a grilled cheese sandwich, or for finding what you're
looking for in a grocery store. In computer science, an
algorithm is a set of steps for a computer program
to accomplish a task. Algorithms put the science
in computer science. And finding good algorithms
and knowing when to apply them will allow you to write
interesting and important programs. Let's talk about a few famous algorithms. How does Google Hangouts
transmit live video across the Internet so quickly? They use audio and video
compression algorithms. How does Google Maps figure out how to get from Dallas, Texas to Orlando, Florida so that you can get to Disney World? They use a route finding algorithm. How does Pixar color a
3D model of a character based on the lighting in a virtual room? They use a rendering algorithm. How does Nasa choose how
to arrange the solar panels on the International Space Station and when to rearrange them? They use an optimization
and a scheduling algorithm. Those algorithms are more complex than our everyday algorithms like making a grilled cheese sandwich. But they boil down to the same thing, a set of steps to accomplish a task. If you know something
about existing algorithms, you can save yourself some effort and make your programs faster by applying the right one. For example, let's say
that you're writing a game and you want the user to be able to play against the computer. Well, you could look at
checkers games for inspiration. Computer scientists have
figured out how to write checkers programs that never lose by using the minimax search algorithm to search through the huge
tree of possible moves. If your game is similar to checkers, then you might be able to use algorithms based on these techniques. If not, then knowing the
limitations of those algorithms might lead you to redesign your game if it requires having a
skilled computer player. It's also important to know
how to design new algorithms as well as how to analyze their
correctness and efficiency. In the biological sciences, new algorithms are
continually being designed with purposes like designing
the molecular structures that are the core of
disease fighting drugs. In physics, algorithms simulate climate and weather patterns. In other algorithms, search
and analyze the vast data about stars in the
universe that's collected by automated space telescopes. Across all the sciences,
and even on websites like Khan Academy, efficient
algorithms are needed to analyze huge data sets
or to select intelligently from a vast number of possible decisions. In just about any area
you might be interested, new algorithms will allow
massive computational power to be harnessed to do things
that people really need and care about. Now, not all algorithms are created equal. So what makes a good algorithm? The two most important criteria are that it solves a problem and that it does so efficiently. Most of the time, we want an algorithm to give us an answer that
we know is always correct. Sometimes we can live with an algorithm that doesn't give us the correct
answer or the best answer because the only perfect algorithms that we know for those problems take a really, really long time. For example, let's say we want a program that would determine
the most efficient route for a truck that delivers packages, starting and ending the day at a depot. It would take weeks to run going through all the possibilities. But if we're okay with a program that would determine a route that's good but maybe not the best, then it could run in seconds. In some case, good is good enough. How do you measure the
efficiency of an algorithm? We could time how long
it takes to run the code, but that would only tell
us about that particular implementation in a certain
programming language on a particular computer and just for the input it was given. Instead, computer
scientists use a technique called asymptotic analysis, which allows algorithms to
be compared independently of a particular programming
language or hardware so that we can conclusively say that yes, some algorithms are more
efficient than others. Now you can learn about algorithms and asymptotic analysis on Khan Academy thanks to the contribution
of two Dartmouth college professors. Tom Cormen is the first author of the most popular
college algorithms textbook in the world, plus the author of Algorithms Unlocked. Devin Balkcom designed
Dartmouth's intro CS course and researches robotics. He built the world's first
origami folding robot. Tom and Devin will teach
you many of the algorithms that you would learn in APCS or CS 101, like searching algorithms,
sorting algorithms, recursive algorithms
and my personal favorite, graph algorithms. There will be tons of
interactive visualizations, quizzes and coding challenges to help you understand better along your learning journey.