Notatki z lekcji informatyki (XIV LO 2006/2007)

Z RNO-Wiki
Wersja Rno (dyskusja | edycje) z dnia 12:25, 14 lis 2007
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Powrót do strony lekcji informatyki

Spis treści

Lekcja organizacyjna

2006.10.03

Lekcja 2

2006.10.10
  • Przeczytaj nasze zasady i reguły
  • Maszyna RAM --- nasz model komputera :-)
  • Emulator maszyny RAM pod Windows
  • Nasze problemy (ich specyfikacje) zadania domowe (kod: RAM01):
    1. (2 pkt) Napisz program, który wczyta z taśmy wejściowej dwie liczby i wypisze mniejszą z nich
    2. (2 pkt) Napisz program, który wczytane trzy liczby z taśmy wejściowej wypisze na wyjście w porządku niemalejącym.
      Na przykład dla danych: 5 8 2, program powinien wypisać: 2 5 8.
    3. (2 pkt) Dane: dwie liczby a,b.
      Wynik: reszta z dzielenia całkowitego liczby a przez b
    4. (2 pkt) Napisz program, który dla wczytanej liczby wypisze jej cyfrę setek.
      Na przykład dla liczby 129458 program powinien wypisać 4, a dla liczby 68 powinien wypisać 0.
    5. (2 pkt) Napisz program, który dla wczytanej liczby sprawdzi, czy jest ona parzysta. Wynik 1 oznacza TAK, a 0 --- nie.
    6. (2 pkt) Napisz program, który dla wczytanej liczby sprawdzi, czy jest ona podzielna przez 2 lub 3 lub 5. Wynik 1 oznacza TAK, a 0 --- nie.

Lekcja 3

2006.10.17
  • Problem obliczenia reszty z dzielenia dwóch liczb
    Dane: <math>a,b</math> - liczby naturalne
    Wynik: reszta z dzielenia <math>a</math> przez <math>b</math>
    Rozwiązanie w maszynie RAM: Modulo.ram.gif
  • Problem znalezienia maksymalnej liczby w zbiorze
    Dane: <math>n, a_1, a_2, \ldots, a_n</math> - liczby naturalne
    Wynik: <math>\max_{k=1,2,\ldots,n} a_k</math>
    Rozwiązanie w maszynie RAM: Maksimum.ram.gif
  • Zadanie domowe (kod RAM02)
  1. Problem pierwszości:
    Dane: <math>n \geq 2</math> - liczba naturalna
    Wynik:
    1. 1 - jeśli <math>n</math> jest liczbą pierwszą
      0 - jeśli <math>n</math> nie jest liczbą pierwszą
  2. Pierwiastek
    Dane: <math>n \geq 1</math> - liczba naturalna
    Wynik: część całkowita liczby <math>\sqrt{n}</math>, czyli <math>\max\{k : k^2 \leq n\}</math>
  3. Odwróc kolejność liczb
    Dane: <math>n, a_1, a_2, \ldots, a_n</math> - liczby całkowite (<math>n>0</math>)
    Wynik: Liczby w odwrotnej kolejności, czyli <math>a_n, a_{n-1}, \ldots, a_1</math>
  4. Powtórka
    Dane: <math>n, a_1, a_2, \ldots, a_n</math> - liczby całkowite (<math>n>0</math>)
    Wynik: 1 lub 0 w zależności od tego, czy istnieją wśród danych liczb trzy jednakowe liczby (1-prawda, 0-fałsz)
  5. Podzielność przez 7
    Dane: <math>n</math>, <math>b_{n-1}, b_{n-2}, \ldots, b_1, b_0</math> - bity pewnej liczby całkowitej (podane od najbardziej znaczących), <math>n>0</math>
    Wynik: 1 lub 0 w zależności od tego, czy dana liczba w systemie dwójkowym jest podzielna przez 7.

Lekcja 4

