Spotkanie 55. Podstawowe protokoły sieciowe

1. Protokół

Jest to zbiór procedur oraz reguł rządzących komunikacją, między co najmniej dwoma urządzeniami sieciowymi. Istnieją różne protokoły, lecz nawiązujące w danym momencie połączenie urządzenia muszą używać tego samego protokołu, aby wymiana danych pomiędzy nimi była możliwa.

W celu komunikacji między różnymi protokołami wykorzystuje łącza (ang. gateway) - czyli urządzenia, które tłumaczącą rozkazy jednego protokołu na drugi. Należy pamiętać, że używanie łącz może spowolnić w znacznym stopniu komunikację pomiędzy systemami. Kolejnym rozwiązaniem może być skonfigurowanie komputerów w taki sposób, by wykorzystywały kilka protokołów równocześnie, jednak i to rozwiązanie może prowadzić do dodatkowego obciążania sieci.

2. HTTP, HTTPS, FTP, SFTP, DNS, TELNET

HTTP (ang. HyperText Transfer Protocol) - to protokół internetowy, używany do obsługi stron WWW. HTTP stanowi podstawowy protokół, przy pomocy którego przebiega komunikacja między klientami i serwerami sieci Web. Jest to protokół poziomu aplikacji dla współpracujących ze sobą, hipermedialnych, rozproszonych systemów informacyjnych. HTTP jest bezstanowym i generycznym protokołem zorientowanym obiektowo. Cechą charakterystyczną tego protokołu możliwość wpisywania oraz negocjowania reprezentacji danych, co umożliwia budowę systemów niezależnie od typu transferowanych danych.

HTTPS (ang. Hypertext Transfer Protocol Secure) – szyfrowana wersja protokołu HTTP. W przeciwieństwie do komunikacji niezaszyfrowanego tekstu w HTTP klient-serwer, szyfruje go za pomocą protokołu SSL. Zapobiega to przechwytywaniu i zmienianiu przesyłanych danych.

HTTPS działa domyślnie na porcie nr 443 w protokole TCP. Wywołania tego protokołu zaczynają się od https://, natomiast zwykłego połączenia HTTP od http://. Protokół HTTPS jest warstwę wyżej (na transporcie SSL), najpierw następuje więc wymiana kluczy SSL, a dopiero później żądanie HTTP. Powoduje to, że jeden adres IP może serwować tylko jedną domenę lub też tylko subdomeny danej domeny (zależnie od przyznanego certyfikatu).

FTP (ang. File Transfer Protocol) - to protokół służący do transmisji plików. Przeważnie usługę ftp stosuje do przesyłania danych z odległej maszyny do lokalnej lub na odwrót. Protokół ten działa w oparciu o zasadę klient-serwer i korzystanie z usługi polega na użyciu interaktywnej aplikacji. Technologia FTP zapewnia ochronę stosując hasła dostępu.

DNS (ang. Domain Name Service) - protokół używany w sieci Internet obsługujący system nazywania domen. Umożliwia on nadawanie nazw komputerom, które są zrozumiałe i łatwe do zapamiętania dla człowieka, tłumacząc je na adresy IP. Nazywany czasem usługą BIND (BSD UNIX), DNS oferuje hierarchiczną, statyczną usługę rozróżniania nazw hostów. Administratorzy sieci konfigurują DNS używając listę nazw hostów oraz adresów IP. DNS nie posiada centralnego repozytorium przechowującego adresy IP maszyn w sieci. Dane dotyczące tych adresów dzielone są między wiele komputerów, zwanych serwerami DNS (nazw domenowych), które są zorganizowane hierarchicznie w formie drzewa. Początek drzewa nazywany jest korzeniem. Nazwy najwyższego poziomu składają się z dwuliterowych domen narodowych opartych na zaleceniach ISO 3166 (wyjątek stanowi brytyjska domen uk). Nadrzędna domena narodowa w Polsce oznaczona jest przez pl. Jeżeli chodzi o domeny trzyliterowe, ich znaczenie jest następujące:

• com - organizacje komercyjne
• gov - agencje rządowe
• edu - instytucje edukacyjne
• mil - organizacje wojskowe
• org - pozostałe organizacje
• net - organizacje, których działalność dotyczy sieci komputerowych

DHCP (ang. Dynamic Host Configuration Protocol) - to standardowy protokół przydzielający adresy IP poszczególnym komputerom. Serwer DHCP przypisuje adresy IP poszczególnym końcówkom.

