Algorithmes de recherche
Durée estimée: 45 minutes
Introduction
Les algorithmes de recherche correspondetn à un domaine de recherche très important des scientes informatiques. Pensez au nombre de fois où vous faites une recherche sur internet avec un moteur de recherche comme Google ou un autre. C' est assez étonnant de voir le volume d'informoation que ces moteurs peuvent traiter et à quelle vitesse ils répondent.
So, as the video described, when you do a Google search, you aren't actually searching the Web, you're searching Google's index of the Web. Google's spider programs are constantly traversing the web, collecting millions of web pages and organizing them into an index. When you do a Web search Google's algorithms are searching that index.
What's the best algorithm for searching an index? An index is an ordered collection. Think of the index that comes at the back of a textbook. It is organized in alphabetical order. Each entry in the index refers to some page in the book.
Activité POGIL pour la classe (15 minutes)
To help you think about the problem of searching an index we're going to play a guessing game. The objective of the game is to come up with the most efficient algorithm for guessing a number between 1 and 100, where most efficient means that it takes the fewest number of guesses.
To play the game you can use this widget:
Or, you can play the game "by hand", in which case one team member will think of a secret number between 1 and 100 and the other team members will collaborate to try to come up with the best guess. Just as in the widget,after each guess, the person who knows the secret will tell the guessers whether the guess was too high or too low or just right.
After figuring out a good algorithm, write it in pseudocode.
Break into POGIL teams of 4. Record your answers using this worksheet. (File-Make a Copy to have a version you can edit.)
| Role | Responsibility |
|---|---|
| Facilitator | For each trial of the guessing game, the facilitator records the team's guesses and the result (too high or too low or just right) and keeps track of how many guesses are made. |
| Spokesperson | Reports the team's pseudocode algorithm. |
| Quality Control | Tests the algorithm, using the widget or by playing the guessing game by hand. |
| Process Analyst | Keeps track of the teams progress and assesses its performance and records on the Portfolio the team's answers to the following guided inquiry questions. |
Questions
- (Portfolio) Define a pseudocode algorithm that will efficiently play the guessing game.
- (Portfolio) To guess a number between 1 and 100, what's the maximum number of guesses your algorithm would take?
- (Portfolio) To guess a number between 1 and 500, what's the maximum number of guesses your algorithm would take?
Guessing Game: I'll Guess Your Secret Number
One way to look at this game is that we are searching for a number in a list of numbers. Our search made use of the fact that numbers are ordered. The feedback we received – "too high" or "too low" – was based on that order. If you're still working on figuring out an efficient algorithm, maybe the following widget will give you some ideas. Try to observe the algorithm that the widget is using.
An Efficient Algorithm
There is a very efficient algorithm for the guessing game problem, known as the binary search algorithm. Click here to see the pseudocode.
Sequential (or Linear) Search
What if you had to search a set of data that was not sorted? Binary search won't work in that case. To illustrate this problem, let's try a variation of our guessing game. This time the app will only tell you if your guess is right or wrong, not whether it is too high or too low. Try it.
As you can see from this game, if you don't know the order of the items you are going to search, you have no choice but to search them sequentially if you definitely want to find the secret number.
Here's a summary of the sequential (or linear) search algorithm. Let's suppose we have 16 boxes umbers 1 to 16, each containing a letter, but that the words are not in any particular order:
Problem: Find the letter 'F'
|
Pseudocode of Sequential (or Linear) Search Algorithm
Let b represent the box number to search, initially 1
Repeat until you find 'F' or run out of boxes to search
Look in box b.
If 'F' is in box b, stop and report b's value.
Otherwise, add 1 to b
If you don't find 'F' in any box, report it not found.
|
So in this algorithm we are letting b keep track of what box we are searching. It starts at 1 and increases by 1 so that we will look at every box until we find 'F' or run out of boxes. If we find 'F' we report what box it was in by reporting b's value. If we don't find it, we report that it wasn't found.
Searching for 'F' in this set of boxes represents our worst case scenario because our algorithm would have to look in every box to conclude that 'F' was not in the boxes.
Self-Check
Choose all that apply.
Choose all that apply.
Reflection: For Your Portfolio
Create a page named Search Algorithms under the Reflections category of your portfolio and answer the following questions:
- (POGIL) Define a pseudocode algorithm that will efficiently play the guessing game.
- (POGIL) To guess a number between 1 and 100, what's the maximum number of guesses your algorithm would take?
- (POGIL) To guess a number between 1 and 500, what's the maximum number of guesses your algorithm would take?
- Suppose you have a deck of cards and you want to find the Ace of Spades. If the deck is shuffled, which is the best search algorithm to use and why?
- Give an example of a search problem you encounter in everyday life. Does it use sequential, binary, or some other search?