2006.10.24
  • Problem : Suma kwadratów
    Dane: <math>n</math> - liczba naturalna
    Wynik: suma <math>\sum_{k=1}^{n} k^2 = 1^2 + 2^2 + \ldots + n^2</math>
    Rozwiązanie w Maszynie RAM:
        LOAD  =0
        STORE  2
        READ   1

 PETLA: LOAD   1
        MULT   0
        ADD    2
        STORE  2
        LOAD   1
        SUB   =1
        STORE  1
        JGTZ   PETLA

        WRITE  2

Lekcja 5

2006.10.31
  • Problem
    Dane: <math>a, b</math> - liczby naturalne takie, że <math>a > b</math>
    Wynik: największy wspólny dzielnik liczb a i b, czyli NWD(a,b).
    Rozwiązanie: Algorytm Euklidesa
  • Zadanie domowe (kod: RAM03):
    1. Problem (3 pkt)
      Dane: n - liczba naturalna
      Wynik: liczba zer od końca w liczbie n!
    2. Problem (3 pkt)
      Dane: n - liczba naturalna
      Wynik: ostatnia cyfra liczby <math>2^n</math>
    3. (*) Problem (+5 pkt)
      Dane: n - liczba naturalna
      Wynik: ostatnia cyfra liczby Fibonacciego <math>f_n</math>

Lekcja 6

2006.11.07

Dzisiaj rozwiązywaliśmy na kartkach zadania z Maszyny RAM

Łagodne wprowadzenie do języka C/C++

2006.11.14
  • Przeczytaj notatki, które pozwolą Ci zrozumieć składnię jezyka C/C++
  • Jeśli rozumiałeś instrukcje maszyny RAM, to nie powinieneś mieć żadnych kłopotów z programowaniem w bardzo wygodnym języku, mianowicie w języku C/C++.
  • Zadanie domowe (kod CPP01)
    1. RAM01.2
    2. RAM01.4
    3. RAM02.1
    4. RAM02.2
    5. RAM02.4
    6. RAM02.5
    7. (+ pkt) "Czy umiesz potęgować?"
      Dane: <math>a, b</math> - naturalne
      Wynik: ostatnia cyfra liczby <math>a^b</math>
    8. (+ pkt) "Szybki Fibonacci"
      Dane: <math>n, m</math> - naturalne
      Wynik: reszta z dzielenia <math>Fib(n)</math> przez <math>m</math>

Lekcja 8

2006.11.21

Lekcja 9

2006.11.28
  • Rejestracja w zawodach [1]
  • Programowanie zadań matematycznych (punkty liczą się do aktywności; każde zadanie warte jest 3 punkty)
    • TEST -- proste zadanie sprawdzające, czy umiesz przerwać pętlę
    • FCTRL -- po polsku, to zadanie RAM03.1
    • Proste dodawanie wielu liczb z wejścia (uwaga: kilka zestawów danych)
    • Suma cyfr - obliczanie sumy cyfr danej liczby na wejściu
  • Zadanie domowe : CPP02

Lekcja 10

2006.12.05
  • Postać liczby <math>n</math> w systemie dwójkowym
    <math>n = b_0 + 2 b_1 + 4 b_2 + 8 b_3 + \ldots + 2^k b_k, \qquad (b_i\in\{0,1\}).</math>
    • Chcąc wyznaczyć ostatni bit (najmniej znaczący) liczby <math>n</math> wystarczy obliczyć <math>n \mod 2</math>, czyli poprostu sprawdzić, czy liczba jest parzysta.
 x = n%2; // x - ostatni bit liczby n;  1 - jeśli liczba n jest nieparzysta,  0 - jeśli n jest parzysta
    • Przykład: <math>n=18</math>
      <math>n = 16 + 2 = 2^4 + 0\cdot 2^3 + 0\cdot 2^2 + 2^1 + 0\cdot 2^0 = (10010)_2</math>
      <math>18 \mod 2=0</math> - ostatni bit
      Zauważ, że po podzieleniu przez 2, otrzymujemy liczbę, której zapis binarny jest zapisem binarnym liczby przed podzieleniem przez 2, bez ostatniego bitu, tzn.
      <math> 18/2 = 9 = (1001)_2 </math>
    • Program wyznaczający kolejne bity (od najmniej znaczącego czyli od tyłu) liczby <math>n</math>
