Algoritme er en trinnvis prosedyre for å løse et problem eller utføre en oppgave. I sammenheng med datastrukturer og algoritmer er det et sett med veldefinerte instruksjoner for å utføre en spesifikk beregningsoppgave. Algoritmer er grunnleggende for informatikk og spiller en svært viktig rolle i å designe effektive løsninger for ulike problemer. Å forstå algoritmer er avgjørende for alle som er interessert i å mestre datastrukturer og algoritmer.

Innholdsfortegnelse

• Hva er en algoritme?
• Hvordan fungerer algoritmer?
• Hva gjør en god algoritme?
• Hva er behovet for algoritmer?
• Eksempler på algoritmer
• Hvordan skrive en algoritme?
• Lær det grunnleggende om algoritmer
• Analyse av algoritmer
• Typer algoritmer

Hva er en algoritme?

An algoritme er en begrenset sekvens av veldefinerte instruksjoner som kan brukes til å løse et beregningsproblem. Den gir en trinn-for-trinn prosedyre som konverterer en inngang til en ønsket utgang.

Hvordan fungerer algoritmer?

Algoritmer følger vanligvis en logisk struktur:

• Inndata: Algoritmen mottar inndata.
• Behandling: Algoritmen utfører en serie operasjoner på inndataene.
• Produksjon: Algoritmen produserer ønsket utgang.

Egenskaper til en algoritme:

• Klart og entydig: Algoritmen skal være entydig. Hvert av trinnene skal være tydelige i alle aspekter og må kun føre til én mening.
• Veldefinerte innganger: Hvis en algoritme sier å ta innganger, bør det være veldefinerte innganger. Det kan ta innspill eller ikke.
• Veldefinerte utganger: Algoritmen må klart definere hvilken utgang som skal gis, og den bør også være godt definert. Den skal produsere minst 1 utgang.
• Begrensethet: Algoritmen må være endelig, dvs. den skal avsluttes etter en begrenset tid.
• Gjennomførbart: Algoritmen må være enkel, generisk og praktisk, slik at den kan utføres ved bruk av rimelige begrensninger og ressurser.
• Språkuavhengig: Algoritmen må være språkuavhengig, det vil si at det bare må være enkle instruksjoner som kan implementeres på et hvilket som helst språk, og likevel vil utgangen være den samme, som forventet.

Hva er behovet for algoritmer?

Algoritmer er avgjørende for å løse komplekse beregningsproblemer effektivt og effektivt. De gir en systematisk tilnærming til:

• Løser problemer: Algoritmer bryter ned problemer i mindre, håndterbare trinn.
• Optimalisering av løsninger: Algoritmer finner de beste eller nesten optimale løsningene på problemer.
• Automatisering av oppgaver: Algoritmer kan automatisere repeterende eller komplekse oppgaver, noe som sparer tid og krefter.

Eksempler på algoritmer

Nedenfor er noen eksempler på algoritmer:

• Sorteringsalgoritmer: Slå sammen sortering, Hurtigsortering, Heapsortering
• Søkealgoritmer: Lineært søk, Binært søk, Hashing
• Grafalgoritmer: Dijkstras algoritme, Prims algoritme, Floyd-Warshall-algoritmen
• Algoritmer for strengsamsvar: Knuth-Morris-Pratt-algoritme, Boyer-Moore-algoritme

Hvordan skrive en algoritme?

Følg disse trinnene for å skrive en algoritme:

• Definer problemet: Angi tydelig problemet som skal løses.
• Design algoritmen: Velg et passende algoritmedesignparadigme og utvikle en trinn-for-trinn-prosedyre.
• Implementer algoritmen: Oversett algoritmen til et programmeringsspråk.
• Test og feilsøk: Utfør algoritmen med ulike innganger for å sikre korrekthet og effektivitet.
• Analyser algoritmen: Bestem tids- og romkompleksiteten og sammenlign den med alternative algoritmer.

Lær det grunnleggende om algoritmer

• Hva er Algoritme | Introduksjon til algoritmer
• Definisjon, typer, kompleksitet, eksempler på algoritmer
• Algoritmer designteknikker
• Hvorfor er analyse av en algoritme viktig?

Analyse av algoritmer

• Asymptotisk analyse
• Verste, gjennomsnittlige og beste tilfeller
• Asymptotiske notasjoner
• Nedre og øvre grense teori
• Introduksjon til amortisert analyse
• Hva betyr 'romkompleksitet'?
• Polynomisk tidstilnærmingsskjema
• Regnskapsmetode | Amortisert analyse
• Potensiell metode i amortisert analyse