TELNET - zadaniem protokołu Telnet jest zapewnienie komunikacji wielozadaniowej, dwukierunkowej, ośmiobitowej i zorientowanej bajtowo. Umożliwia połączenie ze sobą urządzenia terminalowego i procesu pozwalającego na jego obsługę.Telnet nie tylko pozwala użytkownikowi na zalogowanie się na zdalnym komputerze (uzyskanie dostępu poprzez podanie nazwy użytkownika i hasła), ale także na wywoływanie na nim poleceń. Tak więc użytkownik w Łodzi może połączyć się z hostem w Nowym Jorku i uruchamiać na nim programy tak, jakby faktycznie znajdował się przed tamtym komputerem.Telnet uruchamiany jest odpowiednim poleceniem, po którym następuje nazwa (albo adres numeryczny IP) hosta zdalnego. Połączenie będzie zaakceptowane bądź odrzucone z zależności od konfiguracji komputera zdalnego

Spotkanie 54. MODEL OSI; TCP/IP

1. OSI

OSI (ang. Open Systems Interconnection) lub Model OSI (pełna nazwa ISO OSI RM, ang. ISO OSI Reference Model – model odniesienia łączenia systemów otwartych) – standard zdefiniowany przez ISO oraz ITU-T opisujący strukturę komunikacji sieciowej.
Międzynarodowa Organizacja Normalizacyjna (ang. International Organization for Standardization) na początku lat osiemdziesiątych dostrzegła potrzebę stworzenia modelu sieciowego, dzięki któremu producenci mogliby opracowywać współpracujące ze sobą rozwiązania sieciowe. W taki sposób powstała specyfikacja Open Systems Interconnection Reference Model, która do polskich norm została zaadaptowana w 1995 roku.

Model ISO OSI RM jest traktowany jako model odniesienia (wzorzec) dla większości rodzin protokołów komunikacyjnych. Podstawowym założeniem modelu jest podział systemów sieciowych na 7 warstw (ang. layers) współpracujących ze sobą w ściśle określony sposób. Został przyjęty przez ISO w 1984 roku a najbardziej interesującym organem jest wspólny komitet powołany przez ISO/IEC, zwany Joint Technical Committee 1- Information Technology (JTC1). Formalnie dzieli się jeszcze na podkomitety SC.
Dla Internetu sformułowano uproszczony Model TCP/IP, który ma tylko 4 warstwy.


2. TCP/IP

Model TCP/IP (ang. Transmission Control Protocol/Internet Protocol) – teoretyczny model warstwowej struktury protokołów komunikacyjnych. Model TCP/IP został stworzony w latach 70. XX wieku w DARPA, aby pomóc w tworzeniu odpornych na atak sieci komputerowych. Potem stał się podstawą struktury Internetu.

3. Adres IP

Adres IP (ang. IP address) – w protokole IP liczba nadawana interfejsowi sieciowemu, grupie interfejsów (broadcast, multicast), bądź całej sieci komputerowej, służąca identyfikacji elementów sieci w warstwie trzeciej modelu OSI – w obrębie sieci lokalnej oraz poza nią (tzw. adres publiczny).

Adres IP nie jest "numerem rejestracyjnym" komputera – nie identyfikuje jednoznacznie fizycznego urządzenia – może się dowolnie często zmieniać (np. przy każdym wejściu do sieci Internet) jak również kilka urządzeń może dzielić jeden publiczny adres IP. Ustalenie prawdziwego adresu IP użytkownika, do którego następowała transmisja w danym czasie jest możliwe dla systemu/sieci odpornej na przypadki tzw. IP spoofingu (por. man in the middle, zapora sieciowa, ettercap) – na podstawie historycznych zapisów systemowych.
W najpopularniejszej wersji czwartej (IPv4) jest zapisywany zwykle w podziale na oktety zapisywane w systemie dziesiętnym i oddzielane kropkami, rzadziej szesnastkowym bądź dwójkowym(oddzielane dwukropkami bądź spacjami).

4. Maska podsieci i maska adresu

Maska podsieci, maska adresu (ang. subnetwork mask, address mask) – liczba służąca do wyodrębnienia w adresie IP części sieciowej od części hosta.
Pola adresu, dla których w masce znajduje się bit 1, należą do adresu sieci, a pozostałe do adresu komputera. Po wykonaniu iloczynu bitowego maski i adresu IP komputera otrzymujemy adres IP całej sieci, do której należy ten komputer.
adres = 128.10.2.3 = 10000000 00001010 00000010 00000011
maska = 255.255.0.0 = 11111111 11111111 00000000 00000000

Spotkanie 53. Sieci komputerowe.

1.Sieć komputerowa

Zbiór komputerów i innych urządzeń połączonych ze sobą kanałami komunikacyjnymi. Sieć komputerowa umożliwia wzajemne przekazywanie informacji oraz udostępnianie zasobów własnych między podłączonymi do niej urządzeniami, tzw. „punktami sieci”.

