Úvod do programování ALG110006
KONTAKT
[email protected] http://jonathan.verner.matfyz.cz/vyuka
POŽADAVKY (zimní semestr)
Nutno získat 216 bodů ! •
zápočtový test, 144 bodů (50 %)
•
domácí úkoly, 120 bodů (41.6666 %)
•
docházka, 12 bodů (4.1666 %)
•
bonus, 12 bodů (4.1666 %)
PREHISTORIE Antikytera •
1900 nalezeno ve vraku
•
1951 J. de Solla Price
počítalo pozici Slunce, Měsíce (možná i dalších planet), fázi měsíce, zatmění slunce, data celořeckých her •
150 - 100 př. Kr.
http://www.antikythera-mechanism.gr
PREHISTORIE Abakusy, z hebr. ābāq ()אבק, "prach" Sumerové (2700 př. Kr.), Římané, Číňané, Japonci, Mayové, Indové •
kalkulovat, z lat calculos ponere = položit kaménky •
Římský Abakus
PREHISTORIE •
Římané, Odometr
•
1620 Logaritmické pravítko
1623 „kalkulačka“ (Schickard, shořela před dokončením) •
1642 první mechanická kalkulačka, B. Pascal, ještě jako dítě •
Pascalina
1820 první komerčně vyráběná kalkulačka, Ch. X. Thomas (uměla +,-,×,÷) •
1963 první komerční celoelektronická kalkulačka, stála 2200 dolarů, uměla +,-,×,÷ •
Curta (1948)
Charles Babbage (1781-1871)
osobní život tragický, v jednom roce mu zemřela manželka, otec a syn, jeho projekty zůstaly vesměs nedokončené •
navrhl difference engine, později analytical engine •
•
prolomil Vigenérovu "auto-key" šifru
předpověděl důležitost výpočtové složitosti •
Difference Engine 1876 J. H. Müller, první "idea" difference enginu •
1822 Ch. Babbage, první návrhy, prototyp by vážil 15 tun, byl vysoký 2.4 metru; nebyl nikdy dokončen •
1855 Scheutz, postavil několik funkčních DE podle Babbageových plánů, 59 prodal několik exemplářů Britské vládě •
1989-91 byl postaven model DE v2 podle Babbageových plánů (metodami dostupnými v 19. stol) ; počítá s přesností na 31 desetinných míst, víc než většina dnešních kalkulaček •
Difference Engine
Difference Engine některé důležité funkce (log., odmocnina, sinus, ...) obecně nelze "spočítat" přesně •
•
tyto funkce lze aproximovat polynomy
v 19. stol. se tyto funkce vypočítávaly ručně; náročné, velmi chybové •
difference engine měl tuto práci automatizovat •
založený na Newtonově metodě dělení rozdílů •
Analytical engine •
nikdy nezkonstruována (nedostatek financí)
•
"parní počítač"
•
první "Turingovsky úplný" stroj
první programátorka, hraběnka Adelaida Lovelace Byronová (navrhla program na výpočet Bernoulliho čísel) •
http://www.fourmilab.ch/babbage/sketch.html
Děrné štítky 1801, J. M. Jacquard, programovatelný tkalcovský stav •
1842, princip automatického klavíru, čtoucího noty z děrné pásky •
Děrné štítky 1890, Herman Hollerith, výrazně (o několik let) zkrátil a zlevnil zpracování dat ze sčítání lidu v USA •
používal děrné štítky k ukládání dat; jejich velikost byla dána velikostí amerických bankovek té doby, protože pro ně již existovaly stroje na zpracování •
•
založil firmu, ze které později vzniklo IBM
pozdější verze "tabulačního stroje" počítaly diferenciální rovnice, za války se používaly ke statistickému zpracování dat pro kryptografii •
Analogové počítače αναλογικος (úměrně) Differential analyser 1836, Gaspard-Gustave Coriolis navrhl mechanický přístroj na integrování diferenciálních rovnic prvního řádu 1876, integrování dif. rovnic libovolného řádu, James Thomson (bratr lorda Kelvina) 1912, Differential analyzer použit pro řízení námořních děl britské armády (Arthur Pollen) 1928-31, první šířeji využitelný počítač, na MITu, H. L. Hazen & Vannevar Bush (1936 zaměstnali Clauda Shannona, aby stroj řídil) 1934, postaven model ze stavebnice mecana na Manchesterské univerzitě
Analogové počítače
Model ze stavebnice Mecano
Analogové počítače Stroj na výpočet přílivu/odlivu •
Lord Kelvin (William Thomson) 1872
•
podobné stroje používány až do 70 let
•
použity např. k výpočtům pro den D.
použitá matematika: Newton (teorie gravitace), Laplace (aplikace na příliv a odliv), Laplace, W. Thomson (použití fourrierovy analýzy) je třeba sečíst fourrierovu řadu •
A1cos(ω1t +φ1) + A2cos(ω2t +φ2) + ... Stroj na počítání přílivu/odlivu
Analogové počítače
Analogové počítače Další analogové počítače •
FERMIAC (Enrico Fermi, 1947 studium neutronového přenosu)
•
MONIAC (hydraulický ekonomický model :-) )
•
Elektrické analogové počítače
•
Hybridní počítače
oproti digitálním počítají s reálnými čísly (některé problémy, realisticky neřešitelné digitálními •
počítači teoreticky lze spočíst analogovými, ale prakticky díky šumu nikoliv) •
Mark 56 (dělostřelecký zaměřovač, navržen za druhé světové války A. Svobodou)
Antonín Svoboda Vystudoval ČVUT, 1935 získal doktorát, 1936 přešel na ministerstvo obrany, konstruoval automatické zaměřovače pro protiletecké kanóny Utekl před nacisty do francie, kde se dále věnoval konstrukcím; narodily se mu děti, nepodařilo se utéci do anglie, dostal se do Portugalska a pak do USA; jeho kolegovi se podařilo nalodit na loď do UK, ale kolo, v jehož rámu měli schovány plány, musel hodit do moře (měl na vybranou mezi sebou a kolem) spolupracoval v MIT s Johnem von Neumannem, Vannevarem Bushem a Claudem Shannonem 1946 se vrátil do Prahy, vedoucím katedry matematiky na ČVUT, pak odešel a využil nabídky E. Čecha a založil Výzkumný ústav matematických strojů 1950-56 navrhl, 1957-60 zkonstruoval SAPO (samočinný počítač), první Fault-tolerant počítač na světě (tři aritmetické jednotky, výsledek byla shoda dvou, nebo se přepočítal), v porovnání s ENIAC byl dost vyspělý 1964 emigroval přes Jugoslávii do Ameriky, zde se mu hodila medaile, kterou dostal za Mark 56 (jinak by ho vyhodili) byl na UCLA profesorem informatiky napsal jednu z prvních učebnic informatiky více viz http://www.vumscomp.cz/Svoboda.html
A. Svoboda 1907 - 1980
John von Neumann pracoval na atomové bombě, později na vodíkové bombě rozvinul metodu Monte-Carlo simulace navrhl pseudorandom number generator (middle squares method start with 4-digit number, square, pad with 0 to get 8 digits, output middle four and continue), nebyl ideální, ale byl rychlý při práci na EDVACu napsal zprávu, ve které popsal tzv. von Neumannovu architekturu, t.j. program a data jsou uložená v paměti ve stejném místě; (návrh byl částečně založen na předchozí práci Eckerta a Mauchlyho z ENIACu) navrhnul (tvrdí Knuth) merge sort vymyslel cellular automata (ekvivalentní univerzálnímu Turingově stroji)
J. von Neumann (1903-1957)
Alan Turing I hope he will not fall between two stools. If he is to stay at Public School, he must aim at becoming educated. If he is to be solely a Scientific Specialist, he is wasting his time at a Public School Studoval v Cambridge, Kings College, dizertace na centrální limitní větu Pracoval na počítači ACE Přišel s pojmem "Turingova stroje" (matematická formalizace počítače) Student Alonzo Churche (36-38) Podílel se na rozluštění Enigmy 1945 získal OBE Turingův test - počítač je inteligentní, pokud člověk nepozná, že mluví s počítačem Napsal první šachový program (nebyly dostatečně silné počítače, tak hrál místo počítače) 1952 odsouzen za homosexualitu 1954 nalezen mrtvý (vedle postele leželo nakousnuté nejspíše otrávené jablko)
A. Turing (1912-1954)
Turingův stroj
K samostudiu Norbert Wiener Kolmogorov Claude Shannon Alonzo Church http://en.wikipedia.org/wiki/Timeline_of_computing_2400_BC–1949 http://en.wikipedia.org/wiki/Timeline_of_computing_1950–1979