if (n==0) cout << 0;
while (n != 0)
{
  x = n%2;   // x - ostatni bit liczby n
  cout << x; // wypisywanie ostatniego bity liczby n
  n = n/2;   // n staje sie liczba po "oderwaniu" ostatniego bitu 
}
cout << endl;
  • Wczytywanie danych do tablicy
int Tablica[1000]; // deklracja tablicy zmiennych typu int
cin >> n; // wczytujemy rozmiar tablicy
for (int i=0; i<n; i=i+1)
{
   cin >> Tablica[i]; // wczytujemy ze standardowego wejścia liczbę typu int i zapamiętujemy ją w komórce Tablica[i]
}
  • Znajdowanie minimum w tablicy o rozmiarze n
// n - rozmiar tablicy
// tab - tablica liczb
int min, i;
min = tab[0];
for (i=1; i<n; i++) // przegladamy całą tablicę po kolei i jesli znajdujemy mniejszy element od aktualnego minimum, to uaktualniamy minimum
{
  if (tab[i] < min) min=tab[i];
}
  • Programowanie zadań na lekcji (punkty liczą się do aktywności; każde zadanie warte jest 2 punkty):
  • Zadanie domowe (kod CPP03) Tarasy (6 pkt)

Lekcja 11

2006.12.12
  • Sprawdzanie czy słowo jest palindromem
 int i,j, n;
 string s; // string to coś jakby tablica char'ów
 n = s.length(); // n = s.size(); <-- to to samo
 i = 0; j = n-1;

 bool czyPalindrom = true; // bool - to typ danych logicznych (true, false)
 while (i<j)
 {
    if (s[i] != s[j]) { czyPalindrom = false; break; }
    i++; j--;
 }


Lekcja 12

2006.12.19

Funkcje i procedury w C/C++

Sito Eratostenesa

Lekcja 13

2007.01.02
  • Programowanie zadań na SPOJ-u (aktywność na lekcji: każde zadanie za 4 pkt)
    • Imieniny
    • Binarny ciąg leksykograficzny
    • Liczby s-pierwsze
  • Powyższe zadania przechodzą jako zadania domowe (kod CPP05) na następny tydzień.

Lekcja 14

2007.01.09

Sorotwanie w czasie kwadratowym

  • algorytm SELECT-Sort (sortowanie przez wybór) <-- to ten z szukaniem maksimum
  • algorytm INSERT-Sort (sortowanie przez wstawianie) <-- to ten co na początku nic nie robi
  • Złożoność obu algorytmów to <math>O(n^2)</math>

Sorotwanie w czasie <math>O(n \log n)</math>

  • algorytm MERGE-Sort - sortowanie przez scalanie

'Kod źródłowy'

#include <iostream>
using namespace std;

const int SIZE = 1000000;

int tab[SIZE]; // tablica do posortowania
int tmp[SIZE]; // tymczasowa tablica (potrzebna przy scalaniu)

void merge(int *t, int a, int m, int b) // scala dwie połówki tablicy t[...]
{
   int x,y,z;
   x = a; 
   y = m+1;
   z = a;

   while(x<=m && y<=b)
     if (tab[x]<tab[y]) tmp[z++] = tab[x++];
     else               tmp[z++] = tab[y++];

   while(x<=m) tmp[z++] = tab[x++];
   while(y<=b) tmp[z++] = tab[y++];

   for (z=a; z<=b; z++) tab[z] = tmp[z]; // kopiujemy wypełnioną tablicę tmp do tablicy tab
}


