Formatieve toets 4A

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4

Welke uitspraak over BubbleSort is onjuist?

1. Het is een eenvoudig sorteeralgoritme.
2. Het is een efficiënt algoritme voor lijsten met weinig elementen
3. Het algoritme vergelijkt ieder element met het volgende element in de lijst.
4. Het algoritme maakt gebruik van divide-and-conquer.

Bij welk van de onderstaande algoritmen wordt de efficiëntie nauwelijks bepaald door de lijst die moet worden gesorteerd?

1. BubbleSort
2. MergeSort
3. QuickSort

Een bruteforce-algoritme is een algoritme dat:

1. een probleem eerst vereenvoudigt en vervolgens oplost.
2. eerst sorteert en vervolgens steeds door te halveren naar de oplossing zoekt
3. binnen een vooraf bepaalde tijd naar de beste oplossing zoekt.
4. alle mogelijkheiden nagaat totdat het de juiste oplossing heeft gevonden

Beschrijf het algoritme dat de wiskundige Dantzig als oplossing voor het rugzakprobleem heeft bedacht.

De pincode die hoort bij een bankpas bestaat uit vier cijfers. Cijfers mogen vaker voorkomen. Teken het toestandsdiagram van een eindige automaat die de generator van een pincode kan zijn.

In de afbeelding zie je een toestandsdiagram van een eindige automaat die onder andere woorden met precies één b accepteert. De woorden bestaan alleen uit de letters a en b.

Ontwerp een eindige automaat die alle woorden met precies één a accepteert

Ontwerp een eindige automaat die alle woorden met minstens een a accepteert.

Ontwerp een eindige automaat die alle woorden met hoogstens een a accepteert.