Topologia sieci komputerowej.Głównym przeznaczeniem sieci komputerowej – ideą dla której została stworzona i wciąż jest ulepszana i rozwijana – to ułatwienie komunikacji pomiędzy ludźmi, będącymi faktycznymi użytkownikami sieci. Sieć umożliwia łatwy i szybki dostęp do publikowanych danych, jak również otwiera techniczną możliwość tworzenia i korzystania ze wspólnych zasobów informacji i zasobów danych. W sensie prawnym, i w pewnym przybliżeniu, użytkownicy sieci komputerowej są również jej beneficjentami.

2.Topologia fizyczna - opisuje fizyczną realizację sieci komputerowej przez układ mediów transmisyjnych. 

Wyróżnia się następujące podstawowe układy:

• pierścień podwójny – komputery są połączone dwoma odcinkami kabla, np. FDDI;

• gwiazda – komputery są podłączone do jednego, centralnego punktu zwanego koncentratorem lub przełącznikiem;

pierścień – komputery są połączone pomiędzy sobą odcinkami kabla tworząc zamknięty pierścień, np. token ring;

magistrala – komputery współdzielą jeden nośnik kablowy;

hierarchiczna – struktura podobna do drzewa binarnego;

• siatka – sieć rozszerzona o połączenia nadmiarowe. Rozwiązanie stosowane w sieciach, w których jest wymagana wysoka niezawodność działania.

Spotkanie 52. Podstawowe komendy i polecenia w Linux

1. Polecenia związane z użytkownikami, grupami, loginami i 
zamykaniem systemu

• adduser (dodajemy nowego użytkownika)
• newgrp (dodajemy nową grupę)
• passwd (zmieniamy hasła)
• logout (wylogowanie się)
• who (sprawdzamy kto jest aktualnie zalogowany)
• users (j/w)
• w (j/w)
• whoami (sprawdzamy kim jesteśmy)
• mesg (zezwolenie na przyjmowania komunikatów)
• write (wysłanie wiadomości do danego użytkownika)
• wall (j/w tylko do wszystkich użytkowników)
• rwall (j/w tylko do wszystkich w sieci)
• ruser (wyświetla użytkowników pracujących w systemie)
• talk (możliwość interaktywnej rozmowy)
• finger(szczegółowe informacje o użytkownikach)
• su (zmieniamy się w innego użytkownika)
• chmod (zmieniamy parametry pliku)
• chown (zmieniamy właściciela pliku)
• chgrp (zmieniamy jaka grupa jest właścicielem pliku)
• shutdown(zamykamy Linuxa)

2. Polecenia związane z plikami i katalogami

Polecenia związane z katalogami