void msort(int *t, int a, int b) // funkcja sortuje t[...] od indeksu 'a' do indeksu 'b'
{
   if (a==b) return;
   int m = (a+b)/2;
   msort(t,a,m);    // posortuj lewą połowe tablicy
   msort(t,m+1,b);  // posortuj prawą połowę tablicy
   merge(t,a,m,b);  // scal dwie posortowane połówki
}

int main(void)
{
   // przykład zastosowania tablicy msort;
   tab[0] = 56;
   tab[1] = 564;
   tab[2] = 256;
   tab[3] = 53;
   tab[4] = 1;
   tab[5] = 2;
   tab[6] = 908;
   tab[7] = 21256;
   tab[8] = 2156;
   tab[9] = 5324656;
   tab[10] = 53456;
   tab[11] = 56234;
   tab[12] = 12346;
   tab[13] = 82346;
   tab[14] = 116;

   msort(tab, 0, 14); // posortuj tablicę tab[0...14]
   for (int i = 0; i<=14; i++) cout << tab[i] << " "; // wypisz tablicę na std wyjście
/*
    Program wypisuje
    
    1 2 53 56 116 256 564 908 2156 12346 21256 53456 56234 82346 5324656
*/
}
  • Zadanie domowe (do 23 stycznia 2007 r.)
    • zmodyfikuj funkcję 'msort' oraz program podany na lekcji, aby wypisywał również ile wykonał porównań
    • Użyj swojego programu w celu wyznaczenia liczby porównań wykonanych przez algorytm MERGE-Sort przy sortowaniu następujących danych:
 1,2,3,4,5,6,7,8,9,10, 1,2,3,4,5,6,7,8,9,10, 1,2,3,4,5,6,7,8,9,10, ... , 1,2,3,4,5,6,7,8,9,10
 bloków 1,2,...,10 jest 40 000.


Obóz naukowy w Miliczu

2007.01.16

Jeśli jest ktoś chętny sporządzić notatki do wykładów i zadań przerobionych na obozie, to proszę się do mnie zgłaszać. Ja mogę udostępnić materiały na papierze.

Tutaj znajduje się contest (zawody) z obozu : Milicz, styczeń 2007


Struktury

2007.01.23

Temat: Struktury w C++. Definiowanie własnych operatorów w C++.

Lekcja 17

2007.02.13

Programowanie dynamiczne:

  • Zadania na lekcji : Sums in a triangle (3 pkt - aktywność), Długość najdłuższego wspólnego podciągu (3 pkt - aktywność)
  • Zadanie domowe (kod CPP06, termin do 2007.02.20):
    • Zadania z lekcji : (3 pkt) Sums in a triangle, (3 pkt) Długość najdłuższego wspólnego podciągu
    • (4 pkt) Street Parade
    • (5 pkt*) Trójkąty jednobarwne

Wszystkie zadania znajdują się na naszym klasowym CONTESTcie : [2].

Lekcja

Liga szkolna

2007.02.20

Grafy

2007.02.27

Grafy - wprowadzenie, oznaczenia i definicje. Kilka podstawowych twierdzeń.

Drzewa - własności i podstawowe twierdzenia

Konkurs

2007.03.06

Nie będę komentował wyników.

Wektory, grafy, sortowanie topologiczne

2007.03.20

Poznaliśmy typ

 vector<int> t;

Przeczytaj te notatki o wektorach.

Poznaliśmy metody

  1. size()
  2. resize(int n), resize(int n, int x)
  3. push_back(int x)
  4. clear()

Tutaj zamieściłem informacje o rozmiarze pamięciowym miliona pustych wektorów. Przyznaję rację Wiktorowi, że milion pustych wektorów zajmie sporo pamięci. Po przeczytaniu przekonasz się, że milion pustych wektorów zajmuje sporo pamięci - ok. 24 MB. Wygląda na to, że jeden wektor zajmuje ok 24 B, czyli aż 6 zmiennych rozmiarze 4B. Gdyby napisać własną strukturę vector, to zajęłaby około 12B (wskaźnik na początek tablicy - 4B, liczba elementów w tablicy - 4B, rozmiar dostępnej pamięci - 4B). Wówczas milion naszych struktur zająłby ok. 12 MB, a nie 24 MB. Wygląda na to, że STL, zabrał nam dwa razy więcej. Podsumuję to w taki sposób:

Za wygodę trzeba płacić pamięcią.

Wektory, grafy, sortowanie topologiczne c.d.

2007.03.27
  1. Struktura zbioru uporządkowanego jest opisana tutaj - Set
  2. Zadanie na lekcji: Porządek w grafie
  3. Zadanie domowe CPP08: Porządek w grafie, Porządek leksykograficzny w grafie

Przeglądanie grafu w głąb i wszerz

2007.04.03
  1. Kolejka : queue, deque
  2. Tutaj zamieściłem opis algorytmu przeglądania grafu w głąb - DFS
  3. Tutaj znajdziesz fajne animacje, które przedstawiają działanie obu algorytmów przeszukiwania : [3]
  4. Zadanie domowe (CPP09): Najkrotsza sciezka w DAG-u (3 pkt), Dwie cyfry silnii (3 pkt), Linknet (4 pkt*), Bitmap (3 pkt)

Algorytmy tekstowe

2007.04.17
  1. Omówienie zadania Najkrotsza sciezka w DAG-u
  2. Omówienie zadania Bitmap
  3. Rozpoczęliśmy tematykę związaną z algorytmami na słowach, tzw. algorytmami tekstowymi
    Na sam początek - trudny problem. Znajdowanie wzorca w tekscie
    Algorytm KMP
  4. Przedłużone zadanie domowe: Najkrotsza sciezka w DAG-u (75% * 3pkt), Linknet (50% * 4 pkt*), Bitmap (75% * 3 pkt)
  5. Zadanie domowe: Konferencje (3 pkt), Konferencje 2 (4 pkt*)
  6. Zadanie domowe: Napisz program obliczający funkcję prefiksową Knutha
    Np. dla tekstu aaabaabaaaba powinien wypisać liczby 0 1 2 0 1 2 0 1 2 3 4 5
a a a b a a b a a a b a
0 1 2 0 1 2 0 1 2 3 4 5

Funkcja prefiksowa Knutha

2007.04.24
  1. Zadanie na lekcji: Obliczanie funkcji prefiskowej Knutha - zadanie na SPOJU - Funkcja prefiskowa Knutha (3 pkt)
  2. Zadanie domowe  : Funkcja prefiskowa Knutha (3 pkt), Wyszukiwanie wzorca w tekscie (3 pkt)
  3. Zadania dodatkowe: Gra Euklidesa (3 pkt), Symbol Newtona (3 pkt)

KMP - ciąg dalszy

2007.05.08

Równoważność cykliczna dwóch słów

Dla słowa P[1..n] definiujemy rotację poprzez przestawienie pierwszej litery na jego koniec. W ten spobób otrzymujemy słowo : P[2..n] P[1]

Dwa słowa nazywamy równoważnymi cyklicznie, jeśli można pierwsze słowo sprowadzić do drugiego poprzez operacje rotacji.

  1. Problem
    1. dane: dwa słowa <math>u, v</math>
    2. wynik: TAK lub NIE w zalezności od tego, czy słowa <math>u, v</math> są równoważne cyklicznie
  2. Rozwiązanie
    1. Sprawdź, czy słowo <math>v</math> jest podsłowem słowa <math>u u</math>


Zadanie Szablon

Omówiliśmy i chyba rozwiązaliśmy zadanie Szablon (p. link poniżej).



Algorytmy tekstowe - ciąg dalszy

2007.05.15

Równoważność cykliczna dwóch słów

  • Na lekcji przedstawiony został algorytm działający w czasie liniowym i w miejscu, tj. o złożoności pamięciowej <math>O(1)</math>
