Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

4SA101 Algoritmus

No description
by

Alexander Galba

on 29 February 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of 4SA101 Algoritmus

Co dělá počítač ?
sekvenční vykonávání instrukcí v dvojkové soustavě
umí to rychle 3 000 000 000/s
bez instrukcí NIC (smysluplného)
BIOS, OS, APLIKACE (programy)
Program - algoritmus
Co je algoritmus ?
návod jak postupovat
běžný život
recept, lidské chování, evakuační plán
zápis v přirozeném jazyku, graficky
vykonavatelem člověk
svět počítačů
programy
zápis v programovacím jazyku
vykonavatelem počítač (procesor)
Rozdíl ?
člověk je schopen samostatného uvažování
počítači se musí "říct všechno" =>
jeden z důvodů, proč dochází k chybám software(Y2K)
Matematika a algoritmy
Teorie algoritmů, Teorie vyčíslitelnosti
Alan Turing (Enigma), Kurt Gödel
algoritmů (programů) není víc než přirozených čísel => jdou očíslovat od 1,2,...
univerzální algoritmus (Turingův stroj) ?
číslo algoritmu (Gödelovo číslo) ?
úloha algoritmicky neřešitelná ?
Algorimty a praxe
obchodní cestující - jak obejít předem daná města tak, aby se ujelo co nejméně kilometrů (sypání silnic v zimě, poštovní doručovatel)
jak nálezt nejkratší(nejlevnější) cestu z bodu A do bodu B  (spediční, dopravní a logistické firmy, telekomunikace)
jak zakódovat (zašifrovat) informace
jak ukládat data tak, aby se rychle našli
předpověď počasí - jak vypočítat soustavu rovnic v omezeném čase
jak najít relevantní informace na Internetu (internetové vyhledávače
Vlastnosti algoritmu
Konečný
Univerzální
Deterministický
Krokově jednoduchý
Ověřitelný
Parciálně správný*
Výsledkový
 
* Existují pravděpodobnostní algoritmy, které v sobě obsahují prvky náhody (
Složitost algoritmu
rozhodujícím faktorem složitosti (efektivnosti) algoritmu je čas, který je nutný k provedení algoritmu a množství potřebných prostředků (počítačové paměti) 
závisí na rozsahu úlohy (vstupních podmínkách, vstupních datech)
 
Polynomiální složitost, náročnost -  nX  
Exponenciální složitost, náročnost - xn
     (n vyjadřuje velikost vstupních dat, x je přirozené číslo)
 
v praxi se používají algoritmy polynomiální složitosti
úloha: najít všechny cestu koně po šachovnicí tak, aby na každém políčku stál pouze jednou,prošel všechna políčka a vrátil se na výchozí pole:
        na šachovnici 6x6 polí                        9 862 řešení
        na šachovnici 8x8 polí 13 267 364 410 532 řešení
Způsoby zápisu algoritmu
zápis přirozeným jazykem
obrázkový návod
vývojový diagram, schéma
programovací jazyk
Visual Basic, C, C#, C++, Java, Javascript, PHP, SQL, Fortran, Cobol, Algol, Simula, Pascal, Lisp,...
strojově převoditelné do kódu který je schopen vykonat počítač
knihovny programů , funkcí, struktur
Programování je mix kreativního psaní, matematiky, křížovky a skládaní puzzle. Pokud se dostanete do potíží (a to se dostanete) tak je to také detektivní práce při hledání chyby.
JAAN TALLIN - Skype
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;

namespace WindowsApplication2
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}

private void buttonSpocist_Click(object sender, EventArgs e)
{
try {
int vstup = Int32.Parse(textBox1.Text);
if (vstup > 15 || vstup < 0)
{
label3.Text = "Umím jen od 1 do 15";
label3.Visible = true;
}
else
{
int faktorial = 1;
for (int i = 2; i <= vstup; i++) { faktorial = faktorial * i; }
label3.Text = faktorial.ToString();
label3.Visible = true;
}
}
catch (FormatException) {
label3.Text = "Neexistuje";
label3.Visible = true;
}

}

private void textBoxZadej_TextChanged(object sender, EventArgs e)
{
label3.Visible = false;
}

private void buttonExit_Click(object sender, EventArgs e)
{
this.Close();
}
}
Algoritmus - techniky
ohodnocovací funkce
pokus - oprava (backtracking)
rozděl a panuj
Praktická použitelnost algoritmu
existuje způsob, jak vyhrát v loterii Sportka?
existuje způsob, jak vyhrát v ruletě ?
existuje způsob, jak vyhrát šachovou partii ?
Sportka - 13 983 816 kombinací za 83 902 896,-CZK
Ruleta - sází se na barvu(na 18 čísel) a po každé prohře se zdvojnásobuje sázka
Šachy - v každém kroku se partie dohraje všemi možnými variantami a zvolí se nejvýhodnější
Praktická použitelnost algoritmu
MF ČR - jaký bude postup pro výběr subjektů k daňové kontrole ? (v roce 2010 cca 800.000 podnikatelských subjektů a  1.600.000 živnostníků)
Pořizování informací do IS, jak minimalizovat chybovost při zadávání dat ?
Komunikace se zákazníky. Jak minimalizovat v psané komunikaci chyby a kontrolovat její správnost ?
Pokud společnost žádá přeplatek DPH od určité výše -> automaticky je vyslána kontrola
 
Data se pořizují 2x po sobě 2 osobami
 
Pravidlo 4 očí – každou komunikaci přečte ještě jeden člověk kromě autora
Třídicí algoritmus

Seřaďte 1000 faktur číslovaných od 1 do 2 500 vzestupně.
Postupně budete brát faktury a necháte si v ruce tu, která má vyšší číslo, jinak ji odložíte na novou hromadu. Po projetí všech faktur položíte fakturu co máte v ruce na cílovou hromadu. Toto budete opakovat až nezbude žádná faktura.
Fakturu budete vždy porovnávat (999)*(1000)/2 = 499500x

Postupně budete brát do ruky faktury a budete tvořit cílovou hromadu tak, že každou fakturu zařadíte před první fakturu s vyšším číslem. Toto opakujete až nezbude žádná faktura.
Maximálně uděláte 499500x porovnání a minimálně 999x porovnání

Postupně budete procházet faktury po jedné tak, že porovnáte dvě po sobě jdoucí a pokud nejsou v relaci < (menší) prohodíte je. Takhle procházíte faktury do té doby až v jednom průchodu nedojde k prohození. Maximálně uděláte 499500x porovnání a minimálně 999x porovnání

Co když budete mít ještě někoho na výpomoc ?
Umělá inteligence
Turingův test
Searle - argument čínského pokoje

Komunikační programy - Eliza, www.elbot.com

Co je inteligence ?
Co znamená myslet a co znamená simulovat myšlení ?

Sci-fi - záloha vědomí, uload, download, nesmrtelnost
Full transcript