• ls (pokazuje nam zawartość katalogu)
• dir (okrojona wersja ls, pochodząca z msdos'a)
• pwd (pokazuje nam katalog w którym się znajdujemy)
• cd (zmieniamy katalog)
• rmdir (usuwamy katalog)
• mkdir (nowy katalog)

Polecfenia związane z plikami

• cat (edytowanie tekstu)
• rm (usuwamy plik(i))

Polecenia związane z kopiowaniem i przenoszeniem plików i katalogów

• mv (przenosimy plik lub zmieniamy jego nazwę)
• cp (kopiujemy plik)
• mvdir (przenosimy katalog lub zmieniamy jego nazwę)

3. Polecenia związane z procesami

• ps (pokazuje nam jakie procesy są aktualnie wykonywane)
• kill ("zabijamy" procesy)

4. Polecenia związane z pomocą

• help (wyświetla nam wszystkie polecenia w Linuxie)
• man (pokazuje nam pomoc do programu

Spotkanie 51. BIOS

BIOS – zapisany w pamięci stałej zestaw podstawowych procedur pośredniczących pomiędzy systemem operacyjnym a sprzętem. Posiada on własną pamięć, w której znajdują się informacje dotyczące daty, czasu oraz danych na temat wszystkich urządzeń zainstalowanych na naszym komputerze. Jest to program zapisany w pamięci ROM płyty głównej oraz innych kart rozszerzeń takich jak np. karta graficzna. Obecnie większość BIOS-ów zapisywana jest w pamięciach typu EEPROM, co umożliwia ich późniejszą aktualizację.


System operacyjny – oprogramowanie zarządzające systemem komputerowym, tworzące środowisko do uruchamiania i kontroli zadań użytkownika.
W celu uruchamiania i kontroli zadań użytkownika system operacyjny zajmuje się:

• planowaniem oraz przydziałem czasu procesora poszczególnym zadaniom,
• kontrolą i przydziałem pamięci operacyjnej dla uruchomionych zadań,
• dostarcza mechanizmy do synchronizacji zadań i komunikacji pomiędzy zadaniami,
• obsługuje sprzęt oraz zapewnia równolegle wykonywanym zadaniom jednolity, wolny od interferencji dostęp do sprzętu.

Przyjęto podział na trzy główne elementy budowy systemu operacyjnego:

• jądro systemu wykonujące i kontrolujące ww. zadania.
• powłoka – specjalny program komunikujący użytkownika z systemem operacyjnym,
• system plików – sposób zapisu struktury danych na nośniku.

Jądro składa się z następujących elementów funkcjonalnych:

• planisty czasu procesora, ustalającego które zadanie i jak długo będzie wykonywane,
• przełącznika zadań, odpowiedzialnego za przełączanie pomiędzy uruchomionymi zadaniami,
• Dodatkowo: 
• modułu zapewniającego synchronizacje i komunikację pomiędzy zadaniami,
• modułu obsługi przerwań i zarządzania urządzeniami,
• modułu obsługi pamięci, zapewniającego przydział i ochronę pamięci.
• innych zależnie od funkcji i przeznaczenia systemu

 System operacyjny jest odpowiedzialny za pracę komputera. Dzięki niemu na komputerze możemy wykonywać czynności. Na świecie powstało bardzo dużo systemów operacyjnych. Systemy operacyjne są najczęściej produkowane przez microsoft. System operacyjny pełni także funkcje ochronne komputera.

System plików – metoda przechowywania plików, zarządzania plikami, informacjami o tych plikach, tak by dostęp do plików i danych w nich zgromadzonych był łatwy dla użytkownika systemu.
  

Przykłady systemów operacyjnych:

Spotkanie 50. Kierunki rozwoju TI

Aspekty etyczne, prawne i społeczne w zastosowaniu informatyki

1. Historia informatyki.

1940-1949 zbudowano pierwsze komputery 1971 pierwsze mikroprocesory 1981, i 3 lata później Apple Macintosh, zmieniają wyobrażenie o komputerach

1994 pojawia się WWW
Rządy USA, W. Brytanii, Japonii i Nowej Zelandii zakładają serwery WWW,
w Internecie szybko pojawiają się sklepy, banki i stacje radiowe. 1995 firmy Internetowe pojawiają się na  1997 Moc obliczeniowa komputerów wzrasta do poziomu 1/10.000 ludzkiego mózgu.
komputery dowodzą twierdzenia, z którymi nie radzą sobie matematycy;
komputery coraz lepiej rozpoznają twarze i zamieniają mowę na tekst.

1998
po 3 latach rozwoju WWW jest wszędzie;
transakcje pomiędzy ludźmi a systemami sterowanymi głosem stają się częste; bazy danych przyjmują polecenia głosowe, są już komercyjne systemy do dyktowania tekstu;
samochodowe systemy nawigacyjne uzywają komputerowych map i GPS;
komputer prowadzi samochód bez udziału człowieka przez całe USA ze średnią szybkością 70 mil/h;


1999
sprzedaż firmy Intel przez WWW osiąga 1 mld $/miesiąc.
ewoluujące wirtualne Babyz, czyli sztuczna inteligencja w grach;
pierwsze roboty - zabawki, pieski AIBO;
superkomputery rzędu 1/1000 ludzkiego mózgu.
pierwsze eksperymenty pokazujące możliwość zbudowania kwantowego komputera;
przeszczepiono głowę małpie, można będzie przeszczepić głowę człowiekowi;
implanty do nerwu ucha stosuje się rutynowo; sztuczna siatkówka znajduje się w fazie testów,
sztuczne siatkówki i bezpośrednie podłączenie kamery do kory wzrokowej;

2000
zakończono 5 lat przed planowanym czasem mapowanie ludzkiego genomu; dla bioinformatyki moc komputerów to prawie wszystko;
komórki macierzyste wszczepione do mózgu zamieniają się w neurony;
urządzenia gospodarstwa domowego (lodówki, mikrofalówki) podłączone do Internetu;
automatyczne tłumaczenie stron WWW pomiędzy wieloma językami (niezłe chociaż niedoskonałe);


pierwsze roboty zaprojektowane przez komputerowe programy, zbudowane przez roboty, obserwowane w środowisku i automatycznie ulepszane przez programy oparte na algorytmach ewolucyjnych; pierwsze roboty rozpoznające emocje i reagujące w emocjonalny sposób;

W niektórych dziedzinach nauki ponad 90% czytanych prac pochodzi z Internetu; doskonałe archiwa specjalistyczne automatycznie indeksują wszystkie dostępne w Internecie prace oceniając je według liczby cytowań;


2. Przyszłość informatyki.
2030-2050
Co będzie możliwe za 30 lat? Nie mamy pojęcia!
Na pewno świat nie będzie podobny do dzisiejszego.

Za 1000 $ można kupić komputer (kwantowy?) o mocy rzędu 1000 mózgów;
3 wymiary są mało interesujące - ewolucja myśli przenosi się w światy wielowymiarowe;

upowszechniają się bezpośrednie połączenia z mózgiem, implanty i sterowanie myślami; dzięki implantom wirtualna rzeczywistość nie różni się od wrażeń realnych;

Rozwinie się Komputer DNA (biokomputer), w którym obliczenia zachodzą dzięki reakcjom chemicznym między cząsteczkami DNA..
roboty będą rozpoznawać emocje i będą reagować w emocjonalny sposób;
maszyny przechodzą test Turinga i twierdzą, że są świadome i większość ludzi to akceptuje;
cała sfera produkcji i większość usług jest w pełni zautomatyzowana;
osobowości ludzkie mieszają się ze sztucznymi - osiągnięta zostaje całkowita rozszerzalność umysłu, praktyczna nieśmiertelność. być może przeprowadzka z umysłu do umysłu sztucznego i odwrotnie będzie możliwa, być może sprzężenie pomiędzy umysłami stanie się na tyle silne, by powstał jeden umysł ...

3. Aspekty etyczne.
 W przyszłości możemy spotkać z twierdzeniem, że komputery znajdują się  na równi z żywym organizmem, posiadają pełną świadomość i będą odbierać bodźce emocjonalne. Spowoduje to problem natury etycznej, z którym będziemy musieli sobie poradzić.

4.Prawa autorskie.
Prawo autorskie  – pojęcie prawnicze oznaczające ogół praw przysługujących autorowi utworu albo zespół norm prawnych wchodzących w skład prawa własności intelektualnej, upoważniających autora do decydowania o użytkowaniu dzieła i czerpaniu z niego korzyści finansowej.

Przyjęta w 1994 roku ustawa o prawie autorskim i prawach pokrewnych reguluje między innymi przedmiot i podmiot prawa autorskiego, wyjątki i ograniczenia praw autorskich, okres obowiązywania praw autorskich oraz ochronę przedmiotu prawa autorskiego. Podstawowym założeniem jest rozróżnienie autorskich praw.

5.Licencje.
Licencja - dokument prawny lub umowa, określająca warunki korzystania z utworu, którego dana licencja dotyczy. Właściciel praw autorskich, znaku handlowego lub patentu może (i często to robi) wymagać od innych posiadania licencji jako warunku użytkowania lub reprodukowania licencjonowanego utworu.

• Licencja pełna - zezwolenie uprawnionego do korzystania z prawa przez licencjobiorcę w tym samym zakresie co uprawniony i jego posiadacz. 
• Licencja wyłączna - zezwolenie uprawnionego do wyłącznego korzystania z prawa na określonym terytorium lub polu eksploatacji prawa.
• Licencja niewyłączna - licencja która nie ogranicza grona licencjobiorców, dopuszczając wzajemną konkurencję.

Przykładowe zadania maturalne. Anagramy.

Przykładowe zadania maturalne. Palindromy.

Przykładowe zadania maturalne. Szyfrowanie.

Przykładowe zadania maturalne. Liczby cd.

Przykładowe zadania maturalne. Cyfry.

Przykładowe zadania maturalne. Liczby.

Przykładowe zadania maturalne.

Spotkanei 49. Szyfrowanie asymetryczne

1. Definicja szyfrowania asymetrycznego.
Kryptografia klucza publicznego (nazywana również kryptografią asymetryczną) - to rodzaj kryptografii, w którym używa się zestawów dwu lub więcej powiązanych ze sobą kluczy, umożliwiających wykonywanie różnych czynności kryptograficznych. Jeden z kluczy może być udostępniony publicznie bez utraty bezpieczeństwa danych zabezpieczanych tym kryptosystemem.

Algorytmy mające zastosowanie w kryptografii asymetrycznej wykorzystują operacje jednokierunkowe - takie, które da się łatwo przeprowadzić w jedną stronę a bardzo trudno w drugą. Np. mnożenie jest łatwe, a faktoryzacja trudna (na czym opiera się RSA). Potęgowanie modulo jest łatwe, a logarytmowanie dyskretne jest trudne (na czym opierają się ElGamal, DSA i ECC).

2. Najważniejsze zastosowania.
Najważniejsze zastosowania kryptografii asymetrycznej – szyfrowanie i podpisy cyfrowe – zakładają istnienie 2 kluczy – prywatnego i publicznego, przy czym klucza prywatnego nie da się łatwo odtworzyć na podstawie publicznego. W niektórych innych zastosowaniach kluczy może być więcej. 
  
3. Podpisy cyfrowe.
Strona uwierzytelniająca wylicza skrót (ang. hash) podpisywanej wiadomości. Następnie szyfruje ten skrót swoim kluczem prywatnym i jako podpis cyfrowy dołącza do oryginalnej wiadomości. Dowolna osoba posiadająca klucz publiczny może sprawdzić autentyczność podpisu, poprzez odszyfrowanie skrótu za pomocą klucza publicznego nadawcy i porównanie go z własnoręcznie wyliczonym na podstawie wiadomości.  

4. Schemat szyfrowania.

  Krok 1.
Alice przesyła do Boba swój klucz publiczny. 

 Krok 2 i 3.
Bob szyfruje wiadomość kluczem publicznym Alice, która to następnie  otrzymuje zaszyfrowaną wiadomość i rozszyfrowuje ją kluczem prywatnym.
 

Spotkanie 48. Szyfrowanie - wstęp

1. Szyfrowanie.

Metody szyfrowania tekstów oparte były głownie na zamianie i przestawianiu znaków lub symboli, a skuteczność utajniania zależała przede wszystkim od utrzymania w tajemnicy sposobu szyfrowania.Samą kryptologię można także postrzegać jako gałąź matematyki stosowanej i informatyki. Faktycznie w zastosowaniach informatycznych kryptologia nabiera praktycznego znaczenia w połączeniu z zagadnieniami dostępu do systemów operacyjnych, baz danych oraz sieci komputerowych i przesyłania danych.

2. Metody szyfrowania.

2.1. Szyfry przestawieniowe.

Szyfry te zmieniają uporządkowanie znaków w danych według pewnego schematu. Zazwyczaj dokonuje się przestawienia za pomocą pewnej figury geometrycznej. Szyfrowanie przebiega więc w dwóch krokach: tekst jawny wpisuje się do figury w sposób określony pewną tzw. ścieżką zapisu, a następnie odczytuje się go według określonego porządku (ścieżki odczytu) otrzymując tekst zaszyfrowany. Klucz obejmuje więc figurę geometryczną oraz ścieżki zapisu i odczytu.

Jako pierwszy przykład weźmy prosty szyfr płotowy. Litery tekstu jawnego zapisuje się tu tak, aby tworzyły kształt przypominający wierzchołek płotu zbudowanego ze sztachet. Tekst zaszyfrowany otrzymujemy odczytując kolejne wiersze tak utworzonej konstrukcji. Proces szyfrowania możemy przedstawić na prostym przykładzie. 

2.2. Szyfry podstawieniowe wieloalfabetyczne.

Stosuje się w nich wiele odwzorowań znaków tekstu jawnego na znaki kryptogramu, przy czym każde odwzorowanie jest z reguły typu jeden do jednego. Jak więc widzimy szyfry wieloalfabetyczne ukrywają rozkład częstości przez użycie wielu podstawień.

Szyfrowanie wiadomości przebiega tu na podstawie dowolnie wybranego słowa kluczowego (hasła). W przypadku znaków ASCI może to być dowolny ich ciąg. Do numeru każdego kolejnego znaku tekstu jawnego dodajemy numer odpowiadającego mu znaku słowa kluczowego i uzyskujemy znak kryptogramu. Gdy słowo kluczowe się skończy, bierzemy je kolejny raz od początku.

2.3. Szyfry podstawieniowe poligramowe.

Szyfry tego typu, w odróżnieniu od wyżej przedstawionych innych rodzajów szyfrów podstawieniowych, "obrabiają" jednocześnie większe grupy liter. Złamanie takiego szyfru jest zatem dużo trudniejsze dzięki odebraniu znaczenia częstości występowania liter lub znaków.

Dobrym, choć dosyć prostym, przykładem szyfru poligramowego jest szyfr Playfaira, wykorzystywany przez Anglików w czasie I wojny światowej. Kluczem jest tu macierz o wymiarach 5x5, w której skład wchodzą wszystkie litery alfabetu łacińskiego z wyjątkiem J. Użyjmy jako słowa-klucza słowa SZYFR. Zatem pierwszą czynnością będzie zapisanie liter alfabetu w kwadracie 5 x 5, zaczynając od słowa kluczowego i łącząc litery I oraz J.
 

 

Spotkanie 47. Odwrotna notacja Polska

1. Definicja ONP.
Odwrotna notacja Polska (ONP) (ang. RPN – Reverse Polish Notation) - zwana często również notacją Postfix, wymyślono w celu zapisywania dowolnych wyrażeń arytmetycznych bez nawiasów.

Notacja ONP jest szeroko wykorzystywana w kompilatorach języków wysokiego poziomu. Istnieją również języki, które do obliczeń stosują jedynie ONP – np. Forth.

W normalnym zapisie arytmetycznym operatory znajdują się pomiędzy argumentami:

2 + 2     6 - 4     3 * 5     12 / 3

Operatory posiadają priorytety, czyli "ważność". Jeśli w wyrażeniu wystąpią operatory o różnych priorytetach, to najpierw zostaną wykonane te ważniejsze:

3 + 5 * 2 = 3 + 10 = 13

Jeśli chcemy zmienić kolejność wykonywania działań, musimy używać nawiasów:

(3 + 5) * 2 = 8 * 2 = 16

W ONP problem ten nie występuje. Operator zawsze występuje po swoich argumentach:

2 2 +     6 4 -     3 5 *     12 3 /

Dzięki tej prostej zasadzie nawiasy stają się zbędne:

3 + 5 * 2 → 3 5 2 * + = 3 10 + = 13

(3 + 5) * 2 → 3 5 + 2 * = 8 2 * = 16

2. Zasada ONP.

Do obliczenia wartości wyrażenia zapisanego w ONP potrzebujemy stosu. Zasada jest następująca:

Wyrażenie ONP przeglądamy od strony lewej do prawej. Jeśli napotkamy liczbę, to umieszczamy ją na stosie. Jeśli napotkamy operator, to ze stosu pobieramy dwie ostatnie liczby, wykonujemy na nich działanie zgodne z napotkanym operatorem i wynik umieszczamy z powrotem na stosie. Gdy wyrażenie zostanie przeglądnięte do końca, na szczycie stosu będzie znajdował się jego wynik.

Przed przystąpieniem do zaprojektowania algorytmu ONP musimy poczynić pewne ustalenia. Dla prostoty umawiamy się, że używać będziemy tylko czterech operatorów arytmetycznych:

• + - dodawanie
• - - odejmowanie
• * - mnożenie
• / - dzielenie

 3. Przykład.

Spotkanie 46. Wyszukiwanie wzorca w tekście

1. Problem wyszukiwania wzorca.
W łańcuchu znakowym s znaleźć wszystkie wystąpienia wzorca p.

Problem Wyszukiwania Wzorca – WW (ang. pattern matching) to jeden z podstawowych problemów tekstowych, który intensywnie badali wybitni informatycy.

 2. Rozwiązanie.
Rozwiązaniem jest wskazanie w ciągu s wszystkich pozycji i takich, że zachodzi równość:

s[i : i + |p|] = p

Oznacza to, iż wzorzec p jest fragmentem łańcucha s występującym na pozycji i-tej.

Algorytm N – naiwny – ustawia okno o długości wzorca p na pierwszej pozycji w łańcuchu s. Następnie sprawdza, czy zawartość tego okna jest równa wzorcowi p. Jeśli tak, pozycja okna jest zwracana jako wynik, po czym okno przesuwa się o jedną pozycję w prawo i cała procedura powtarza się. Algorytm kończymy, gdy okno wyjdzie poza koniec łańcucha. Klasa pesymistycznej złożoności obliczeniowej algorytmu N jest równa O(n × m), gdzie n oznacza liczbę znaków tekstu, a m liczbę znaków wzorca. Jednakże w typowych warunkach algorytm pracuje w czasie O(n), ponieważ zwykle wystarczy porównanie kilku początkowych znaków okna z wzorcem, aby stwierdzić, iż są one niezgodne.

3. Rozwiązanie w C++

 

Spotkanie 45. Anagramy

1. Definicja anagramów.
Anagram - nazwa wywodząca się od słów greckich: ana- (nad) oraz grámma (litera), oznacza wyraz, wyrażenie lub całe zdanie powstałe przez przestawienie liter bądź sylab innego wyrazu lub zdania, wykorzystujące wszystkie litery (głoski bądź sylaby) materiału wyjściowego. W czasopismach szaradziarskich pojawiają się zadania polegające na odgadnięciu wykreskowanego anagramu na podstawie wierszowanego komentarza, a także anagramy rysunkowe polegające na ułożeniu hasła z wszystkich liter właściwego określenia rysunku.
Najprostszy anagram to poukładanie liter w odwrotnej kolejności, np. kebab – babek. Przykładem jednego z prostych przestawień jest zamiana sylab w wyrazie ranty, dająca anagram: tyran. Przestawiając pojedyncze litery możemy otrzymać np. anagram narty.

2. C++

 

Spotkanie 44. Problem plecakowy - programowanie zachłanne

Dyskretny problem plecakowy - jest jednym z najczęściej poruszanych problemów optymalizacyjnych. Nazwa zagadnienia pochodzi od maksymalizacyjnego problemu wyboru przedmiotów, tak by ich sumaryczna wartość była jak największa i jednocześnie mieściły się w plecaku. Przy podanym zbiorze elementów o podanej wadze i wartości, należy wybrać taki podzbiór by suma wartości była możliwie jak największa, a suma wag była nie większa od danej pojemności plecaka.

Problem plecakowy często przedstawia się jako problem złodzieja rabującego sklep – znalazł on N towarów; j–ty przedmiot jest wart oraz waży . Złodziej dąży do zabrania ze sobą jak najwartościowszego łupu, przy czym nie może zabrać więcej niż B kilogramów. Nie może też zabierać ułamkowej części przedmiotów (byłoby to możliwe w ciągłym problemie plecakowym).

Spotkanie 43. Anagramy w tekstach

Palindrom (gr. palindromeo – biec z powrotem) - wyrażenie brzmiące tak samo czytane od lewej do prawej i od prawej do lewej. Przykładem palindromu jest: Kobyła ma mały bok. Współcześnie palindromy pełnią funkcję gry słownej. Prawdopodobnie tak było również i w przeszłości, choć pewne znaleziska sugerują, że palindromy mogły też mieć znaczenie magiczne.

Spotkanie 42. Przybliżona wartość miejsca zerowego - metoda połowienia przedziałów.

1. Miejsce zerowe.
To argument x, dla którego funkcja przyjmuje wartość zero f(0)=0.

Naszym zadaniem jest znalezienie przybliżonej wartości miejsca zerowego, czyli punktu przecięcia wykresyu z osią Ox. Będziemy posługiwali się metodą "dziel i zwyciężaj".
Jednak aby algorytm działał poprawnie muszą być spełnione warunki:

• funkja f(x), której wykres jest linią ciągła w przedziale [p,q];
• wartość funkcji w punktach p i q są przeciwnych znaków, czyli spełniają warunki f(p) * f(q) < 0;

Spotkanei 41. Obliczanie pola obszaru ograniczonego wykresem funkcji.

Metoda całkowanie numerycznego - zajmuje się obliczaniem pola obszaru ograniczonego wykresem funkcji.

Wyróżniamy metody:

• prostokątów;

• trapezów;

Spotkanei 40. Metody numeryczne.

Spotkanie 39. Sortowanie przez scalanie. Sortowanie szybkie.

1. Sortowanie przez scalanie.
Metoda sortowania przez scalanie zaliczana jest do algorytmów wykorzystujących porównania. Jednocześnie jednak jest to metoda wykorzystująca ‘’dziel i zwyciężaj’ .

W tej metodzie wyróżniamy 2 etapy:

1. Podział - faza wykonywana jest rekurencyjnie , polega na podzieleniu ciągu na podciągi zawierające jedną wartość
2. Scalanie - realizowana jest podczas łączenia podciągów i polega na scalaniu ich, z jednoczesnym sortowaniem

Wynika stąd, że głównym celem jest tutaj scalenie dwóch uporządkowanych ciągów w jeden posortowany.

2. Sortowanie szybkie.
Metoda sortowania szybkiego jest oparta na następującej własności: jeśli w tablicy T [0…n-1] istnieje element o indeksie k taki, że wszystkie elementy o mniejszych numerach mają wartość mniejszą od T [k], to aby uzyskać posortowany ciąg, wystarczy osobno posortować elementy tablicy T[0…k-1] i T[k+1…n-1].

W każdym kolejnym kroku powtarzane są te same czynności, zmienia się tylko fragment ciągu, na którym wykonujemy określone operacje. Indeks pierwszego wyrazu oznaczamy jako lewy, ostatniego – prawy.

Realizacje każdego kroku algorytmu należy rozpocząć od wybrania wyrazu ŚRODKOWEGO , którego wartość wyznaczamy : srodek – T [(lewy+prawy/2].Znajdowanie wyrazów w ciągu do zmiany rozpoczynamy od wyrazów skrajnych : LEWY i PRAWY, a dalej przesuwamy się w stronę wyrazu środkowego SRODEK. Szukamy z lewej strony elementu T [i] mniejsze/równe srodek, a z prawej elementu T[j] większy/równy srodek. Po znalezieniu pary spełniającej podane warunki wykonujemy zamianę elementów T[i] z T[j]. Czynności te powtarzamy tak długo, aż indeksy I i J się spotkają, dochodząc z obsu stron do elementu srodek.