Algoritmos e Estruturas de Dados é parte do conhecimento fundamental que todo programador precisa saber ou nunca vai avançar de verdade na profissão. Vamos ver a ponta do iceberg pra vocês terem uma idéia do que isso significa. E vou aproveitar pra consertar alguns erros que cometi no episódio anterior.
Erratas:
24:40 – sobre função aleatória eu falo que deveria ser distribuição gaussiana mas na realidade o correto é distribuição uniforme
25:48 – hash bitwise shift left 5 é equivalente a multiplicar por 32 e não 33
42:40 – na realidade O(n^n) exponencial é pior que O(n!) fatorial
44:35 – eu falo que NP é Não Polinomial, mas o certo é Non-Deterministic Polynomial time ou Tempo Polinomial Não Determinístico – que depois eu explico certo no video, mas nesse pedaço saiu errado
47:45 – complexidade exponencial é O(2^n) e não O(n^2)
Conteúdo:
00:00 – Intro
01:47 – Consertando meus erros de C
04:13 – Segmentos da Memória Virtual
11:53 – Arrays de Javascript são “Arrays”?
15:56 – Lista Ligada em C
21:37 – Hashtable em C
39:11 – Algoritmos de Ordenação
42:11 – Complexidade e Big O
43:30 – Vendedor Viajante e Fatorial
47:29 – Mergesort vs Quicksort
52:18 – Melhor e pior caso, Bubble vs Quick
55:45 – Livros sobre Algoritmos
Links:
* Visualgo.net (
Me siga nas redes sociais:
* Twitter (
* Instagram (
* Facebook (
* Podcasts (
Podcast:
Transcript:
source
A parte mais útil do episódio, pra mim, é o deslocamento: depois do Hello World, o problema deixa de ser só “fazer funcionar” e passa a ser entender o custo escondido de cada escolha. Array, lista ligada, hash, stack e heap mudam muito quando o volume cresce. Peguei os livros que apareceram nessa linha da conversa — nem todos como recomendação formal.
📚 LIVROS
The C Programming Language — Brian Kernighan e Dennis Ritchie (1:01)
O Mítico Homem-mês — Frederick P. Brooks Jr. (55:26)
The Art of Computer Programming — Donald Knuth (55:57)
Introduction to Algorithms — Cormen, Leiserson, Rivest e Stein (56:58)
A lista completa está no blog disponível no perfil.
Depois desse vídeo, terei que estudar tanenbaum com força. Eu tirei nota baixa em C. Preciso rever meus conceitos rapidamente.
não entendi mais tô compreedendo kkkkkk
Alguem mais teve um loop infinito por causa de garbage no codigo dos 17:40, como tem o if(previous) nao ta cobrindo casos onde tem lixo e nao ta com previous = NULL haha, so pra ver se mais alguem pego
57:00 E eu aqui lendo o "Entendendo Algoritmos" de Aditya Y. Bhargava, me sentindo uma criança chegando no clube do livro com sua revistinha da Monica enquanto todos estão lendo clássicos da literatura kkkkkk!
Meu primeiro programa de ordenamento de vetores usava o Bubble Sort. O professor simplesmente disse "escreva um programa que coloque em ordem do menor para o maior um vetor de n elementos". Era no tempo que você tinha que fazer primeiro um fluxograma depois escrever o programa em FORTRAN. Bubble Sort é a coisa mais natural para você fazer neste momento, nem precisa pensar muito e, para uma cadeira de Computação Básica, era mais que suficiente…
43:20 Na verdade esse algoritmo recursivo de cálculo de fatorial não é O(n) ?
A função recursiva é chamada no máximo N vezes, apenas uma vez para cada argumento
Vale a Pena aprender c como 1 linguagem pq parece mas verboso
Galera ai que está cursando TI deem valor nesse conteúdo. É ouro puro. Nem na faculdade vocês acharam conteúdos tão bons como o do Fábio Akita. Ele ensina ciência da computação e nao apenas programação. Lembre-se que o mercado vai ficar mais exigente e programadores sem base ficarão para trás.
assistido
Tó vendo que uma pessoa pra chegar a esse nível nunca para de estudar, eu acho que nem férias deve tirar (quer dizer tira férias sim, eu imagino que deve ficar brincando (Passa-Tempo na programação, e se aprofundar mais), falando em férias…. eu estou de férias, estou tentando aprender programação por que eu acho incrível, o que inspirou foi aquele anime do Digimon (o primeiro anime), sou servente prático de construção Civil, e este está sendo o meu HOBBY (QUE POR SINAL É BASTANTE COMPLEXO).
🤯 agora MUITA coisa faz sentido 🤯🤯🤯
voce da curso?
É tanto conteúdo que, pela primeira vez, precisei mexer na velocidade de reprodução. Porém, pra colocar em 0.85x 😆
Por sorte, eu vi um professor da Ufscar compartilhando um link do livro Algorithms do Jeff Erickson na faixa. Baixei o pdf e tá completaço batendo praticamente todos os tópicos do video. É só Googlar que acha.
Esse ano eu comecei a ler o "Estruturas de Dados" do Thiago Leite e Carvalho (Casa do Código) por pura aleatoriedade. Achei – simplesmente ACHEI – que era importante saber sobre o assunto e, caramba, que acerto. Agora eu entendi porque ele usou C pra explicar todos os conceitos. Realmente é pesado demais o conteúdo. Vão ser necessárias várias e várias passagens para realmente dominar o tema.
Se eu não ver isso aplicado em um progeto eu não conseguirei aprender
Se um iniciante pega esse vídeo ele desiste…
Livro de c!
Muito bom.
Aprendi isso (listas encadeadas) em AED no segundo período de Sistemas de Informação. Foi quando meus olhos se abriram para o paradigma da Orientação a Objetos, por mais bizarro que pareça,
Eu já vi esse vídeo umas 4 vezes e continua sendo uma verdadeira obra. Parabéns akita.
2024
17:57 só um extra sobre o %d. Ele formata especificamente números inteiros decimais. Para outros tipos, é necessário usar %f ou %lf (float e double). Existem outros também, mas é fácil de encontrar sobre isso na internet 😉
Muito bom.
Nos últimos dias , nos tempos livres , busco assistir aos vídeos deste canal. Honestamente, nunca vi um indivíduo tão capacitado fora dos filmes. Fogos ! Minha admiração
to estudando algoritmos e estruturas de dados, vi várias implementações em diferentes linguagens, só consegui entender de fato depois de assistir esse video, a forma que o Akita explica é mt boa
Cara, tava tendo dificuldade de entender isso na faculdade, mas o vídeo ficou muito didático e ajudou bastante. O interessante é que o Akita traz o histórico do problema junto casos reais. Acho que esse é o grande problema da faculdade, ela deixa muitas coisas muito abstratas, e trazer o contexto do problema ajuda a entender muito mais o assunto. Como pode um vídeo tão curto ser tão explicativo sobre o assunto? Parabéns pela didática!
Para quem ficou com vontade de verificar a colisão eu criei um algoritmo que testa strings aleatórias até achar o caso de hash code igual.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define HASH_SIZE 100
int hashCode(char *key);
int main(){
srand(time(NULL)); // Initialization, should only be called once.
char *validchars = "abcdefghijklmnopqrstuvwxyz";
char *s1 = "Akita"; // String comparada
char *s2 = ( char * ) malloc ( (strlen(s1) + 1) * sizeof(char));
int num = 0;
while (hashCode(s1) != hashCode(s2))
{
int tam = rand()%strlen(validchars) – 1;
for(int i = 0; i < tam; i++){
int index = rand()%strlen(validchars);
s2[i] = validchars[index];
s2[i+1] = 0x0;
}
printf("String comparada %s != %sn", s1, s2);
num++;
}
printf("String com para %s == %snn", s1, s2);
printf("O hash de %s é: %i sendo igual ao da string %s: %i", s1, hashCode(s1), s2, hashCode(s2));
printf("nForam testados mais de %i casosn", num);
}
int hashCode(char *key){
unsigned long hash = 2024; // inteiro sem sinal com capacidade de armazenamento maior
unsigned int c;
while (c = *key++) // char a char da cadeia de chars 🙂
{
hash = ((hash<<5) + hash) + c; // hash * 33 + c
}
return hash % HASH_SIZE;
}
Obv que não tem tanto material de C, poucas pessoas são doentes ao ponto de querer aprender C e pior ainda e difícil achar aquele que sabe e queira ensinar kkkkk
Uma observação: em 40:05, o Akita menciona que 'i' deve ir até 'total – 1', o que está correto já que o array tem 15 posições (0 a 14). O erro está na condição. 'i < total – 1', que vai parar em 13 ao invés de 14. Isso porque total – 1 nesse caso é 14, representando o último elemento do array, mas o operador '<' (menor que) não considera verdadeira a comparação se o número do lado esquerdo for igual ao número do lado direito (14). Veja o exemplo abaixo caso não tenha entendido nada:
1 < 14 = true
2 < 14 = true
[…]
13 < 14 = true
14 < 14 = false
O correto seria escolher uma das comparações abaixo:
i <= total – 1 (14 <= 14 = true); ou
i < total (14 < 15 = true)
Esperando pelo vídeo: "Consertando meu C#"
ensino da minha faculdade ta ate bom, entendi o video todo.
Obrigado
achei meio bosta mas de resto tudo certo
Tem uma coisa que eu não entendi, porque gerar hash da key na estrutura hashtable?, programo em Java, e sei que HashMap de Java faz a mesma coisa, mas porque gerar hash da key?. Na minha cabeça faz sentido em estruturas como Set, onde a key é o hash do value, e isso serve para não ter duplicação, visto que hash vai dar colisão se tiver os mesmos values. Mas e no Map? porque gerar hash da key? pelo que pesquisei é porque fica mais fácil de fazer os search, mas é isso mesmo?, é mais performatico ficar fazendo encode da key para o hash para ai fazer o search com este hash do que fazer search direto da key?
43:18 isso não é um exemplo de um código fatorial, isso é só um exemplo de um código que usa recursividade para achar o fatorial de um número, ele vai depender do tamanho da entrada "n", nesse caso, como ele só tem comparações e atribuições ele chega a ser O(N), bom mas não perfeito como log(n). Só que a recursividade tem lá seus problemas, para entradas muito grandes ela começa a dar b.o
17:47 – Tem um detalhe faltando no código de exemplo da função createNode: Você só grava o previous se for verdadeiro(linha 18), e como na primeira execução o previous é NULL(linha 25), o código pula o if e você não grava nenhum endereço para o ponteiro previous desse nó. Isso pode causar um loop infinito onde o seu while que printa os valores(linha 30) nunca fecha pq o NULL do first nunca foi gravado.
quem souber uma fonte confirmando isso que vou dizer por favor deixe o link, akita explicou nesse e em outros videos o comportamento da função realloc que aloca um bloco de memoria com um tamanho diferente e copia os dados do bloco antigo para o bloco novo.
pelo que li e testei agora isso nem sempre acontece, caso vc use realloc pra aumentar o tamanho de um bloco de memoria, a função so vai alocar um outro bloco maior e copiar os dados caso não seja possivel expandir o bloco original (não poder expandir no final do bloco por causa de fragmentação de memoria). A doc do gcc não deixa isso muito claro mas esse codigo aqui pelo menos no meu pc (linux) retorna o mesmo endereço
#include <stdio.h>
#include <stdlib.h>
int main(void) {
char *ptr1, *ptr2;
ptr1 = (char*)malloc(sizeof(char) * 10);
ptr2 = (char*)realloc(ptr1, sizeof(char) * 20);
printf("%pn", ptr1);
printf("%pn", ptr2);
return 0;
}
Fabio Akita, excelente exposição dos seus conhecimentos adquiridos na prática durante todos seus anos de trabalho. Você mostrou a todos que se as pessoas não aprenderem a sintaxe da linguagem C é impossível obter sucesso no desenvolvimento de qualquer programa.
Eu já não sei nada, vou entrar no python Jajá.
Vejo um vídeo desse
" É rapaz".
🤣🥲