Typer algoritmer

Algoritmer kan være forskjellige typer, avhengig av hva de gjør og hvordan de er laget. Noen vanlige typer er:

1. Søke- og sorteringsalgoritmer

• Introduksjon til søkealgoritmer
• Introduksjon til sorteringsalgoritme
• Stabile og ustabile sorteringsalgoritmer
• Nedre grense for sammenligningsbaserte sorteringsalgoritmer
• Kan kjøretidskompleksiteten til en sammenligningsbasert sorteringsalgoritme være mindre enn N logN?
• Hvilken sorteringsalgoritme gjør minimum antall minneskrivinger?

2. Grådige algoritmer

• Introduksjon til grådige algoritmer
• Aktivitetsvalgproblem
• Huffman-koding
• Problem med jobbsekvensering
• Quiz om grådige algoritmer
• Minimum antall plattformer som kreves for en jernbane-/busstasjon

3. Dynamiske programmeringsalgoritmer

• Introduksjon til dynamisk programmering
• Overlappende underproblemer Egenskap
• Optimal underbygningseiendom
• Lengst økende etterfølge
• Lengste vanlige etterfølge
• Min kostnadsbane
• Myntskifte
• Matrisekjedemultiplikasjon
• 0-1 Rullesekkproblem
• Lengste palindromiske sekvens
• Palindrom-partisjonering

4. Mønstersøkealgoritmer

• Introduksjon til mønstersøking
• Naiv mønstersøking
• KMP-algoritme
• Rabin-Karp-algoritmen
• Mønstersøking med en prøve av alle suffikser
• Aho-Corasick-algoritme for mønstersøking
• Z-algoritme (Lineær tidsmønstersøkealgoritme)

5. Tilbakesporingsalgoritme

• Introduksjon til Backtracking
• Skriv ut alle permutasjoner av en gitt streng
• Ridderens turproblem
• Rotte i en labyrint
• N Queen Problem
• Delmengde Sum
• m Fargeproblem
• Hamiltonsk syklus
• Sudoku

6. Divide and Conquer-algoritmen

• Introduksjon til Divide and Conquer
• Slå sammen sortering
• Skriv din egen pow(x, n) for å beregne x*n
• Tell inversjoner
• Nærmeste poengpar
• Strassens matrisemultiplikasjon

7. Geometrisk algoritme

• Introduksjon til geometriske algoritmer
• Nærmeste poengpar | O(nlogn) Implementering
• Hvordan sjekke om et gitt punkt ligger innenfor eller utenfor en polygon?
• Hvordan sjekke om to gitte linjestykker krysser hverandre?
• Gitt n linjestykker, finn om noen to stykker krysser hverandre
• Hvordan sjekke om gitt fire poeng danner en firkant
• Konveks skrog ved hjelp av Jarvis' algoritme eller innpakning

8. Matematiske algoritmer

• Introduksjon til matematiske algoritmer
• Skriv en effektiv metode for å sjekke om et tall er multiplum av 3
• Skriv et program for å legge til to tall i grunntallet 14
• Program for Fibonacci-tall
• Gjennomsnitt av en strøm av tall
• Multipliser to heltall uten å bruke multiplikasjon, divisjon og bitvise operatorer, og ingen løkker
• Babylonsk metode for kvadratrot
• Sil av Eratosthenes
• Pascals trekant
• Gitt et tall, finn det nest minste palindromet
• Program for å legge til to polynomer
• Multipliser to polynomer
• Tell etterfølgende nuller i faktorial av et tall

9. Bitvise algoritmer

• Introduksjon til bitvise algoritmer
• Lille og Store Endian
• Oppdag motsatte tegn
• Bytt biter
• Slå av biten lengst til høyre
• Roter biter
• Neste høyere tall med samme antall sett biter
• Bytt to nibbles i en byte

10. Grafalgoritmer

• Introduksjon til randomiserte algoritmer
• Linearitet av forventning
• Forventet antall forsøk frem til suksess
• Randomiserte algoritmer | Sett 0 (matematisk bakgrunn)
• Randomiserte algoritmer | Sett 1 (introduksjon og analyse)
• Randomiserte algoritmer | Sett 2 (klassifisering og applikasjoner)
• Randomiserte algoritmer | Sett 3 (1/2 omtrentlig median)
• Reservoarprøvetaking