wejściePrzeważają wykonawcy formalni. "Informatyka"
Matematyczne podstawy informatyki
A.G. Gein
Konspekt
| NEWSPAPER_NUMBER | Wykład |
Wykład 1.Czym są „matematyczne podstawy informatyki”. Dlaczego informatyka jest często uważana za blisko spokrewnioną Informacja i jej kodowanie. Matematyka kodów. Kody korekcji błędów. Ekonomiczne kodowanie. |
|
| Wykład 2.Matematyczne modele wykonawców formalnych. Co to jest formalne przetwarzanie informacji? Finał żadnych maszyn. Co jest pierwsze: język czy wykonawca? Gramatyka języka. Rozpoznawane języki. Wersje uniwersalne korpusy (maszyna Turinga, maszyna pocztowa). |
|
| Wykład 3.Algorytm i jego własności. Nierozstrzygalność algorytmiczna. Obliczalność. Złożoność. | |
| Praca egzaminacyjna nr 1. | |
| Wykład 4. Wykresy... Wykresy i dwuznaki. W jakich zadaniach powstają? Różne własności grafów (Euler, Hamiltonian wiadomości, planarność, dwustronność). Sieci. Strumienie w sieciach. Reprezentacja graficzna. Podstawowe algorytmy na grafach. |
|
| Wykład 5. Modele logiczne w informatyce. Algebra zdań. Funkcje logiczne. Formy normalne. Pełny klasy funkcji logicznych. Obwody stykowe przekaźnika. Zawory. Modele matematyczne procesora i pamięci komputera. Predykaty i relacje. Algebra relacyjna. Podstawy teoretyczne relacyjny DBMS. Logiczne języki programowania i ich matematyczne podstawy. |
|
| Praca testowa nr 2. | |
| Wykład 6. Komputerowa teoria liczb i geometria obliczeniowa. Dlaczego potrzebujesz teorii liczb w komputerze? nauki? Wyścig na liczby pierwsze. Jak rozłożyć liczbę? Jaka jest różnica między geometrią teoretyczną a przetwarzanie danych? Dlaczego jest gładka na papierze, ale niezdarna na komputerze? Podstawowe zasady i algorytmy obliczeń geometria. |
|
| 23/2007 | Wykład 7. Ochrona informacji... Ochrona informacji symbolicznej. Co należy chronić? Podpis elektroniczny... Systemy weryfikacja. Kryptosystemy klucza publicznego. Ochrona informacje graficzne... Matematyka elektronicznych znaków wodnych. |
| 24/2007 | Wykład 8. Podstawy metod nauczania matematycznych podstaw informatyki. |
| Ostateczna praca |
Wykład 2.
Matematyczne modele wykonawców formalnych
„Grace jest chłodna w tym próżnym świetle”. Fraza ta została wymyślona przez komputer korzystający z jednego z pierwszych programów do generowania tekstów w językach naturalnych. Ale emocja przekazywana przez to zdanie jest oczywiście niedostępna dla komputera. A komputer nie może zrozumieć znaczenia tego wyrażenia. Ponieważ jest tylko formalnym wykonawcą.
W naszej świadomości społecznej słowo „formalny” ma zwykle negatywne konotacje. Nagradzamy urzędnika pogardliwym piętnem „formalisty”, który działa wyłącznie na podstawie udzielonych mu poleceń, nie chcąc zagłębiać się w istotę postawionego mu problemu.
Ale czy zawsze jest źle być formalnym wykonawcą? Czy właściciel pasterza będzie szczęśliwy, gdy na komendę „Fas!” jego czworonożny przyjaciel zastanowi się, czy zadzierać z bandytą. Albo gdy samolot w odpowiedzi na ruch pilota sterowego nadal leci tym samym kursem, ponieważ nie chcesz zawracać. A operator reaktora jądrowego, porzucając instrukcję, będzie nim kierował z kaprysu. Zgadzam się, że nawet osoba czasami musi być formalnym wykonawcą. Jeśli chodzi o urządzenia do automatycznego przetwarzania informacji, nieformalna ścieżka jest dla nich po prostu niemożliwa. Przypomnijmy, jak zauważono w Wykładzie 1, informatyka zajmuje się badaniem samych procesów zautomatyzowane przetwarzanie Informacja.
Przetwarzanie informacji (transformacja) to dość szeroko rozumiany proces informacyjny. Przetwarzanie informacji rozumiane jest jako pozyskiwanie nowych informacji z informacji istniejących lub przekształcanie formy prezentacji informacji.
Detektyw zebrał dowody i wskazał, kto popełnił przestępstwo. Matematyk porównał znane mu twierdzenia i udowodnił nowe twierdzenie. DI. Mendelejew sformułował prawo okresowe na podstawie informacji o właściwościach chemicznych pierwiastków. We wszystkich tych przykładach w wyniku przetwarzania informacji pojawiły się nowe informacje.
Obliczenie sumy dwóch liczb należy również uznać za przetwarzanie informacji - wszak z dwóch znanych danych uzyskuje się nową, wcześniej nieznaną. Przetwarzaniem informacji jest np. tłumaczenie zdania z języka rosyjskiego na język obcy.
Na pierwszy rzut oka, pomiędzy procesami przetwarzania informacji wskazanymi w dwóch poprzednich akapitach, duża różnica... Główna różnica polega na tym, że w przypadku poszukiwania przestępcy lub udowodnienia nowego twierdzenia nie ma i nie można określić ścisłych reguł dotyczących sposobu przetwarzania wstępnych informacji. Jak mówią, osoba w tych przypadkach działa heurystycznie... Dodając dwie liczby, kierujemy się już sztywno określonymi zasadami. Taką pracę można powierzyć urządzeniu technicznemu, które jest w stanie zrozumieć i wykonać określone dla niego instrukcje. Urządzenia sterowane przez instrukcje i wykonujące swoją pracę automatycznie nazywane są programowalnymi i mówi się, że formalnie wykonują swoją pracę.
W szczególności możemy mówić o formalnym przetwarzaniu informacji. Wykonawca dokonujący takiego przetwarzania nie powinien zagłębiać się w znaczenie wykonywanych przez niego czynności; w związku z tym formalne przetwarzanie informacji co do zasady dotyczy zmiany formy ich prezentacji, a nie treści.
Tak więc wygodnie jest rozumieć przetwarzanie informacji jako każdą transformację ich treści lub formy prezentacji.
Jednak bez względu na sposób przetwarzania informacji – formalny czy heurystyczny, coś lub ktoś wykonuje to przetwarzanie. Zwykle nazywa się to wykonawca.
Formalni wykonawcy mogą być aranżowani na bardzo różne sposoby. Do ich badania, jak w każdej nauce, stosuje się modelowanie. Jakie modele matematyczne są wykorzystywane do badania wykonawców formalnych, powiemy w tym wykładzie.
§ 3. Wykonawca formalny: automat
Człowiekowi bardzo udaje się tworzyć różnorodne urządzenia, które wykonują tę czy inną pracę zgodnie z jasnymi instrukcjami. Jednocześnie nie jest już zobowiązany do ciągłego przebywania w pobliżu tego urządzenia, aby je kontrolować. W tym przypadku mówią, że urządzenie wykonuje pracę automatycznie, a samo urządzenie nazywa się automatyczny.
W rzeczywistości maszyny są bardzo różne. Może to być automat biletowy do pociągów podmiejskich, automat do napełniania gotowych produktów lub automat do produkcji dowolnych części. Automaty tego drugiego typu są często nazywane roboty przemysłowe.
Z punktu widzenia informatyki nie ma znaczenia, z czego zbudowana jest maszyna. Ważne jest tylko to, że odbiera niektóre sygnały jako rozkazy i za każdym rozkazem wykonuje jakąś akcję, przechodząc z jednego stanu do drugiego. Dlatego możemy założyć, że każdy automat opisany jest zbiorem możliwych stanów, listą poprawnych poleceń oraz wyliczeniem stanu, z którego automat przechodzi pod wpływem każdego polecenia. Na przykład, jeśli są tylko dwa polecenia, można je oznaczyć literami, powiedzmy, a oraz b lub cyframi stan maszyny - literami Q 1, Q 2, ..., qm, a opcje przejścia z jednego stanu do drugiego można wyliczyć za pomocą tabeli (patrz Tabela 1).
Tabela 1
Komórka na przecięciu wiersza i kolumny wskazuje stan, w który wchodzi automat, który był w stanie wskazanym w nagłówku tej samej kolumny i otrzymał polecenie wskazane w nagłówku tego samego wiersza. Dla każdego jest jasne, że taka tabela jest modelem informacyjnym prawdziwego automatu.
Automat można również opisać innym modelem informacyjnym, digrafem *. Wierzchołki dwugrafu to stany automatu, łuki to przejścia z jednego stanu do drugiego. Każdy łuk ma znacznik wskazujący polecenie wykonania przejścia. Następnie automat opisany w tabeli 2 jest wyświetlane, jak pokazano w Ryż. 1.
Tabela 2
Jeden ze stanów nazywa się stanem początkowym - to w nim maszyna znajduje się przed rozpoczęciem pracy. Zgódźmy się zawsze oznaczać stan początkowy Q 1. Niektóre stany są ostateczne - wprowadzenie automatu w ten stan ma na celu sterowanie automatem za pomocą takiej lub innej sekwencji poleceń. Na przykład, jeśli jest to automat biletowy, w stanie początkowym oczekuje, że monety zaczną wchodzić do akceptora monet. Istnieją dwa stany końcowe: wystawienie biletu i zwrot pieniędzy. Do tego dochodzą stany pośrednie – liczące ilość pieniędzy przelanych do automatu do tej chwili. Polecenia przenoszące maszynę z jednego stanu do drugiego to wrzucenie monety do wrzutnika monet, wciśnięcie przycisku wystawienia biletu lub wciśnięcie przycisku zwrotu pieniędzy. Fakt, że stan ten jest ostateczny, będzie oznaczony literą K w nawiasie przy oznaczeniu tego stanu. Na przykład, Q 2 (K).
Oczywiste jest, że celem sterowania automatem jest wydanie mu takiej sekwencji poleceń, która przenosi go ze stanu początkowego do końcowego. Ponieważ każde polecenie jest oznaczone literą, zestaw poleceń rozumianych przez tę maszynę można uznać za jakiś alfabet A... Następnie sekwencja poleceń, czyli program zostanie zapisany jako słowo w tym alfabecie. Na przykład słowo aba tłumaczy automat opisany w tabeli. 2, od stan początkowyQ 1 w stanie Q 4 . Można powiedzieć, że słowo aba określa na wykresie danego automatu pewną trasę ze stanu Q 1 w stanie Q 4 .
Zbiór wszystkich tych słów przenoszących automat ze stanu początkowego do jednego ze stanów końcowych tworzy rodzaj języka formalnego. Ten język nazywa się język rozpoznawany przez tę maszynę!... Jeśli dla jakiegoś języka istnieje przynajmniej jeden automat, który rozpoznaje ten język, to taki język nazywa się rozpoznawalny.
Na Ryż. 2 przedstawia automat mający dwa stany - Q 1 (K) i Q 2 - i rozumie dwa polecenia, które są oznaczone cyframi 0 i 1. Łatwo się domyślić, że język rozpoznawany przez tę maszynę składa się z tych i tylko tych słów, które zawierają parzystą liczbę jedynek i dowolną liczbę zer. Innymi słowy, ten automat oblicza sumę cyfr w liczbie zapisanej w system binarny rachunek.
Teraz miejmy stały alfabet A, oraz L- jakiś zestaw słów, składający się z symboli danego alfabetu. Czy zawsze można zbudować taki automat, aby zestaw L czy był to dla niego rozpoznawalny język? Odpowiedź brzmi nie.
Twierdzenie. Zostawiać A = {a, b}, L = {a n b n, gdzie n mieści się w zbiorze wszystkich liczb naturalnych). Wiele L nie jest uznanym językiem.
Nagranie jakiś występujące w stwierdzeniu tego twierdzenia oznacza, że litera a powtarzający się n pewnego razu.
Dowód twierdzenia wykorzystuje jedną z najważniejszych metod matematycznych - przez sprzeczność. Załóżmy więc, że L- rozpoznawany język. Oznacza to, że istnieje automat, który można przełożyć na jakiś stan końcowy dowolnym słowem tego języka. Niech ten automat ma k państw. Rozważ słowo a k b k... Należy do języka L a zatem przenosi ten automat ze stanu początkowego Q 1 do pewnego stanu końcowego Q s. Od listu a powtarza się co najmniej tyle razy, ile stanów automatu, jest taki stan Q t, który dla pierwszego k aplikacje listu a zostanie przekazany dwukrotnie (patrz. Ryż. 3). Niech automat wejdzie w stan po raz pierwszy Q t w wyniku zastosowania a ty, a następnym razem będzie w tym samym stanie po złożeniu wniosku a ty + v... Rozważ słowo K + v b k... Oczywiste jest, że zastosowanie tego słowa do stanu początkowego Q Umieszczę go w tym samym stanie końcowym Q s. Oznacza to, że dane słowo jest również rozpoznawalne przez dany automat, a zatem musi należeć do języka L... Ale w wielu L nie ma takiego słowa. Wynikająca z tego sprzeczność pokazuje, że przyjęte założenie jest błędne, tj. maszyna dla której dany zestaw służyłby jako rozpoznawalny język nie istnieje.
Ryż. 3. Trasa na wykresie automatu od stanu początkowego Q 1 do stanu końcowego Q s (określić Q litera t a stoi na łukach ty czas, na pętli - więcej v pewnego razu)
Ponieważ nie każdy zestaw słów jest rozpoznawalnym językiem, pojawia się pytanie, które zestawy są do tego odpowiednie. Znaleziono matematyków dogodne sposoby opisy uznanych języków, a metody te stanowiły podstawę do projektowania wszystkich obecnie istniejących języków programowania.
Pytania i zadania
1. Jakie dwa modele informacji może reprezentować automat?
2. Jaki jest język rozpoznawany przez to urządzenie?
3. Jaki język nazywa się rozpoznawalnym?
4. Dla maszyny pokazanej na Ryż. 1, określ, w jakim stanie będzie po wykonaniu sekwencji poleceń
a) Abba; v) babaabaaa;
b) ababbabb; G)* a n b n.
5. Dla maszyny pokazanej na Ryż. 2, zrób opis w formie tabeli.
6. Wykres jako wykres model informacyjny maszyna określona w tabeli. 3.
Tabela 3
7. Jaki język ponad dwuliterowym alfabetem (0, 1) rozpoznaje maszyna pokazana w Ryż. 4?
Ryż. 4
8. Jaki język nad dwuliterowym alfabetem ( a, b) jest rozpoznawany przez automat podany w tabeli. 3?
9. Narysuj w formie wykresu model informacyjny automatu rozpoznającego język po alfabecie (0, 1), składający się ze wszystkich słów zawierających dokładnie 5 kolejnych słów.
10. Narysuj w formie wykresu model informacyjny automatu, który rozpoznałby język po alfabecie (0, 1), składający się ze wszystkich słów zawierających dokładnie 5 jednostek.
11. Przedstaw w postaci grafu model informacyjny automatu, który rozpoznałby język po alfabecie (0, 1), składający się ze wszystkich słów zaczynających się od jedynki (czyli automat ten rozróżnia liczby naturalne zapisane w liczbie binarnej system z dowolnych sekwencji znaków 0 i 1).
12. Wśród języków wymienionych poniżej L 1 , L 2 , L 3 , L 4, zdefiniowane nad dwuznakowym alfabetem (1; 2), wskazują, które są rozpoznawane. Dla każdego z rozpoznawanych języków zbuduj automat, który go rozpoznaje, dla każdego z nierozpoznawalnych udowodnij, że jest nierozpoznawalny.
a) L 1 składa się ze wszystkich słów, które są nawet liczbami naturalnymi, zaczynając od liczby 1;
b) L 2 składa się ze wszystkich słów, których liczba jednostek jest liczbą naturalną kończącą się cyfrą 3;
v) L 3 składa się ze wszystkich słów, w których liczba dwójek jest liczbą pierwszą;
G) L 4 składa się ze wszystkich słów, które są liczbami naturalnymi podzielnymi przez 3.
13. Jaka jest różnica z punktu widzenia informatyki „w życiu według praw” i „w życiu według pojęć”?
§ 4. Uniwersalny wykonawca
Gry komputerowe... Chyba każdy, kto kiedykolwiek miał do czynienia z komputerem, widział, a być może sam, w jakąkolwiek grę komputerową. Na ekranie niektóre obiekty w postaci żywych istot lub urządzeń technicznych wykonują polecenia gracza, innymi steruje komputer, który wykonuje zaprogramowany program... Wszystkie te obiekty są wykonawcami formalnymi, każdy z własnym zestawem dopuszczalnych działań. Tylko te obiekty nie są prawdziwe, ale symulowane przez komputer. Okazuje się, że przy pomocy jednego formalnego wykonawcy naśladuje się innych.
Jeśli spróbujesz sformułować, co to znaczy, że jeden wykonawca jest naśladowany z pomocą innego, otrzymasz następujące. Mówią, że formalny wykonawca A imituje formalnego wykonawcę V, Jeśli
Do każdego obiektu, na którym wykonawca wykonuje czynności V, jednoznacznie odpowiada obiektowi, na którym wykonawca wykonuje czynności A(imitacja środowiska wykonawcy);
Do każdego dozwolonego działania wykonawcy V nad takim czy innym obiektem środowiska dopuszczalne działanie wykonawcy jest jednoznacznie kojarzone A nad odpowiednim obiektem jego otoczenia (imitacja działań);
Każda instrukcja napisana dla wykonawcy V i prowadząc w trakcie jego realizacji do określonego rezultatu (tj. do określonego stanu środowiska wykonawcy i jego samego), może zostać przekształcony przez naśladowanie dopuszczalnych działań w instrukcję dla wykonawcy A, którego wykonanie prowadzi do odpowiedniego wyniku w środowisku wykonawcy A.
Jednak założenie, że wykonawcy A oraz V odmienne środowisko, w którym one istnieją, nie jest zasadniczo z punktu widzenia informacji. Na przykład wykonawca A zajmuje się liczbami i V transformuje obrazy graficzne... Ale już wiesz, że tak naprawdę w każdym z tych przypadków mówimy o przekształceniu odpowiednio zakodowanej informacji. Ponadto można założyć, że używany jest ten sam kod binarny. W tym sensie możemy przyjąć, że środowisko performera jest po prostu takie samo – informacja przedstawiona w formie zakodowanego komunikatu.
Jedno z najważniejszych pytań w informatyce teoretycznej brzmi: czy istnieje taki formalny wykonawca, za pomocą którego można naśladować każdego formalnego wykonawcę? Nazywanie się takim wykonawcą jest naturalne uniwersalny... Łatwo zrozumieć, że jako urządzenie fizyczne uniwersalny wykonawca nie istnieje – w końcu informacje można zakodować w dowolnych długich wiadomościach, a każdy nośnik fizyczny jest skończony. Jeśli mówimy o uniwersalnym performerze jako idealnym przedmiocie, to okazuje się, że odpowiedź na zadane pytanie brzmi tak. I uzyskali go niemal jednocześnie i niezależnie dwaj wybitni naukowcy - A. Turing (w 1936) i E. Post (w 1937). Zaproponowani przez nich wykonawcy różnili się od siebie, ale okazało się, że potrafili się naśladować, a co najważniejsze, naśladować w ogóle każdego formalnego wykonawcę.
Zwyczajowo nazywa się uniwersalnego wykonawcę maszyną. Zwyczajem jest również nadawanie maszynom nazwisk ich wynalazców. Tak więc uniwersalny wykonawca wymyślony przez A. Turinga nazywa się maszyną Turinga; performer opisany przez E. Posta jest maszyną Posta. Później pojawili się inni uniwersalni wykonawcy, na przykład maszyna Minsky.
Możemy więc założyć, że mamy wiadomość napisaną jakimś alfabetem i trzeba ją przekonwertować na inną wiadomość. Oczywiście napisanie instrukcji dla formalnego wykonawcy, aby przetworzył określoną parę wiadomości, nie jest trudną sprawą. Ale już wiesz, że instrukcje (tj. algorytmy), które pozwalają rozwiązać całą klasę problemów tego samego typu - tak zwaną „właściwość masowego charakteru algorytmu”, są naprawdę interesujące. Na przykład takie zadanie: przypisać do prawej jeszcze jeden predefiniowany znak do dowolnej wiadomości. Jeśli, powiedzmy, ciąg identycznych znaków działa jak kod liczby naturalnej – liczba znaków w ciągu jest zakodowaną liczbą naturalną – to tak naprawdę mówimy o stworzeniu algorytmu zwiększania liczby o 1.
Naturalne jest myślenie, że wiadomość jest nagrana na taśmie. Co więcej, wygodniej sobie wyobrazić, że ta taśma jest podzielona na identyczne komórki, a każda komórka zawiera dokładnie jeden symbol wiadomości. Ponieważ wiadomości mogą być tak długie, jak nam się podoba, zgadzamy się wyobrazić sobie taśmę jako niekończącą się. Puste komórki będą traktowane jako wypełnione spacją. Dlatego zadeklarowaliśmy, że każdy alfabet, który będzie używany przez nas do pisania wiadomości na tej taśmie, musi zawierać „spację”. Umówmy się to wyznaczyć a 0. Pozostałe znaki alfabetu używane do nagrywania wiadomości na taśmie zostaną oznaczone a 1 , a 2 , ..., a n. Jeśli na przykład musimy zapisać problem obliczenia sumy dwóch liczb, to alfabet można przyjąć w następujący sposób: a 0; 1; 2; 3; 4; 5; 6; 7; osiem; dziewięć; 0; ,; +; =. W przypadku określonej pary danych (tj. dwóch liczb) wpis na taśmie może wyglądać na przykład tak, jak pokazano na Ryż. 5.
Ryż. 5
Oczywiście nie napiszemy symbolu na taśmie w pustych komórkach a 0, co oznacza, że tam. Ponadto zgadzamy się, że pierwszy znak wiadomości, poza spacją, zawsze pojawia się w tej samej komórce - on Ryż. 4 jest oznaczony . Ta komórka będzie nazywana początkową.
Wiadomość nagrana na taśmie jest przetwarzana przez jakieś urządzenie, a wynik jest zapisywany z powrotem na taśmie. Ponieważ wykonawca jest formalny, nie zagłębia się w znaczenie przekazu, ale zgodnie z opracowanymi dla niego instrukcjami zastępuje niektóre symbole innymi. Nie interesuje nas to, jak fizycznie odbywa się taka zamiana, więc możemy sobie wyobrazić, że po taśmie porusza się pewien automat, który odczytuje znak z komórki na taśmie, przetwarza otrzymane informacje, drukuje inny znak w komórce ( jeśli tak określa instrukcja) i przechodzi do sąsiedniej komórki - w prawo lub w lewo.
Wiesz już, że każdy automat opisany jest zbiorem stanów. Zwyczajowo stany określonej maszyny drukującej czytnik oznacza się literami Q 0 , Q 1 , Q 2 , ..., Q m. W takim przypadku zgadzamy się, że gdy maszyna jest włączona, tj. na początku pracy jest zawsze w tym samym stanie, który będziemy oznaczać Q 0 i znajduje się naprzeciwko komórki początkowej.
Tak więc maszyna Turinga jest formalnie opisana za pomocą zestawu dwóch alfabetów: A = {a 1 , a 2 , ..., a) oraz Q = {Q 0 , Q 1 , Q 2 , ..., Q m). Alfabet A nazywa zewnętrzny i służy do nagrywania oryginalnych wiadomości, alfabetu Q nazywa wewnętrzny i opisuje zestaw stanów czytnika-urządzenia drukującego. Przedstawimy maszynę Turinga, jak pokazano na Ryż. 6.
Ryż. 6
Na Ryż. 6 przedstawia moment działania maszyny Turinga, kiedy urządzenie odczytująco-drukujące przegląda trzecią komórkę od pierwotnej (w tym momencie był symbol i tak 3) i jest w stanie q k.
Zatem dopuszczalne działania maszyny Turinga są następujące:
Wpisz dowolny znak alfabetu zewnętrznego w sekcji taśmy (znak, który był tam wcześniej, zostanie nadpisany);
Przejdź do sąsiedniej sekcji;
Zmień stan na jeden z symboli wskazanych przez wewnętrzny alfabet;
Przestań pracować (przestań).
Oczywiście w tym wyliczeniu w każdym wierszu nie jest wskazana jedna akcja, ale grupa akcji tego samego typu - akcje „zapisz symbol alfabetu zewnętrznego” tyle, ile tych symboli, możesz przejść do następnej sekcji po prawej lub po lewej stronie jest tyle akcji, aby zmienić stan, ile tych stanów (tj. ile znaków alfabetu wewnętrznego).
Teraz trzeba powiedzieć, w jaki sposób rejestrowane są polecenia wykonania określonych czynności. Każde polecenie maszyny zawiera co najwyżej jedną akcję z każdej grupy akcji i ma postać
W rzeczywistości polecenia wyglądają tak:
ja Q j - napisz do sprawdzanej sekcji a i, przejdź w prawo (do następnej sekcji) i przejdź do stanu Q J;
ja Q j - napisz do sprawdzanej sekcji a ja, przesuń się w lewo i przejdź do stanu Q J;
a ja S Q j - napisz do sprawdzanej sekcji ai, zatrzymaj się i jedź do stanu Q J.
Do wykonywania działań maszyna Turinga ma jednostkę operacyjno-logiczną. Blok ten posiada dwa wejścia: przez jedno otrzymujemy informację o tym, który symbol znajduje się w monitorowanej komórce, przez drugie – informację o stanie maszyny na tym etapie jej pracy. Informacje te jednoznacznie określają, które polecenie ma wykonać maszyna. Ponieważ polecenie może zawierać wskazanie wykonania trzech akcji – zapisania znaku na taśmę, przesunięcia i zmiany stanu – blok operacyjno-logiczny ma trzy wyjścia: zapisanie znaku A, zrównoważyć m i zmiana stanu Q(cm. Ryż. 7).
Ryż. 7. Blok operacyjno-logiczny maszyny Turinga
Ponieważ blok ten ma tylko dwa wejścia, wygodnie jest przedstawić jego reakcję na dostarczone mu znaki w postaci tabeli prostokątnej, w której wiersze i kolumny są oznaczone symbolami odpowiednio alfabetu zewnętrznego i wewnętrznego (patrz Tabela 4) . Polecenia są zapisywane w komórkach tabeli. Jeśli samochód znajduje się naprzeciwko komórki, w której jest napisane ja, a jego stan to q j, to polecenie jest wykonywane na przecięciu linii oznaczonej symbolem ai, a kolumna oznaczona q j.
Tabela 4
Ta tabela nazywa się schemat funkcjonalny ta maszyna; pełni również rolę instrukcji (programu) dla maszyny Turinga. Z tego w szczególności możesz zobaczyć, jakie są zewnętrzne i wewnętrzne alfabety maszyny.
Załóżmy na przykład, że na taśmie zapisana jest sekwencja o określonej ilości tego samego znaku „*”. Następnie schemat funkcjonalny przedstawiony w tabeli. 5 powoduje, że maszyna Turinga zwiększa liczbę gwiazdek w tej sekwencji o jeden.
Tabela 5
Nie da się udowodnić, że maszyna Turinga jest uniwersalnym wykonawcą. W ten sam sposób, na przykład, nie da się udowodnić prawa zachowania energii w fizyce. Jednak praktyka kompilowania algorytmów pokazuje, że każdy problem, który dana osoba może dziś rozwiązać, można zaprogramować na maszynie Turinga. Ten eksperymentalny fakt, zwany tezą Turinga, jest sformułowany w następujący sposób: dla problemu istnieje algorytm rozwiązania wtedy i tylko wtedy, gdy istnieje odpowiednia maszyna Turinga, za pomocą której można rozwiązać ten problem.
Pytania i zadania
1. Jaki formalny wykonawca nazywa się uniwersalnym?
2. Co to jest maszyna Turinga?
3. Czym różni się jedna maszyna Turinga od drugiej?
4. Co nazywa się schematem funkcjonalnym maszyny Turinga?
5. Czy to prawda, że maszyna Turinga z napisanym dla niej schematem funkcjonalnym jest automatem skończonym?
6. Przedstaw w formie sekwencji figur, jak zmieniają się informacje na taśmie podczas pracy maszyny Turinga, co opisuje schemat funkcjonalny w tabeli. 5.
7. Zgodnie ze schematem funkcjonalnym opisanym w tabeli. 5, maszyna Turinga jest przypisywana podana sekwencja gwiazdki jeszcze jedna gwiazdka po lewej stronie. Sporządź schemat funkcjonalny, zgodnie z którym gwiazdka zostanie przypisana po prawej stronie podanej sekwencji.
8. Działanie maszyny Turinga opisuje poniższy schemat funkcjonalny:
Ustal, jaki komunikat będzie na taśmie po zakończeniu pracy maszyny i wskaż naprzeciw której komórki w tym momencie będzie znajdował się jej blok do zapisywania.
Ryż. osiem
Ryż. dziewięć
9. Taśma maszyny Turinga zawiera wiersz składający się z kilku kolejnych znaków „*”, po których następuje kilka znaków „#”, a na końcu wiersza znajduje się znak „e” (jeden z możliwe opcje taka linia jest podana na Ryż. 5).
Ryż. dziesięć
Dla każdego z poniższych schematów funkcjonalnych określ, które zadanie ma rozwiązać. (Wskazówka: aby uzyskać przekonującą odpowiedź, zastosuj diagram funkcjonalny do różnych opcji wypełniania kanału informacyjnego sekwencjami znaków z zewnętrznego alfabetu.)
10. Niech zewnętrzny alfabet składa się z symbolu „ a 0” i cyfry 0, 1, 2, ..., 9. Na taśmie zapisywana jest liczba naturalna. Pomyśl o maszynie Turinga i sporządź dla niej schemat funkcjonalny, według którego liczba ta zostanie zwiększona o 1.
11. Niech zewnętrzny alfabet składa się z symbolu „ a 0 ”i cyfry 0, 1, 2, ..., 9. Na taśmie zapisana jest liczba naturalna. Zrób schemat funkcjonalny maszyny Turinga, za pomocą którego na taśmie zostanie zapisana suma cyfr tej liczby. Odpowiedź musi być napisana po prawej stronie oryginalnej liczby, oddzielona od niej spacją.
Ryż. 11
PS Poczucie się jak maszyna Turinga jest przydatne, ale męczące. Zalecamy wykonywanie zadań 8 i 9 ręcznie. W przypadku zadań 10 i 11 ręczne testowanie opracowanych schematów funkcjonalnych może być nieskuteczne. W związku z tym proponujemy skorzystać z komputerowej implementacji maszyny Turinga, stworzonej przez R. Zartdinova. Można go uzyskać na stronie internetowej gazety „Informatika” ( inf.1września.ru). Np. tak wygląda schemat funkcjonalny z zadania 8 c) na tym aucie - różnice polegają na tym, że zamiast litery S jest znak drogowy, a zamiast symbolu „ a 0 ”jest napisane„ _ ”(podczas wpisywania polecenia do komórki tabeli należy nacisnąć klawisz„ spacja ”, a nie„ _ ”). Do programu dołączona jest szczegółowa pomoc, jak z nim pracować. Interfejs tego programu jest bardzo prosty. Ponadto opis tej implementacji maszyny Turinga można znaleźć w gazecie „Informatika” nr 8, 2006. Znajdziesz tam również analizę kilku innych problemów związanych z programowaniem maszyny Turinga; trzeba tylko pamiętać, że używają nieco innego (co jest zupełnie nieistotne) systemu poleceń.
* Przypomnij sobie, że wykres to zbiór punktów o nazwie szczyty i linie łączące niektóre wierzchołki. Jeśli kierunek jest wskazany na liniach łączących wierzchołki, wówczas wykres nazywa się zorientowany(w skrócie dwuznak), a linie nazywają się to łuki... Na zwykłym wykresie, czyli nieskierowane, linie łączące wierzchołki nazywają się żebra... Więcej o grafach zostanie omówione w Wykładzie 4.
Główne pytanie brzmi:?
Pytania przewodnie:
§ Jacy są wykonawcy?
§ Co charakteryzuje wykonawcę?
§ Jak sprawić, by wykonawca zrozumiał i wykonał algorytm?
Cele badań:
§ Znajdź przykłady różnych artystów.
§ Określ różnice między wykonawcami.
§ Dowiedz się, czym charakteryzują się wykonawcy.
§ Zbadaj, dlaczego wykonawcy nie zawsze mogą wykonać algorytm.
§ Podaj przykłady algorytmów i określ w nich wykonawcę.
Przykłady wykonawców
Do domu przyniesiono nową szafę ... Oznacza to, że nie ma szafy jako takiej, drzwi, półki, śruby i inne szczegóły przyszłego pojemnika na ubrania i bieliznę są ułożone na podłodze. Mój ojciec i ja podążamy za szczegółowe instrukcje, zacznijmy montować. Tutaj instrukcja działa jak algorytm, a ja z ojcem jako jego wykonawca.
Na lekcjach matematyki wykonujemy różne obliczenia - mnożymy i dzielimy kolumną, dodajemy proste ułamki. W takich przypadkach jesteśmy wykonawcami odpowiednich algorytmów.
Ale wykonawcą może być nie tylko osoba. Różne urządzenia, w tym komputer, mogą również wykonywać określone przez niego algorytmy. Na przykład Lunokhod, samobieżny pojazd automatyczny dostarczony na Księżyc w 1970 roku, wykonywał złożone algorytmy, poruszając się po powierzchni Księżyca i zbierając informacje niezbędne dla ludzi. Roboty przemysłowe zastępują ludzi w produkcji, w życiu codziennym z pomocą gospodyniom domowym przychodzą również urządzenia zdolne do działania według zadanych algorytmów.
Wykonawcy z bajek
Wykonawców często można znaleźć w bajkach. W jednym z nich Iwan Carewicz mówi do Chatki-Na-Nóżkach Kurczaka: „Chata, chała! Stań tyłem do lasu, przede mną!”. W takim przypadku polecenie musi być określone bardzo dokładnie, aby wykonawca je zrozumiał. W bajce „Ali Baba i czterdziestu złodziei” magiczne drzwi otworzyło polecenie „Sezam otwórz!”. Chciwy Kasym, który potajemnie wszedł do jaskini, zapomniał o tym zdaniu i nie mógł wyjść z jaskini.
Zarówno Chatka-Na-Chicken-Nogach, jak i magiczne drzwi mają ze sobą wiele wspólnego: wiedzą, jak rozumieć i wykonywać precyzyjnie określone polecenia, czyli są wykonawcami.
Kim jest wykonawca?
Wykonawcą algorytmu jest istota żywa lub obiekt techniczny zdolny do wykonywania czynności zaleconych przez algorytm.
Wykonawcami mogą być:
§ maszyny: obrabiarki, roboty, Urządzenia(pralka, magnetofon, odtwarzacz itp.), komputery;
§ rośliny: słonecznik (rozkłada się na słońcu), lilie wodne (zamyka się na noc);
§ zwierzęta: tresowany pies (porządny, poszukiwawczy, myśliwski), kot;
§ osoby: student, robotnik, żołnierz, nauczyciel, ...
Czy wszyscy wykonawcy są tacy sami?
Zwierzęta i ludzie jako wykonawcy różnią się od wszystkich innych wykonawców trzema głównymi cechami:
§ Rozumieją polecenia na różne sposoby (na przykład „Usiądź!”, „Usiądź!”, „Usiądź!”).
§ Mogą odmówić wykonania polecenia, jeśli mu się nie spodoba („Zjedz kaszę mannę!”, „Wystrzel przez okno z procy!”, „Daj kość!”). Oznacza to, że osoba i do pewnego stopnia zwierzę mają wolę i są odpowiedzialne za swoje działania.
§ Mogą inny czas wykonuj te same polecenia na różne sposoby (na przykład możesz umyć podłogę rękami lub użyć mopa).
Wykonawcy są dwojakiego rodzaju!
Zastanówmy się teraz nad tym pytaniem: skoro wykonawcy różnią się niektórymi cechami, to czy nie należy ich podzielić na dwie klasy? Wtedy nietrudno zgadnąć, że zwierzęta i ludzie będą należeć do jednej klasy, a wszyscy inni wykonawcy do innej. Pozostaje ustalić, jak nazwać te klasy i określić, jakie właściwości musi mieć wykonawca, aby dostać się do tej lub innej grupy.
Formalny i nieformalny
Aby to zrobić, pamiętajmy o jednej z właściwości algorytmu, a mianowicie o formalności, oznacza to, że wykonawca może nie rozumieć znaczenia algorytmu, ale mimo to wykonać go poprawnie… Czy człowiek lub zwierzę zawsze może to zrobić? Chyba nie, więc nie można powiedzieć, że wykonują algorytm formalnie, więc założymy, że człowiek i zwierzę są wykonawcami nieformalnymi.
Tak więc wykonując algorytm, wykonawca może nie zagłębić się w znaczenie tego, co robi, a mimo to uzyskać pożądany rezultat. W takich przypadkach mówią, że wykonawca działa formalnie, to znaczy jest oderwany od treści zadania i wykonuje wszystkie czynności tylko w ściśle określonej kolejności. To jest formalny wykonawca.
Jeśli wykonawca dokona jakichś zmian w algorytmie (zmienia kolejność kroków; niektóre pomija, uznając je za niepotrzebne lub nieistotne), to mówią, że taki wykonawca nie jest formalny.
Charakterystyka wykonawcy
Wykonawca, jak każdy przedmiot, ma swoje własne cechy.
Wykonawcę charakteryzuje:
§ SKI (system poleceń wykonawcy) – zestaw poleceń, które wykonawca rozumie i może wykonać.
Każdy executor może wykonywać polecenia tylko z określonej, ściśle określonej listy.
§ Środowisko - warunki, w których executor może wykonywać polecenia. Środowisko wykonawcy można również nazwać jego „siedliskiem”.
§ I zrzeczenia się:
1. „Nie rozumiem” – tego polecenia nie ma na liście poleceń wykonawcy, a on go nie zrozumiał. Prawdopodobnie popełniliśmy błąd pisząc tekst polecenia, polecenia nie ma w SKI.
2. „Nie mogę” – wykonawca zrozumiał polecenie, ale nie może go wykonać. Na przykład robot otrzymuje polecenie „naprzód”, ale z przodu jest ściana i nie może chodzić. Albo psu polecono „Usiądź!” A ona już siedziała.
Jak wykonawca wykona algorytm?
Wykonawca będzie mógł wykonać algorytm, jeśli go zna, jeśli został mu poinformowany o algorytmie. Dla ludzi najważniejszym sposobem komunikacji jest język. Wjeżdżając do obcego kraju i nie znając języka ojczystego, człowiek okazuje się zupełnie bezradny. Na ratunek może przyjść język migowy, mimika, pisanie za pomocą rysunków (pismo piktograficzne), ale to wszystko tylko częściowo poprawia sytuację.
Język naturalny (rosyjski, angielski, francuski, ...) jest podstawą pełnoprawnej komunikacji między ludźmi.
Języki naturalne są figuratywne i niejednoznaczne. Jeśli zajrzysz do słownika wyjaśniającego języka rosyjskiego, możesz na przykład dowiedzieć się, że istnieje ponad 20 znaczeń słowa „idź”. Oto tylko kilka przykładów: „Człowiek idzie drogą; pada deszcz; czas ucieka; ta sukienka jej pasuje; grzyby miodowe pójdą później, we wrześniu; chodźmy jutro na ryby? - wchodzi!
W języku naturalnym tym samym słowem można oznaczyć zupełnie inne pojęcia. Z reguły osoba z ogólnego znaczenia tekstu, czasem nawet bez zastanowienia, z całego zestawu znaczeń słowa, wybiera dokładnie to, o którym myślał nadawca wiadomości. Ale wyobraź sobie siebie w miejscu formalnego performera, który nie zagłębia się w sens całego przekazu. Jak w tym przypadku zrozumiesz zwroty: kwaśne moje; wczesna ucieczka; jadłem wszędzie; znajome środowisko?
Aby mieć pewność, że język formalnego kontrahenta nie może być wieloznaczny, staraliśmy się z pomocą formalnego tłumacza przetłumaczyć z angielskiego tekst o… Spróbuj zgadnąć, o co chodzi.
Dzisiejsze interesy z drewnem są - umarło - wycinane ze sklejki sosnowej, a następnie zanurzane w płynnych chemikaliach, które dają radę wypalaną światłem.
I chodziło o prostą drewnianą zapałkę, ale jak wyjaśnić tłumaczowi, że ze wszystkich znaczeń słowa „zapałka” trzeba było wybrać nie „umowę”, ale „zapałkę”, ze znaczeń tego słowa „wskazówka” – „wskazówka”, a nie „wskazówka”, „że” umrzeć „to znaczy nie tylko” umrzeć „ale także” pieczątka”, nie mówiąc już o zawiłościach konstrukcji gramatycznych?
Czym jest program?
Dla formalnego wykonawcy język komunikacji nie może być polisemantyczny, dla takich wykonawców opracowuje się i stosuje specjalne sztuczne języki, gdzie pojedyncze słowa a wyrażenia nie podlegają różnym interpretacjom.
Algorytm opisany w języku executora nazywany jest programem.
Aby nauczyć się pisać programy w tym czy innym języku, musisz przestudiować alfabet, słownictwo i zasady gramatyczne, według których budowane są zdania w tym języku, przy czym nie są dozwolone żadne odstępstwa od zasad pisania słów i zdań, w przeciwnym razie wykonawca po prostu odmów wykonania twoich instrukcji i nie będziesz oszołomiony i zmartwiony błędami, jak robi to przyjaciel Miszki z wiersza A. Shibaeva:
Przyszedł do mnie list
Patrzę -
Z obozu z Miszki...
Oto cudowny łuk i liżę
-Napisane w liście.
Czy łuk liże? Jakie cuda?
Pewnie cheat żartuje...
Czytam dalej:
Oto lis, piękna długa wędka...
Któregoś dnia znalazłem smutek w lesie
i był bardzo zadowolony...
Nie, nie, nie żartuje! Obawiam się,
Mój przyjaciel jest poważnie chory.
Zwroty - wymagają leczenia:
Niech zasady uczą ...
§ Wykonawcy są dwojakiego rodzaju: formalni i pozaformalni.
§ Wykonawcę charakteryzuje system dowodzenia, siedlisko i odmowy.
§ Aby wykonawca nas zrozumiał, konieczne jest napisanie algorytmu w języku wykonawcy, czyli napisanie programu.
| Planowanie lekcji i materiały lekcyjne | 6 stopni | Planowanie lekcji na rok akademicki (FSES) | Wykonawcy wokół nas
Lekcja 24
Wykonawcy wokół nas
Praca w środowisku performera Grasshopper
Wykonawcy formalni
Wykonawcy formalni
Istnieją dwa rodzaje wykonawców: formalne i nieformalne. Wykonawca formalny zawsze wykonuje to samo polecenie w ten sam sposób. Nieformalny wykonawca może wykonać polecenie na różne sposoby.
Na przykład, jeśli wielokrotnie słuchasz płyty z ulubioną muzyką, możesz być pewien, że jest ona odtwarzana przez odtwarzacz (formalny wykonawca) w ten sam sposób. Ale mało który śpiewak (nieformalny wykonawca) będzie w stanie kilkakrotnie wykonać piosenkę ze swojego repertuaru dokładnie w ten sam sposób.
Z reguły osoba działa jako nieformalny wykonawca. Formalni realizatorzy to przede wszystkim urządzenia techniczne. Osoba w roli nieformalnego performera sama jest odpowiedzialna za swoje działania. Podmiot, który go kontroluje, odpowiada za działania wykonawcy formalnego.
Rozważmy bardziej szczegółowo zestaw wykonawców formalnych. Formalni wykonawcy są niezwykle zróżnicowani, ale dla każdego z nich można określić zakres zadań do rozwiązania, środowisko, system dowodzenia, system awarii, tryby działania.
1. Zakres zadań do rozwiązania... Każdy wykonawca jest stworzony do rozwiązywania określonej klasy problemów.
2. Środowisko artystyczne... Obszar, otoczenie, warunki, w jakich działa performer, nazywane są zwykle środowiskiem danego performera.
3. System dowodzenia egzekutora... Polecenie wykonania przez wykonawcę odrębnej, zakończonej akcji nazywa się poleceniem. Całość wszystkich poleceń, które może wykonać dany wykonawca, tworzy SKI - system poleceń wykonawcy.
4. System odmowy wykonawcy... Odmowa „Nie rozumiem” pojawia się, gdy wykonawca otrzymuje polecenie, które nie jest zawarte w jego SKI. Odmowa „Nie mogę” pojawia się, gdy polecenie z SQI nie może być przez niego wykonane w określonych warunkach środowiskowych.
5. Tryby pracy wykonawcy... Dla większości wykonawców dostępne są bezpośrednie i zaprogramowane tryby sterowania. W pierwszym przypadku executor czeka na polecenia z obiektu kontrolnego i natychmiast wykonuje każde otrzymane polecenie. W drugim przypadku executor najpierw otrzymuje pełną sekwencję poleceń (program), a następnie wykonuje wszystkie te polecenia w tryb automatyczny... Wielu wykonawców pracuje tylko w jednym z tych trybów.
Artysta - osoba, grupa ludzi, zwierzę lub urządzenie techniczne zdolny do wykonywania określonego zestawu poleceń. Przykłady: Obiekt - wykonawca !! Przycisk włączania/wyłączania zasilania na obudowie komputera Przejdź do początku Pauza Stop Przejdź do końca Odtwórz System poleceń wykonawcy - CD-player
Bardziej złożony wykonawca. Działa na programach stworzonych przez człowieka. Program wybiera osoba. Maszyna działa automatycznie. Bardziej złożony wykonawca. Działa na programach stworzonych przez człowieka. Program wybiera osoba. Maszyna działa automatycznie. Wykonawca - pralka
Wykonawcy nieformalni i formalni Rolą wykonawcy nieformalnego jest najczęściej osoba Rolą wykonawcy formalnego jest najczęściej urządzenie techniczne Wykonawca nieformalny jest odpowiedzialny za swoje działania Za działania wykonawcy formalnego odpowiada obiekt, który go kontroluje
Formalny executor Formalny executor zawsze wykonuje to samo polecenie w ten sam sposób. Automatyczna maszyna do napełniania i pakowania Dla każdego formalnego kontrahenta możesz określić: zakres zadań do rozwiązania; Środa; system dowodzenia; system awarii; tryby pracy.
System odmów wykonawcy Odmowa „Nie rozumiem” powstaje, gdy wydane zostanie polecenie, które nie jest częścią SKI. Odmowa „Nie mogę” pojawia się, gdy polecenie z SQI nie może zostać wykonane w określonych warunkach środowiskowych. ? Pralka nie może wykonać polecenia płukania, jeśli urządzenie nie jest zasilane wodą. ?
Automatyzacja to zastąpienie części pracy ludzkiej pracą maszyny: proces rozwiązywania problemu przedstawiany jest w postaci ciągu najprostszych operacji; powstaje maszyna, która może wykonać te operacje w określonej kolejności; wykonanie algorytmu powierza się urządzeniu automatycznemu; osoba zostaje uwolniona od rutynowych czynności. Automatyzacja
Przede wszystkim Wykonawcą jest osoba, grupa ludzi, zwierzę lub urządzenie techniczne zdolne do wykonania wydawanych poleceń. Wykonawca formalny zawsze wykonuje to samo polecenie w ten sam sposób. Dla każdego formalnego kontrahenta możesz określić: - zakres zadań do rozwiązania; - Środa; –System poleceń; –System awarii; –Tryby pracy.
Wykonawcy algorytmów. Formalne wykonanie algorytmu. Komputer jako formalny wykonawca algorytmów (programów).
Rodzaj lekcji: łączny.
Cele Lekcji:
Przedstaw pojęcie „obiektu wykonawczego”;
Zapoznanie studentów z trzecim etapem tworzenia algorytmu;
Przedstaw koncepcję „Programu”;
Przedstaw zasady projektowania i wywoływania programu;
Nauczenie rozwiązywania problemów związanych z tworzeniem programów za pomocą algorytmu liniowego.
Cele Lekcji:
Kognitywny :
Organizowanie pracy studentów nad nauką i podstawowym utrwalaniem wiedzy poprzez:zbiorowa i niezależna działalność praktyczna.
Rozwijanie:
Używając zintegrowanego podejścia, pokaż uczniom znaczenie, jakie pojęcie „obiektu wykonawczego” ma w naturze, życiu codziennym, technologii i życiu codziennym.
Zapewnienie rozwoju umiejętności uczniów, które przyczyniają się do rozwoju pamięci, logicznego myślenia oraz wykorzystania posiadanej wiedzy i umiejętności w przygotowywaniu programów w języku programowania.
Edukacyjny:
Tworzenie kultura informacyjna, zdolność i umiejętności zbiorowego i samodzielnego opanowania wiedzy;
Aby pielęgnować kulturę mowy podczas odpowiadania przy tablicy, szanuj wszystkich uczestników procesu edukacyjnego.
Podczas zajęć
Etap organizacyjny
Wzajemne pozdrowienia nauczyciela i uczniów; naprawianie nieobecnych; sprawdzenie stanu zewnętrznego sali lekcyjnej; sprawdzenie gotowości uczniów do lekcji; organizacja uwagi i gotowości wewnętrznej.
Ogłoszenie tematu i celów lekcji. Powtórzenie materiału
Dzisiaj na lekcji będziemy nadal studiować technologię rozwiązywania problemów za pomocą komputera. Spotkaliśmy się już z wami pojęciem algorytmu i jego właściwościami. A przed przystąpieniem do nauki nowego materiału sprawdzimy Twoją gotowość do lekcji.
Sonda frontalna:
Wymień etapy rozwiązania problemu za pomocą komputera PC (postawienie problemu, określenie warunków, zbudowanie modelu problemu, opisanie algorytmu rozwiązania problemu, wybór optymalnego środowiska dla rozwiązania, opisanie algorytmu za pomocą wybranych narzędzia programowe, testowanie rozwiązania problemu, w razie potrzeby - korekta rozwiązania problemu)
Wymień główne właściwości algorytmu (dyskretność, dokładność, zrozumiałość, charakter masy, wydajność)
Wymień główne formy prezentacji algorytmów (werbalne, graficzne, programowe, tabelaryczne)
Wyjaśnienie nowego materiału:
Algorytmy rozwiązywania różnych problemów muszą być wykonalne w środowisku, w którym konieczne jest uzyskanie wyniku. W tym środowisku musi istnieć obiekt, który wykona algorytm. Spójrzmy na przykład. Petya chciał herbaty. Zagotował wodę w czajniczku, włożył torebkę herbaty do filiżanki, nalał do niej wrzątku, dodał dwie łyżeczki cukru, wymieszał łyżką iz przyjemnością wypił herbatę. Sformułujmy algorytm działań Petyi w postaci schematu blokowego (nauczyciel wzywa ucznia do tablicy).
W tym przykładzie wszystkie te czynności wykonuje Petya, dlatego to on jest obiektem realizującym algorytm. Petya wie, jak i potrafi wykonać czynności wskazane w algorytmie. Wykonuje te czynności we wskazanej kolejności. Obiekt, który wykonuje algorytm, nazywa sięwykonawca .
Rozróżnij wykonawców formalnych i nieformalnych. Wykonawca formalny wykonuje tę samą komendę w ten sam sposób. Nieformalny wykonawca może wykonać polecenie.
Formalni wykonawcy są niezwykle zróżnicowani, ale dla każdego z nich można określić następujące cechy: zakres zadań do rozwiązania (cel), środowisko, system dowodzenia i tryb działania.
Zakres zadań do rozwiązania. Każdy wykonawca jest tworzony w celu rozwiązania określonego zakresu zadań - budowania łańcuchów symboli, wykonywania obliczeń, rysowania rysunków na płaszczyźnie i tak dalej.
Środowisko artystyczne - warunki, w których możliwe jest wykonanie algorytmu.
Performer System Dowodzenia (SKI) - lista czynności, które wykonawca jest w stanie zrozumieć i wykonać.
System odmów wykonawców to lista odmów, która ma miejsce, gdy w określonych warunkach niemożliwe jest wykonanie algorytmu.
Tryby pracy wykonawcy - tryb sterowania bezpośredniego i programowanego. Bezpośrednia kontrola - wykonawca oczekuje polecenia od osoby i natychmiast je wykonuje. Sterowanie programem - executor otrzymuje sekwencję poleceń (program), a następnie wykonuje polecenia w trybie automatycznym. Niektórzy wykonawcy pracują tylko w jednym z trybów.
Wykonawcy napotkani w problemach to „Konik polny”, „Kalkulator”, „Wahadło”, „Żółw”, „Strzałka”, „Barwiarka”, „Strzałka”, „Żółw”, „Wodnik” itp. dr.
Przykład: Artysta Żółw porusza się po ekranie komputera, pozostawiając ślad w postaci linii. System poleceń składa się z następujących poleceń:
Do przodun(gdzien- liczba całkowita) - powoduje ruch dalejnkroki w kierunku ruchu - w kierunku, w którym ułożona jest głowa i ciało.
Dobrzem(gdziem- liczba całkowita) - powoduje zmianę kierunku ruchu omstopni zgodnie z ruchem wskazówek zegara.
Powtórz nagrywanieK [<Команда1> <Команда2> … <Команда n>] - oznacza, że sekwencja poleceń w nawiasach zostanie powtórzonakpewnego razu.
Zastanów się, jaki kształt pojawi się na ekranie po wykonaniu przez Żółwia następującego algorytmu:
Powtórz 12[ W prawo 45 Do przodu 20 W prawo 45]
Odpowiedź:
Przykład: System poleceń Kalkulator składa się z dwóch poleceń, którym przypisano numery:
1 - odejmij 1
2 - pomnóż przez 3
Podczas rejestrowania algorytmu, dla zwięzłości, wskazane są tylko numery poleceń. Na przykład algorytm 21212 oznacza:
Pomnóż przez 3
Odejmij 1
Pomnóż przez 3
Odejmij 1
Pomnóż przez 3
Ten algorytm zamienia liczbę 1 na 15: ((1 * 3-1) * 3-1) * 3 = 15
Przykład: Wykonawca Robot działa na polu w kratkę, pomiędzy sąsiednimi komórkami, których mogą znajdować się ściany. Robot porusza się po komórkach pola i może wykonywać polecenia: góra, dół, prawo, lewo.
Po wykonaniu każdego takiego polecenia Robot przesuwa się do sąsiedniej komórki w określonym kierunku. Jeśli w tym kierunku znajduje się ściana między komórkami, Robot zostaje zniszczony.
Co stanie się z Robotem, jeśli wykona sekwencję poleceń: w prawo, w dół, w prawo, w dół, w prawo. Zaczynając od komórki A. Jaką sekwencję poleceń powinien wykonać Robot, aby przejść z komórki A do komórki B bez zawalenia się po zetknięciu ze ścianami?
Algorytm przedstawiony w języku zrozumiałym dla Wykonawcy toprogram .
Program - uporządkowana sekwencja poleceń (instrukcji), niezbędne dla komputera rozwiązać problem.
Główna trudność w tworzeniu programów na komputer polega właśnie na stworzeniu lub znalezieniu algorytmu. Komponowanie programu według znanego algorytmu nazywa się kodowaniem.
Programowanie (kodowanie) - proces kompilacji programu na komputer.
Każdy algorytm przedstawiony w postaci programu musi mieć unikalną nazwę, która nie pokrywa się ze słowami wbudowanymi w język. Program posiada tytuł wskazujący jego nazwę. Nowy algorytm jest zapisywany w pamięci komputera pod własną nazwą i można go wywołać (wykonać) wpisując nazwę tego programu. Programy mają takie same właściwości jak algorytmy.
Podsumowanie lekcji:
Dialog:
Czego nowego nauczyłeś się na lekcji?
Jakie jest praktyczne znaczenie badanego zagadnienia?
Jakie są pozytywne aspekty lekcji.
Życzenia
Dzięki za pracę na lekcji!