bool equiv_cyc(const string &u, const string &v)
{
  int n = u.length(), i = -1, j = -1, k;
  if (n != v.length()) return false;
  
  while( i<n-1 && j<n-1 )
  {
    k = 1;
    while(k<=n && u[(i+k)%n]==v[(j+k)%n]) k++;
    if (k>n) return true;
    if (u[(i+k)%n] > v[(j+k)%n]) i += k; else j += k;
  }
  return false;
}

Minimalne słowo pokrywające

  • Algorytm o złożoności liniowej
int min_cover_word(const string &u, const vector<int> &pi)
{
  int n = u.length(); if (n==1) return 1;
  int S[n], Z[n];
  for (int i=1; i<n; i++) Z[i]=S[i]=i+1;
  for (int i=1; i<n; i++)
    if (pi[i]>0 && i-Z[S[pi[i]]]<S[pi[i]])
    {
      S[i] = S[pi[i]];
      Z[S[i]] = i;
    }
  return S[n-1];
}


na boisku

2007.05.22

Była piękna pogoda.

Programowanie

2007.05.29
  • Zadanie na lekcji : Zależności
  • Zadanie domowe z poprzedniej lekcji można do mnie wysyłać aż do czwartku 31 maja do godziny 19.00.
    Przypominam, że temat listu powinien być następujący : [XIVLO] [Ie:2] [Imię i nazwisko] [CPP14: Nazwa zadania]

Programowanie dynamiczne

Optymalne nawiasowanie iloczynu macierzy

Macierz A o rozmiarach <math>a\times b</math> możemy pomnożyć przez macierz B o rozmiarach <math>b\times c</math> wykonując mniej więcej <math>abc</math> operacji arytmetycznych. Niech liczba tych operacji będzie kosztem mnożenia macierzy A i B.

Twoim zadaniem jest, dla danych rozmiarów macierzy <math>A_1, A_2, ..., A_n</math> wyznaczyć optymalny koszt (minimalny) koszt obliczenia iloczynu <math>A_1 A_2 \cdots A_n</math>.

Przypomnienie: mnożąc macierz o rozmiarach <math>a\times b</math> przez macierz o rozmiarach <math>b\times c</math> otrzymujemy macierz o rozmiarach <math>a\times c</math>.

Rozwiązanie

  • Pomysł polega na obliczeniu dwuwymiarowej tablicy m[i,j] <math>1 \leq i \leq j \leq n</math>, dla której m[i,j] będzie optymalnym kosztem obliczenia iloczynu <math>A_i A_{i+1} \cdots A_j</math>
  • Obserwacja 1.
    m[i,i] = 0, dla i=1,2,...,n,
  • Obserwacja 2.
    m[i,j] = min( m[i,k] + p_{i-1}*p_k*p_j + m[k+1,j] : k=i,i+1,...,j-1 )

Zadanie domowe

Super zadanie dodatkowe

Można uzyskać ok. 15 pkt dodatkowych jeśli zrealizuje się następujące zadanie do 8 czerwca. Zadanie polega na wymyśleniu problemu. Widzieliście już wiele zadań z zawodów, więc nie będę pisał na czym polega problem.

  • Chodzi o to, aby ułozyć własne zadanie. Napisać jakąś treść, może być czysto matematyczna.
  • Należy przygotować testy (plik wejściowy i poprawny plik wyjściowy).
  • Należy przygotować własne rozwiązanie swojego problemu.
  • Proszę nie chwalić się pomysłem na zadanie swoim kolegom i koleżankom, gdyż ułożone przez was zadania będą w klasowym konkursie oraz na obozie.
  • Aby wasze pomysły się nie powtarzały, prosze wysyłać do mnie najpierw pomysł na zadanie, a ja ewentualnie będę go odrzucał jeśli pomysł ten się już powtórzył.
  • W razie pytań - prosze do mnie pisać.

Powrót do strony lekcji informatyki
Osobiste